Publications related to Proximity Results and Faster Algorithms for Integer Programming Using the Steinitz Lemma

On approximation algorithms and polyhedral relaxations for knapsack problems, and clustered planarity testing

Knapsack problems give a simple framework for decision making. A classical example is the min-knapsack problem (MinKnap): choose a subset of items with minimum total cost, whose total profit is above a given threshold. While this model successfully general ...

EPFL2019

Covering convex bodies and the Closest Vector Problem

Moritz Andreas Venzin, Márton Naszódi

We present faster algorithms for the approximate Closest Vector Problem under l_p norms ...

2019

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

Faster Algorithms for Integer Programs with Block Structure

Friedrich Eisenbrand, Kim-Manuel Klein, Christoph Hunkenschröder

We consider integer programming problems max {c^Tx : A x = b, l

Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik2018

Small Extended Formulation for Knapsack Cover Inequalities from Monotone Circuits

Ola Nils Anders Svensson, Abbas Bazzi, Sangxia Huang

Initially developed for the min-knapsack problem, the knapsack cover inequalities are used in the current best relaxations for numerous combinatorial optimization problems of covering type. In spite of their widespread use, these inequalities yield linear ...

UNIV CHICAGO, DEPT COMPUTER SCIENCE2018

Robust auction design under multiple priors by linear and integer programming

Cagil Kocyigit

It is commonly assumed in the optimal auction design literature that valuations of buyers are independently drawn from a unique distribution. In this paper we study auctions under ambiguity, that is, in an environment where valuation distribution is uncert ...

2018

Sum-Rate Capacity for Symmetric Gaussian Multiple Access Channels with Feedback

Michael Christoph Gastpar, Erixhen Sula

The feedback sum-rate capacity is established for the symmetric three-user Gaussian multiple-access channel (GMAC). The main contribution is a converse bound that combines the dependence-balance argument of Hekstra and Willems (1989) with a variant of the ...

2018

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

On some algebraic and extremal problems in discrete geometry

Seyed Hossein Nassajianmojarrad

In the present thesis, we delve into different extremal and algebraic problems arising from combinatorial geometry. Specifically, we consider the following problems. For any integer

n\ge 3

, we define

e(n)

to be the minimum positive integer such that an ...

EPFL2017

Strengths and Limitations of Linear Programming Relaxations

Abbas Bazzi

Many of the currently best-known approximation algorithms for NP-hard optimization problems are based on Linear Programming (LP) and Semi-definite Programming (SDP) relaxations. Given its power, this class of algorithms seems to contain the most favourable ...

EPFL2017

Proximity Results and Faster Algorithms for Integer Programming Using the Steinitz Lemma

Graph Chatbot

Chat with Graph Search

On approximation algorithms and polyhedral relaxations for knapsack problems, and clustered planarity testing

Covering convex bodies and the Closest Vector Problem

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

Faster Algorithms for Integer Programs with Block Structure

Small Extended Formulation for Knapsack Cover Inequalities from Monotone Circuits

Robust auction design under multiple priors by linear and integer programming

Sum-Rate Capacity for Symmetric Gaussian Multiple Access Channels with Feedback

Optimal Representations for Adaptive Streaming in Interactive Multiview Video Systems

On some algebraic and extremal problems in discrete geometry

Strengths and Limitations of Linear Programming Relaxations

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

Faster Algorithms for Integer Programs with Block Structure

Optimal Representations for Adaptive Streaming in Interactive Multiview Video Systems

Sum-Rate Capacity for Symmetric Gaussian Multiple Access Channels with Feedback

On approximation algorithms and polyhedral relaxations for knapsack problems, and clustered planarity testing

Covering convex bodies and the Closest Vector Problem

Small Extended Formulation for Knapsack Cover Inequalities from Monotone Circuits

Robust auction design under multiple priors by linear and integer programming

On some algebraic and extremal problems in discrete geometry

Strengths and Limitations of Linear Programming Relaxations