A fast approximation scheme for fractional covering problems with variable upper bounds

MaRDI QIDQ5501364zbMATH OpenFDO

Authors Lisa Fleischer

Publication date 3 August 2015

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Linear programming (90C05) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• scientific article; zbMATH DE number 1003253
• Fast Approximation Algorithms for Fractional Packing and Covering Problems
• scientific article; zbMATH DE number 1003254
• Approximating Fractional Packings and Coverings in O(1/epsilon) Iterations
• Fast Approximation Algorithms for the Generalized Survivable Network Design Problem

Cited in

(7)

• An approximation algorithm for the general max-min resource sharing problem
• Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems
• Covering linear programming with violations
• Improved Approximation Schemes for Linear Programming Relaxations of Combinatorial Optimization Problems
• Algorithms – ESA 2004
• A faster algorithm for constrained correlation clustering
• Faster and simpler approximation algorithms for mixed packing and covering problems

This page was built for publication: A fast approximation scheme for fractional covering problems with variable upper bounds

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