Publication

Automating cutting planes is NP-hard

Related publications (64)

Graph Chatbot

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.

Deciding Conditional Termination

We address the problem of conditional termination, which is that of defining the set of initial configurations from which a given program always terminates. First we define the dual set, of initial configurations from which a non-terminating execution exis ...

Tech Univ Braunschweig2014

Extendability of Continuous Maps Is Undecidable

We consider two basic problems of algebraic topology: the extension problem and the computation of higher homotopy groups, from the point of view of computability and computational complexity. The extension problem is the following: Given topological space ...

Springer2014

Matrix Completion on Graphs

Pierre Vandergheynst, Michael Bronstein, Xavier Bresson, Vasilis Kalofolias

The problem of finding the missing values of a matrix given a few of its entries, called matrix completion, has gathered a lot of attention in the recent years. Al- though the problem under the standard low rank assumption is NP-hard, Cande`s and Recht sho ...

2014

Testing additive integrality gaps

Friedrich Eisenbrand, Gennady Shmonin

We consider the problem of testing whether the maximum additive integrality gap of a family of integer programs in standard form is bounded by a given constant. This can be viewed as a generalization of the integer rounding property, which can be tested in ...

Springer Berlin Heidelberg2013

Tractability of interpretability via selection of group-sparse models

Volkan Cevher, 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. A promise of these models is to lead to “interpretable” signals for which we identify i ...

2013

Decomposition and tractability in qualitative spatial and temporal reasoning

Jingshi Li

Constraint networks in qualitative spatial and temporal reasoning (QSTR) typically feature variables defined on infinite domains. Mainstream algorithms for deciding network consistency are based on searching for network refinements whose consistency is kno ...

Elsevier2013

Santa Claus Schedules Jobs On Unrelated Machines

Ola Nils Anders Svensson

One of the classic results in scheduling theory is the 2-approximation algorithm by Lenstra, Shmoys, and Tardos for the problem of scheduling jobs to minimize makespan on unrelated machines; i.e., job j requires time p(ij) if processed on machine i. More t ...

Siam Publications2012

The RADO approach to Quality-Driven Service Composition - Approximating the Pareto-Frontier in Polynomial Time

Boi Faltings, Immanuel Trummer

In Quality-Driven Service Composition, tasks from an ab- stract work ow are assigned to concrete services such that work ow QoS are optimized. The following three proper- ties are desirable for a corresponding algorithm. First, the run time is ideally boun ...

2012

Nanoparticle actuated hollow drug delivery vehicles

Esther Amstad

The trend towards personalized medicine and the long-standing wish to reduce drug consumption and unwanted side effects have been the driving force behind research on drug delivery vehicles that control localization, timing and dose of released cargo. Cont ...

2012

Automating cutting planes is NP-hard

Graph Chatbot

Chat with Graph Search

Deciding Conditional Termination

Extendability of Continuous Maps Is Undecidable

Matrix Completion on Graphs

Testing additive integrality gaps

Tractability of interpretability via selection of group-sparse models

Decomposition and tractability in qualitative spatial and temporal reasoning

Sponsored search, market equilibria, and the Hungarian Method

Santa Claus Schedules Jobs On Unrelated Machines

The RADO approach to Quality-Driven Service Composition - Approximating the Pareto-Frontier in Polynomial Time

Nanoparticle actuated hollow drug delivery vehicles

Deciding Conditional Termination

Tractability of interpretability via selection of group-sparse models

Extendability of Continuous Maps Is Undecidable

Matrix Completion on Graphs

Sponsored search, market equilibria, and the Hungarian Method

Testing additive integrality gaps

Decomposition and tractability in qualitative spatial and temporal reasoning

The RADO approach to Quality-Driven Service Composition - Approximating the Pareto-Frontier in Polynomial Time

Nanoparticle actuated hollow drug delivery vehicles

Santa Claus Schedules Jobs On Unrelated Machines