Combinatorial approximation algorithms: a comparative review

DOI10.1016/j.orl.2004.03.010zbMath1213.00027OpenAlexW2054416551MaRDI QIDQ2488226

Gerhard J. Woeginger

Publication date: 25 August 2005

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2004.03.010

zbMATH Keywords

combinatorial optimizationapproximation algorithmperformance guarantee

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) External book reviews (00A17)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A threshold of ln n for approximating set cover
• Short Shop Schedules