Publication

The double exponential runtime is tight for 2-stage stochastic ILPs

Related publications (74)

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.

Sign changes of Kloosterman sums with almost prime moduli

Ping Xi

We prove that the Kloosterman sum changes sign infinitely often as runs over squarefree moduli with at most 10 prime factors, which improves the previous results of Fouvry and Michel, Sivak-Fischler and Matomaki, replacing 10 by 23, 18 and 15, respectively ...

Springer Verlag2015

Node-weighted network design and maximum sub-determinants

Carsten Moldenhauer

We consider the Node-weighted Steiner Forest problem on planar graphs. Demaine et al. showed that a generic primal-dual algorithm gives a 6-approximation. We present two different proofs of an approximation factor of~

3

. Then, we draw a connection to Goem ...

EPFL2014

Coding Structure and Replication Optimization for Interactive Multiview Video Streaming

Pascal Frossard

Multiview video refers to videos of the same dynamic 3-D scene captured simultaneously by multiple closely spaced cameras from different viewpoints. We study interactive streaming of pre-encoded multiview videos, where, at any time, a client can request an ...

Ieee-Inst Electrical Electronics Engineers Inc2014

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. Although the problem is NP-hard, Candes and Recht showed that it can be exactly relaxed if the ...

2014

Prime Power Terms In Elliptic Divisibility Sequences

Valéry Aurélien Mahé

We study a problem on specializations of multiples of rational points on elliptic curves analogous to the Mersenne problem. We solve this problem when descent via isogeny is possible by giving explicit bounds on the indices of prime power terms in elliptic ...

American Mathematical Society2014

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

Single machine scheduling with scenarios

Ola Nils Anders Svensson

In the field of robust optimization, the goal is to provide solutions to combinatorial problems that hedge against variations of the numerical parameters. This constitutes an effort to design algorithms that are applicable in the presence of uncertainty in ...

2013

Some applications of the Weil-Barner explicit formula

Thorsten Kleinjung

The Weil-Barner explicit formula is applied to the prime counting function and to the problem of numerical partial verification of the Riemann hypothesis. ...

Wiley-V C H Verlag Gmbh2013

New Results in the Theory of Linear and Integer Programming

Nicolai Hähnle

The polynomial Hirsch conjecture states that the vertex-edge diameter of a d-dimensional polyhedron with n facets is bounded by a polynomial in d and n. For the special case where the polyhedron is defined as the set of points satisfying a system Ax ≤ b of ...

EPFL2012

Node-weighted network design and maximum sub-determinants

Carsten Moldenhauer

3

. Then, we draw a connection to Goem ...

EPFL2014