Publication
Small Extended Formulation for Knapsack Cover Inequalities from Monotone Circuits
Publications associées (59)
LP-Based Algorithms For Capacitated Facility Location
Ola Nils Anders Svensson, Hyung Chan An
Linear programming (LP) has played a key role in the study of algorithms for combinatorial optimization problems. In the field of approximation algorithms, this is well illustrated by the uncapacitated facility location problem. A variety of algorithmic me ...
Society for Industrial and Applied Mathematics2017Combinatorial Algorithm for Restricted Max-Min Fair Allocation
Ola Nils Anders Svensson, Christos Kalaitzis, Chidambaram Annamalai
We study the basic allocation problem of assigning resources to players to maximize fairness. This is one of the few natural problems that enjoys the intriguing status of having a better estimation algorithm than approximation algorithm. Indeed, a certain ...
Association for Computing Machinery2017Group-Sparse Model Selection: Hardness and Relaxations
Volkan Cevher, Anastasios Kyrillidis, 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. The main promise of these models is the recovery of ``interpretable" signals along with ...
Institute of Electrical and Electronics Engineers2016Strong LP formulations for scheduling splittable jobs on unrelated machines
A natural extension of the makespan minimization problem on unrelated machines is to allow jobs to be partially processed by different machines while incurring an arbitrary setup time. In this paper we present increasingly stronger LP-relaxations for this ...
Springer Heidelberg2015A totally unimodular view of structured sparsity
Volkan Cevher, Marwa El Halabi
This paper describes a simple framework for structured sparse recovery based on convex optimization. We show that many interesting structured sparsity models can be naturally represented by linear matrix inequalities on the support of the unknown parameter ...
2015On the configuration LP for maximum budgeted allocation
Ola Nils Anders Svensson, Christos Kalaitzis, Lukas Polacek, Aleksander Madry
We study the maximum budgeted allocation problem, i.e., the problem of selling a set of m indivisible goods to n players, each with a separate budget, such that we maximize the collected revenue. Since the natural assignment LP is known to have an integral ...
Springer Heidelberg2015Local discontinuous Galerkin methods for fractional ordinary differential equations
This paper discusses the upwinded local discontinuous Galerkin methods for the one-term/multi-term fractional ordinary differential equations (FODEs). The natural upwind choice of the numerical fluxes for the initial value problem for FODEs ensures stabili ...
2015Node-weighted network design and maximum sub-determinants
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~. Then, we draw a connection to Goem ...
EPFL2014Strong LP Formulations for Scheduling Splittable Jobs on Unrelated Machines
We study a natural generalization of the problem of minimizing makespan on unrelated machines in which jobs may be split into parts. The different parts of a job can be (simultaneously) processed on different machines, but each part requires a setup time b ...
Springer2014Coding Structure and Replication Optimization for Interactive Multiview Video Streaming
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