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

DOI10.1137/1.9781611974782.51MaRDI QIDQ4575789zbMATH OpenOpenAlexFDO

Authors Chandra Chekuri, Kent Quanrud

Publication date 16 July 2018

Published in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611974782.51

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Faster approximation schemes for fractional multicommodity flow problems
• Approximating Fractional Packings and Coverings in O(1/epsilon) Iterations
• Fast Approximation Algorithms for Fractional Packing and Covering Problems
• Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms
• A nearly linear-time PTAS for explicit fractional packing and covering linear programs

Cited in

(8)

• A simple method for convex optimization in the oracle model
• LP relaxation and tree packing for minimum k-cut
• scientific article; zbMATH DE number 2163022 (Why is no real title available?)
• Fast and deterministic approximations for \(k\)-cut
• Time-expanded packings
• Fast and Deterministic Approximations for k-Cut.
• A simple method for convex optimization in the oracle model
• A generalized approximation framework for fractional network flow and packing problems

This page was built for publication: Near-linear time approximation schemes for some implicit fractional packing problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575789)