Publications related to Set cover problem

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Optimal Representations for Adaptive Streaming in Interactive Multiview Video Systems

Pascal Frossard, Laura Toni

Interactive multiview video streaming (IMVS) services permit to remotely navigate within a 3D scene with an immersive experience. This is possible by transmitting a set of reference camera views (anchor views), which are used by the clients to freely navig ...

Ieee-Inst Electrical Electronics Engineers Inc2017

Dynamic Facility Location via Exponential Clocks

Ola Nils Anders Svensson, Ashkan Norouzi Fard, Hyung Chan An

The dynamic facility location problem is a generalization of the classic facility location problem proposed by Eisenstat, Mathieu, and Schabanel to model the dynamics of evolving social/infrastructure networks. The generalization lies in that the distance ...

Association for Computing Machinery2017

Probabilistic Schema Covering

Quoc Viet Hung Nguyen, Thành Tâm Nguyên, Chi Thang Duong

Schema covering is the process of representing large and complex schemas by easily comprehensible common objects. This task is done by identifying a set of common concepts from a repository called concept repository and generating a cover to describe the s ...

2017

Group-Sparse Model Selection: Hardness and Relaxations

Volkan Cevher, Anastasios Kyrillidis, Luca Baldassarre, Nirav Bhan

Group-based sparsity models are proven instrumental in linear regression problems for recovering signals from much fewer measurements than standard compressive sensing. The main promise of these models is the recovery of ``interpretable" signals along with ...

Institute of Electrical and Electronics Engineers2016

Approximate BDD Optimization with Prioritized epsilon-Preferred Evolutionary Algorithm

Mathias Soeken

Approximate computing has gained high attention in various applications that can benefit from a reduction in costs by lowering the accuracy. In this paper we present an optimization approach for functional approximation of Binary Decision Diagrams (BDDs) w ...

Assoc Computing Machinery2016

Multiple Query Optimization on the D-Wave 2X Adiabatic Quantum Computer

Christoph Koch, Immanuel Trummer

The D-Wave adiabatic quantum annealer solves hard combinatorial optimization problems leveraging quantum physics. The newest version features over 1000 qubits and was released in August 2015. We were given access to such a machine, currently hosted at NASA ...

Assoc Computing Machinery2016

Strong LP formulations for scheduling splittable jobs on unrelated machines

Ola Nils Anders Svensson

A natural extension of the makespan minimization problem on unrelated machines is to allow jobs to be partially processed by different machines while incurring an arbitrary setup time. In this paper we present increasingly stronger LP-relaxations for this ...

Springer Heidelberg2015

No Small Linear Program Approximates Vertex Cover within a Factor 2 - e

Ola Nils Anders Svensson, Abbas Bazzi

The vertex cover problem is one of the most important and intensively studied combinatorial optimization problems. Khot and Regevproved that the problem is NP-hard to approximate within a factor2 - ∈, assuming the Unique Games Conjecture (UGC). This is tig ...

IEEE Computer Society2015

Approximating ATSP by Relaxing Connectivity

Ola Nils Anders Svensson

The standard LP relaxation of the asymmetric traveling salesman problem has been conjectured to have a constant integrality gap in the metric case. We prove this conjecture when restricted to shortest path metrics of node-weighted digraphs. Our arguments a ...

IEEE Computer Society2015

Set cover problem

Graph Chatbot

Chat with Graph Search

Strengths and Limitations of Linear Programming Relaxations

Optimal Representations for Adaptive Streaming in Interactive Multiview Video Systems

Dynamic Facility Location via Exponential Clocks

Probabilistic Schema Covering

Group-Sparse Model Selection: Hardness and Relaxations

Approximate BDD Optimization with Prioritized epsilon-Preferred Evolutionary Algorithm

Multiple Query Optimization on the D-Wave 2X Adiabatic Quantum Computer

Strong LP formulations for scheduling splittable jobs on unrelated machines

No Small Linear Program Approximates Vertex Cover within a Factor 2 - e

Approximating ATSP by Relaxing Connectivity

Strengths and Limitations of Linear Programming Relaxations

Dynamic Facility Location via Exponential Clocks

No Small Linear Program Approximates Vertex Cover within a Factor 2 - e

Probabilistic Schema Covering

Group-Sparse Model Selection: Hardness and Relaxations

Approximating ATSP by Relaxing Connectivity

Approximate BDD Optimization with Prioritized epsilon-Preferred Evolutionary Algorithm

Optimal Representations for Adaptive Streaming in Interactive Multiview Video Systems

Multiple Query Optimization on the D-Wave 2X Adiabatic Quantum Computer

Strong LP formulations for scheduling splittable jobs on unrelated machines