TY - GEN

T1 - Near-linear time approximation schemes for some implicit fractional packing problems

AU - Chekuri, Chandra

AU - Quanrud, Kent

N1 - Funding Information:
Department of Computer Science, University of Illinois, Urbana, IL 61820. {chekuri,quanrud2}@Illinois.edu. Work on this paper partially supported by NSF grant CCF-1526799.

PY - 2017

Y1 - 2017

N2 - We consider several implicit fractional packing problems and obtain faster implementations of approximation schemes based on multiplicative-weight updates. This leads to new algorithms with near-linear running times for some fundamental problems in combinatorial optimization. We highlight two concrete applications. The first is to find the maximum fractional packing of spanning trees in a capacitated graph; we obtain a (1)-approximation in O time, where m is the number of edges in the graph. Second, we consider the LP relaxation of the weighted unsplittable flow problem on a path and obtain a (1)-approximation in O time, where n is the number of demands.

AB - We consider several implicit fractional packing problems and obtain faster implementations of approximation schemes based on multiplicative-weight updates. This leads to new algorithms with near-linear running times for some fundamental problems in combinatorial optimization. We highlight two concrete applications. The first is to find the maximum fractional packing of spanning trees in a capacitated graph; we obtain a (1)-approximation in O time, where m is the number of edges in the graph. Second, we consider the LP relaxation of the weighted unsplittable flow problem on a path and obtain a (1)-approximation in O time, where n is the number of demands.

UR - http://www.scopus.com/inward/record.url?scp=85016203944&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85016203944&partnerID=8YFLogxK

U2 - 10.1137/1.9781611974782.51

DO - 10.1137/1.9781611974782.51

M3 - Conference contribution

AN - SCOPUS:85016203944

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 801

EP - 820

BT - 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017

A2 - Klein, Philip N.

PB - Association for Computing Machinery

T2 - 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017

Y2 - 16 January 2017 through 19 January 2017

ER -