Improved Approximation Schemes for Linear Programming Relaxations of Combinatorial Optimization Problems

DOI10.1007/11496915_7zbMath1119.90325OpenAlexW1479737148MaRDI QIDQ3596335

Vânia Eleutério, Fabián A. Chudak

Publication date: 30 August 2007

Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/11496915_7

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Linear programming (90C05) Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Discrete location and assignment (90B80)

Related Items (5)

On the Number of Iterations for Dantzig--Wolfe Optimization and Packing-Covering Approximation Algorithms ⋮ Faster and simpler approximation algorithms for mixed packing and covering problems ⋮ Nearly linear-time packing and covering LP solvers. Nearly linear-time packing and covering LP solvers, achieving width-independence and \(=(1/\varepsilon)\)-convergence ⋮ Unnamed Item ⋮ A nearly linear-time PTAS for explicit fractional packing and covering linear programs

This page was built for publication: Improved Approximation Schemes for Linear Programming Relaxations of Combinatorial Optimization Problems