书目

The Design of Approximation Algorithms

内容简介

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.

作者简介

DavidP.WilliamsonisaProfessoratCornellUniversitywithajointappointmentintheSchoolofOperationsResearchandInformationEngineeringandintheDepartmentofInformationScience.PriortojoiningCornell,hewasaResearchStaffMemberattheIBMT.J.WatsonResearchCenterandaSeniorManagerattheIBMAlmadenResearchCenter.Hehaswonseveralawardsforhisworkonapproximationalgorithms,includingthe2000FulkersonPrize,sponsoredbytheAmericanMathematicalSocietyandtheMathematicalProgrammingSociety.Hehasservedonseveraleditorialboards,includingACMTransactionsonAlgorithms,MathematicsofOperationsResearch,theSIAMJournalonComputingandtheSIAMJournalonDiscreteMathematics.DavidShmoyshasfacultyappointmentsinboththeSchoolofOperationsResearchandInformationEngineeringandtheDepartmentofComputerScience,andheiscurrentlyAssociateDirectoroftheInstituteforComputationalSustainabilityatCornellUniversity.HeisaFellowoftheACM,wasanNSFPresidentialYoungInvestigator,andhasservedonnumerouseditorialboards,includingMathematicsofOperationsResearch(forwhichheiscurrentlyanassociateeditor),OperationsResearch,theORSAJournalonComputing,MathematicalProgrammingandboththeSIAMJournalonComputingandtheSIAMJournalonDiscreteMathematics;healsoservedaseditor-in-chiefforthelatter.

—  END  —