@inproceedings{5b86daa18b8a4716b31d2e74beba8463,

title = "Near-linear time approximation schemes for some implicit fractional packing problems",

abstract = "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.",

author = "Chandra Chekuri and Kent Quanrud",

note = "Publisher Copyright: Copyright {\textcopyright} by SIAM.; 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017 ; Conference date: 16-01-2017 Through 19-01-2017",

year = "2017",

doi = "10.1137/1.9781611974782.51",

language = "English (US)",

series = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",

publisher = "Association for Computing Machinery",

pages = "801--820",

editor = "Klein, {Philip N.}",

booktitle = "28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017",

address = "United States",

}