Constant Integrality Gap LP Formulations of Unsplittable Flow on a Path

详细信息    查看全文

• 作者：Aris Anagnostopoulos (18)
  Fabrizio Grandoni (19)
  Stefano Leonardi (18)
  Andreas Wiese (20)
  
• 刊名：Lecture Notes in Computer Science
• 出版年：2013
• 出版时间：2013
• 年：2013
• 卷：7801
• 期：1
• 页码：37-48
• 全文大小：300KB
• 参考文献：1. Bansal, N., Chakrabarti, A., Epstein, A., Schieber, B.: A quasi-PTAS for unsplittable flow on line graphs. In: STOC, pp. 721-29 (2006)
  2. Bansal, N., Friggstad, Z., Khandekar, R., Salavatipour, R.: A logarithmic approximation for unsplittable flow on line graphs. In: SODA, pp. 702-09 (2009)
  3. Bar-Noy, A., Bar-Yehuda, R., Freund, A., Naor, J., Schieber, B.: A unified approach to approximating resource allocation and scheduling. In: STOC, pp. 735-44 (2000)
  4. Berman, P., DasGupta, B., Muthukrishnan, S., Ramaswami, S.: Improved approximation algorithms for rectangle tiling and packing. In: SODA, pp. 427-36 (2001)
  5. Bonsma, P., Schulz, J., Wiese, A.: A constant factor approximation algorithm for unsplittable flow on paths. In: FOCS, pp. 47-6 (2011)
  6. Calinescu, G., Chakrabarti, A., Karloff, H., Rabani, Y.: Improved Approximation Algorithms for Resource Allocation. In: Cook, W.J., Schulz, A.S. (eds.) IPCO 2002. LNCS, vol.?2337, pp. 401-14. Springer, Heidelberg (2002) CrossRef
  7. Chakrabarti, A., Chekuri, C., Gupta, A., Kumar, A.: Approximation algorithms for the unsplittable flow problem. Algorithmica, 53-8 (2007)
  8. Chalermsook, P., Chuzhoy, J.: Maximum independent set of rectangles. In: SODA, pp. 892-01 (2009)
  9. Chekuri, C., Ene, A., Korula, N.: Unsplittable flow in paths and trees and column-restricted packing integer programs, unpublished, http://web.engr.illinois.edu/~ene1/papers/ufp-full.pdf
  10. Chekuri, C., Ene, A., Korula, N.: Unsplittable Flow in Paths and Trees and Column-Restricted Packing Integer Programs. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) APPROX 2009. LNCS, vol.?5687, pp. 42-5. Springer, Heidelberg (2009) CrossRef
  11. Chekuri, C., Mydlarz, M., Shepherd, F.: Multicommodity demand flow in a tree and packing integer programs. ACM Trans. on Algorithms?3 (2007)
  12. Chrobak, M., Woeginger, G.J., Makino, K., Xu, H.: Caching Is Hard -Even in the Fault Model. In: de Berg, M., Meyer, U. (eds.) ESA 2010, Part I. LNCS, vol.?6346, pp. 195-06. Springer, Heidelberg (2010) CrossRef
  13. Darmann, A., Pferschy, U., Schauer, J.: Resource allocation with time intervals. Theor. Comp. Sc.?411, 4217-234 (2010) CrossRef
  14. Frieze, A.M., Clarke, M.R.B.: Approximation algorithms for the / m-dimensional 0??- knapsack problem: worst-case and probabilistic analyses. European J. Oper. Res.?15, 100-09 (1984) CrossRef
  15. Khanna, S., Muthukrishnan, S., Paterson, M.: On approximating rectangle tiling and packing. In: SODA, pp. 384-93 (1998)
  16. Kipp Martin, R., Rardin, R.L., Campbell, B.A.: Polyhedral characterization of discrete dynamic programming. Oper. Res.?38(1), 127-38 (1990) CrossRef
  17. Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Springer, Berlin (2003)
  
• 作者单位：Aris Anagnostopoulos (18)
  Fabrizio Grandoni (19)
  Stefano Leonardi (18)
  Andreas Wiese (20)
  
  18. Sapienza University of Rome, Italy
  19. University of Lugano, Switzerland
  20. Max-Planck-Institut für Informatik, Germany
  
• ISSN：1611-3349

文摘

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--em class="a-plus-plus">ε. 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.