The Unsplittable Flow Problem on a Path (UFPP) is a core problem in many important settings such as network flows, bandwidth allocation, resource constraint scheduling, and interval packing. We are given a path with capacities on the edges and a set of tasks, each task having a demand, a profit, a source and a destination vertex on the path. The goal is to compute a subset of tasks of maximum profit that does not violate the edge capacities. In practical applications generic approaches such as integer programming (IP) methods are desirable. Unfortunately, no IP-formulation is known for the problem whose LP-relaxation has an integrality gap that is provably constant. For the unweighted case, we show that adding a few constraints to the standard LP of the problem is sufficient to make the integrality gap drop from Ω(n) to O(1). This positively answers an open question in [Chekuri et al., APPROX 2009]. For the general (weighted) case, we present an extended formulation with integrality gap bounded by 7 + ε. This matches the best known approximation factor for the problem [Bonsma et al., FOCS 2011]. This result exploits crucially a technique for embedding dynamic programs into linear programs. We believe that this method could be useful to strengthen LP-formulations for other problems as well and might eventually speed up computations due to stronger problem formulations. © 2013 Springer-Verlag.
Constant integrality gap LP formulations of unsplittable flow on a path / Anagnostopoulos, Aristidis; Fabrizio, Grandoni; Leonardi, Stefano; Wiese, Andreas. - 7801 LNCS:(2013), pp. 25-36. (Intervento presentato al convegno 16th Conference on Integer Programming and Combinatorial Optimization, IPCO 2013 tenutosi a Valparaiso nel 18 March 2013 through 20 March 2013) [10.1007/978-3-642-36694-9_3].
Constant integrality gap LP formulations of unsplittable flow on a path
ANAGNOSTOPOULOS, ARISTIDIS;LEONARDI, Stefano;
2013
Abstract
The Unsplittable Flow Problem on a Path (UFPP) is a core problem in many important settings such as network flows, bandwidth allocation, resource constraint scheduling, and interval packing. We are given a path with capacities on the edges and a set of tasks, each task having a demand, a profit, a source and a destination vertex on the path. The goal is to compute a subset of tasks of maximum profit that does not violate the edge capacities. In practical applications generic approaches such as integer programming (IP) methods are desirable. Unfortunately, no IP-formulation is known for the problem whose LP-relaxation has an integrality gap that is provably constant. For the unweighted case, we show that adding a few constraints to the standard LP of the problem is sufficient to make the integrality gap drop from Ω(n) to O(1). This positively answers an open question in [Chekuri et al., APPROX 2009]. For the general (weighted) case, we present an extended formulation with integrality gap bounded by 7 + ε. This matches the best known approximation factor for the problem [Bonsma et al., FOCS 2011]. This result exploits crucially a technique for embedding dynamic programs into linear programs. We believe that this method could be useful to strengthen LP-formulations for other problems as well and might eventually speed up computations due to stronger problem formulations. © 2013 Springer-Verlag.File | Dimensione | Formato | |
---|---|---|---|
VE_2013_11573-515816.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
299.84 kB
Formato
Adobe PDF
|
299.84 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.