Publication | Closed Access
Approximation algorithms for set cover and related problems
39
Citations
0
References
1998
Year
Unknown Venue
Mathematical ProgrammingC Scover ProblemsEngineeringOptimization ProblemGreedy AlgorithmCombinatorial ProblemAlgorithmic EfficiencyComputational ComplexityNp-hard Optimization ProblemsApproximation MethodComputer ScienceApproximation AlgorithmsDiscrete MathematicsCombinatorial OptimizationDiscrete OptimizationApproximation Theory
In this thesis, we analyze several known and newly designed algorithms for approximating optimal solutions to NP-hard optimization problems. We give a new analysis of the greedy algorithm for approximating the S scET C scOVER and P scARTIAL S scET scCOVER problems obtaining significantly improved performance bounds. We also give a first approximation algorithm with a non-trivial performance bound for the E scRRAND S scCHEDULING and T scREE C scOVER problems, known also as the G scENERALIZED T scRAVELING S scALESMAN and G scROUP S scTEINER T scREE problems. The main results of this thesis first appeared in my papers (87), (89), (91), and (90); and in my technical reports (86) and (88).