@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",
}