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

Chandra Chekuri, Kent Quanrud

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publication28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017
EditorsPhilip N. Klein
PublisherAssociation for Computing Machinery
Pages801-820
Number of pages20
ISBN (Electronic)9781611974782
DOIs
StatePublished - 2017
Event28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017 - Barcelona, Spain
Duration: Jan 16 2017Jan 19 2017

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume0

Conference

Conference28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017
CountrySpain
CityBarcelona
Period1/16/171/19/17

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Near-linear time approximation schemes for some implicit fractional packing problems'. Together they form a unique fingerprint.

Cite this