TheDesignofApproximationAlgorithms

Discrete optimization problems are ubiquitous - they appear in traditional operations research planning (scheduling, facility location, and network design), computer science databases, as well as advertising issues in viral marketing. However, the majority of these problems are NP-hard, meaning there are no efficient algorithms to find optimal solutions unless P = NP. This book presents how to design approximation algorithms to solve these challenging problems.

作者简介

Discreteoptimizationproblemsareeverywhere,fromtraditionaloperationsresearchplanning(scheduling,facilitylocationandnetworkdesign);tocomputersciencedatabases;toadvertisingissuesinviralmarketing.YetmostsuchproblemsareNP-hard;unlessP=NP,therearenoefficientalgorithmstofindoptimalsolutions.Thisbookshowshowtodesignapproximationalgorithms:efficientalgorithmsthatfindprovablynear-optimalsolutions.Thebookisorganizedaroundcentralalgorithmictechniquesfordesigningapproximationalgorithms,includinggreedyandlocalsearchalgorithms,dynamicprogramming,linearandsemidefiniteprogramming,andrandomization.Eachchapterinthefirstsectionisdevotedtoasinglealgorithmictechniqueappliedtoseveraldifferentproblems,withmoresophisticatedtreatmentinthesecondsection.Thebookalsocoversmethodsforprovingthatoptimizationproblemsarehardtoapproximate.Designedasatextbookforgraduate-levelalgorithmcourses,itwillalsoserveasareferenceforresearchersinterestedintheheuristicsolutionofdiscreteoptimizationproblems.