Publications associées à Strengths and Limitations of Linear Programming Relaxations

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem

Ola Nils Anders Svensson, Jakub Tarnawski

We give a constant-factor approximation algorithm for the asymmetric traveling salesman problem. Our approximation guarantee is analyzed with respect to the standard LP relaxation, and thus our result confirms the conjectured constant integrality gap of th ...

ASSOC COMPUTING MACHINERY2018

From Infinite to Finite Programs: Explicit Error Bounds with Applications to Approximate Dynamic Programming

Daniel Kuhn, John Lygeros, Peyman Mohajerin Esfahani, Tobias Sutter

We consider linear programming (LP) problems in infinite dimensional spaces that are in general computationally intractable. Under suitable assumptions, we develop an approximation bridge from the infinite-dimensional LP to tractable finite convex programs ...

2018

Load Balancing Video Clients in Enterprise Wireless Networks

Dan-Cristian Tomozei, Lorenzo Granai, Aswin Suresh, Sergio Mena

Given the increasing popularity of real-time video communication over enterprise wireless networks, ensuring good quality of experience is becoming critical. A common problem in such networks is that the clients typically adopt the strategy of associating ...

IEEE2018

Proximity results and faster algorithms for Integer Programming using the Steinitz Lemma

Friedrich Eisenbrand

We consider integer programming problems in standard form max{c(T)x : Ax = b; x >= 0, x is an element of Z(n)} where A is an element of Z(mxn), b is an element of Z(m) and c is an element of Z(n). We show that such an integer program can be solved in time ...

ASSOC COMPUTING MACHINERY2018

Sharp sphere packings

Maryna Viazovska

In this talk we will speak about recent progress on the sphere packing problem. The packing problem can be formulated for a wide class of metric spaces equipped with a measure. An interesting feature of this optimization problem is that a slight change of ...

World Scientific Publishing2018

Using Structural Properties for Integer Programs

Kim-Manuel Klein

Integer programs (IPs) are one of the fundamental tools used to solve combinatorial problems in theory and practice. Understanding the structure of solutions of IPs is thus helpful to argue about the existence of solutions with a certain simple structure, ...

SPRINGER INTERNATIONAL PUBLISHING AG2018

Hardness Results for Consensus-Halving

Jie Zhang, Aris Filos Ratsikas

The Consensus-halving problem is the problem of dividing an object into two portions, such that each of n agents has equal valuation for the two portions. We study the epsilon-approximate version, which allows each agent to have an epsilon discrepancy on t ...

Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik2018

Conic Programming Reformulations of Two-Stage Distributionally Robust Linear Programs over Wasserstein Balls

Daniel Kuhn, Grani Adiwena Hanasusanto

Adaptive robust optimization problems are usually solved approximately by restricting the adaptive decisions to simple parametric decision rules. However, the corresponding approximation error can be substantial. In this paper we show that two-stage robust ...

2018

Strengths and Limitations of Linear Programming Relaxations

Graph Chatbot

Chattez avec Graph Search

Algorithms For Clustering Problems

When Stuck, Flip a Coin

A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem

From Infinite to Finite Programs: Explicit Error Bounds with Applications to Approximate Dynamic Programming

Load Balancing Video Clients in Enterprise Wireless Networks

Proximity results and faster algorithms for Integer Programming using the Steinitz Lemma

Sharp sphere packings

Using Structural Properties for Integer Programs

Hardness Results for Consensus-Halving

Conic Programming Reformulations of Two-Stage Distributionally Robust Linear Programs over Wasserstein Balls

Conic Programming Reformulations of Two-Stage Distributionally Robust Linear Programs over Wasserstein Balls

Load Balancing Video Clients in Enterprise Wireless Networks

From Infinite to Finite Programs: Explicit Error Bounds with Applications to Approximate Dynamic Programming

Algorithms For Clustering Problems

When Stuck, Flip a Coin

Hardness Results for Consensus-Halving

A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem

Proximity results and faster algorithms for Integer Programming using the Steinitz Lemma

Sharp sphere packings

Using Structural Properties for Integer Programs