Name
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. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1007/978-3-642-36694-9_3 | IPCO |
Keywords | Field | DocType |
unsplittable flow,integrality gap,unsplittable flow problem,destination vertex,constant integrality gap lp,approximation factor,stronger problem formulation,integrality gap drop,bandwidth allocation,unweighted case,core problem,maximum profit | Flow network,Discrete mathematics,Mathematical optimization,Embedding,Interval graph,Vertex (geometry),Approx,Bandwidth allocation,Computer science,Integer programming,Bounded function | Conference |
Citations | PageRank | References |
9 | 0.54 | 16 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Aris Anagnostopoulos | 1 | 1054 | 67.08 |
| Fabrizio Grandoni | 2 | 1228 | 73.72 |
| Stefano Leonardi | 3 | 411 | 28.87 |
| Andreas Wiese | 4 | 71 | 10.71 |