Using linear programming in the design and analysis of approximation algorithms: Two illustrative problems

DOI10.1007/BFB0053960MaRDI QIDQ4400841zbMATH OpenFDO

Authors David B. Shmoys

Publication date 2 August 1998

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmslinear programming relaxationnear-optimal solutionscheduling precedence-constrained jobsuncapacitated facility location

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Discrete location and assignment (90B80) Linear programming (90C05)

Recommendations

• Approximation algorithms for facility location problems
• Improved Approximation Schemes for Linear Programming Relaxations of Combinatorial Optimization Problems
• LP-based algorithms for capacitated facility location
• Improved approximation algorithms for uncapacitated facility location

Cited in

(6)

• Approximation algorithms for shop scheduling problems with minsum objective
• Preemptive and non-preemptive generalized min sum set cover
• Solving the maximum duo-preservation string mapping problem with linear programming
• Designing PTASs for MIN-SUM scheduling problems
• Improved Approximation Schemes for Linear Programming Relaxations of Combinatorial Optimization Problems
• Finding total unimodularity in optimization problems solved by linear programs

This page was built for publication: Using linear programming in the design and analysis of approximation algorithms: Two illustrative problems

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