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.

Efficient SIMD Arithmetic Modulo a Mersenne Number

Arjen Lenstra, Joppe Willem Bos, Thorsten Kleinjung

This paper describes carry-less arithmetic operations modulo an integer 2^M-1 in the thousand-bit range, targeted at single instruction multiple data platforms and applications where overall throughput is the main performance criterion. Using an implementa ...

IEEE2011

Content Search Through Comparisons

Amin Karbasi

We study the problem of navigating through a database of similar objects using comparisons under heterogeneous demand, a problem strongly related to small-world network design. We show that, under heterogeneous demand, the small-world network design proble ...

2011

CoPhy: A Scalable, Portable, and Interactive Index Advisor for Large Workloads

Anastasia Ailamaki, Debabrata Dash

Index tuning, i.e., selecting the indexes appropriate for a workload, is a crucial problem in database system tuning. In this paper, we solve index tuning for large problem instances that are common in practice, e.g., thousands of queries in the workload, ...

2011

Testing additive integrality gaps

Friedrich Eisenbrand, Nicolai Hähnle, Gennady Shmonin

We consider the problem of testing whether the maximum 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 polynomi ...

2010

Conditional hardness of precedence constrained scheduling on identical machines

Ola Nils Anders Svensson

Already in 1966, Graham showed that a simple procedure called list scheduling yields a 2-approximation algorithm for the central problem of scheduling precedence constrained jobs on identical machines to minimize makespan. Till this date it has remained th ...

ACM2010

The interval constrained 3-coloring problem

Laura Sanità

In this paper, we settle the open complexity status of interval constrained coloring with a fixed number of colors. We prove that the problem is already NP-complete if the number of different colors is 3. Previously, it has only been known that it is NP-co ...

Springer Verlag2010

Heuristics for Distributed Pseudo-tree Regeneration

Jonas Helfer

The goal of this project is to develop a new heuristic for pseudo-tree regeneration in S-DPOP. S-DPOP is a version of DPOP which should show performance improvements when resolving problems after small changes. Examples of such problems are: tracking movin ...

2010

Factorization of a 768-Bit RSA Modulus

Arjen Lenstra, Joppe Willem Bos, Thorsten Kleinjung, Dag Arne Osvik, Patric Zimmermann

This paper reports on the factorization of the 768-bit number RSA-768 by the number field sieve factoring method and discusses some implications for RSA. ...

Springer-Verlag New York, Ms Ingrid Cunningham, 175 Fifth Ave, New York, Ny 10010 Usa2010

Polychromatic colorings of arbitrary rectangular partitions

Balázs Keszegh

A general (rectangular) partition is a partition of a rectangle into an arbitrary number of non-overlapping subrectangles. This paper examines vertex 4-colorings of general partitions where every subrectangle is required to have all four colors appear on i ...

2010

New Hardness Results for Diophantine Approximation

Friedrich Eisenbrand, Thomas Rothvoss

We revisit simultaneous diophantine approximation, a classical problem from the geometry of numbers which has many applications in algorithms and complexity. The input of the decision version of this problem consists of a rational vector \alpha, an error b ...

Springer2009