Show simple item record

Primal-Dual Algorithms for Combinatorial Optimization Problems

dc.contributor.advisorKhuller, Samiren_US
dc.contributor.authorMestre, Julian Diegoen_US
dc.description.abstractCombinatorial optimization problems such as routing, scheduling, covering and packing problems abound in everyday life. At a very high level, a combinatorial optimization problem amounts to finding a solution with minimum or maximum cost among a large number of feasible solutions. An algorithm for a given optimization problem is said to be exact if it always returns an optimal solution and is said to be efficient if it runs in time polynomial on the size of its input. The theory of NP-completeness suggests that exact and efficient algorithms are unlikely to exist for the class of NP-hard problems. Unfortunately, a large number of natural and interesting combinatorial optimization problems are NP-hard. One way to cope with NP-hardness is to relax the optimality requirement and instead look for solutions that are provably close to the optimum. This is the main idea behind approximation algorithms. An algorithm is said to be an r-approximation if it always returns a solution whose cost is at most an r factor away from the optimal cost. Arguably, one of the most important techniques in the design of combinatorial algorithms is the primal-dual schema in which the cost of the primal solution is compared to the cost of a dual solution. In this dissertation we study the primal-dual schema in the design of approximation algorithms for a number of covering and scheduling problems.en_US
dc.format.extent660640 bytes
dc.titlePrimal-Dual Algorithms for Combinatorial Optimization Problemsen_US
dc.contributor.publisherDigital Repository at the University of Marylanden_US
dc.contributor.publisherUniversity of Maryland (College Park, Md.)en_US
dc.contributor.departmentComputer Scienceen_US
dc.subject.pqcontrolledComputer Scienceen_US
dc.subject.pquncontrolledCombinatorial Optimizationen_US
dc.subject.pquncontrolledApproximation Algorithmsen_US
dc.subject.pquncontrolledPrimal-Dual Schemaen_US

Files in this item


This item appears in the following Collection(s)

Show simple item record