近似算法的设计与分析（英文版）.pdf-资料库

fake718-7902283-4744302542934064546.pdf-第1页.png

第1页 / 共453页

fake718-7902283-4744302542934064546.pdf-第2页.png

第2页 / 共453页

fake718-7902283-4744302542934064546.pdf-第3页.png

第3页 / 共453页

fake718-7902283-4744302542934064546.pdf-第4页.png

第4页 / 共453页

fake718-7902283-4744302542934064546.pdf-第5页.png

第5页 / 共453页

fake718-7902283-4744302542934064546.pdf-第6页.png

第6页 / 共453页

fake718-7902283-4744302542934064546.pdf-第7页.png

第7页 / 共453页

fake718-7902283-4744302542934064546.pdf-第8页.png

第8页 / 共453页

Springer Optimization and Its Applications VOLUME 62 Managing Editor Panos M. Pardalos (University of Florida) Editor–Combinatorial Optimization Ding-Zhu Du (University of Texas at Dallas) Advisory Board J. Birge (University of Chicago) C.A. Floudas (Princeton University) F. Giannessi (University of Pisa) H.D. Sherali (Virginia Polytechnic and State University) T. Terlaky (McMaster University) Y. Ye (Stanford University) Aims and Scope Optimization has been expanding in all directions at an astonishing rate during the last few decades. New algorithmic and theoretical techniques have been developed, the diffusion into other disciplines has proceeded at a rapid pace, and our knowledge of all aspects of the ﬁeld has grown even more profound. At the same time, one of the most striking trends in opti- mization is the constantly increasing emphasis on the interdisciplinary na- ture of the ﬁeld. Optimization has been a basic tool in all areas of applied mathematics, engineering, medicine, economics, and other sciences. The series Springer Optimization and Its Applications publishes under- graduate and graduate textbooks, monographs and state-of-the-art exposi- tory work that focus on algorithms for solving optimization problems and also study applications involving such problems. Some of the topics covered include nonlinear optimization (convex and nonconvex), network ﬂow prob- lems, stochastic optimization, optimal control, discrete optimization, multi- objective programming, description of software packages, approximation techniques and heuristic approaches. For further volumes: http://www.springer.com/series/7393

Ding-Zhu Du •Ker-I KoDesign and Analysisof Approximation AlgorithmsXiaodong Hu•

Ding-Zhu Du Ker-I Ko Department of Computer Science Department of Computer Science University of Texas at Dallas State University of New York at Stony Brook Richardson, TX 75080 Stony Brook, NY 11794 USA USA dzdu@utdallas.edu keriko@cs.sunysb.edu Xiaodong Hu Institute of Applied Mathematics Academy of Mathematics and Systems Science Chinese Academy of Sciences Beijing 100190 China xdhu@amss.ac.cn ISSN 1931-6828 ISBN 978-1-4614-1700-2 e-ISBN 978-1-4614-1701-9 DOI 10.1007/978-1-4614-1701-9 Springer New York Dordrecht Heidelberg London Library of Congress Control Number: Springer Science+Business Media, LLC 2012 All rights reserved. This work may not be translated or copied in whole or in part without the written permission of the publisher (Springer Science+Business Media, LLC, 233 Spring Street, New York, NY 10013, USA), except for brief excerpts in connection with reviews or scholarly analysis. Use in connection with any form of information storage and retrieval, electronic adaptation, computer soft-ware, or by similar or dissimilar methodology now known or hereafter developed is forbidden. The use in this publication of trade names, trademarks, service marks, and similar terms, even if they are not identified as such, is not to be taken as an expression of opinion as to whether or not they are subject to proprietary rights. Printed on acid-free paper Springer is part of Springer Science+Business Media (www.springer.com) 2011942512

PrefaceAnapproximationalgorithmisanefﬁcientalgorithmthatproducessolutionstoanoptimizationproblemthatareguaranteedtobewithinaﬁxedratiooftheoptimalsolution.Insteadofspendinganexponentialamountoftimeﬁndingtheoptimalsolution,anapproximationalgorithmsettlesfornear-optimalsolutionswithinpoly-nomialtimeintheinputsize.Approximationalgorithmshavebeenstudiedsincethemid-1960s.Theirimportancewas,however,notfullyunderstooduntilthediscov-eryoftheNP-completenesstheory.Manywell-knownoptimizationproblemshavebeenproved,underreasonableassumptionsinthistheory,tobeintractable,inthesensethatoptimalsolutionstotheseproblemsarenotcomputablewithinpolyno-mialtime.Asaconsequence,near-optimalapproximationalgorithmsarethebestonecanexpectwhentryingtosolvetheseproblems.Inthepastdecade,theareaofapproximationalgorithmshasexperiencedanex-plosiverateofgrowth.Thisgrowthrateispartlyduetothedevelopmentofrelatedresearchareas,suchasdatamining,communicationnetworks,bioinformatics,andcomputationalgametheory.Thesenewlyestablishedresearchareasgeneratealargenumberofnew,intractableoptimizationproblems,mostofwhichhavedirectappli-cationstoreal-worldproblems,andsoefﬁcientapproximatesolutionstothemareactivelysoughtafter.Inadditiontotheexternal,practicalneedforefﬁcientapproximationalgorithms,thereisalsoanintrinsic,theoreticalmotivebehindtheresearchofapproximationalgorithms.Inthedesignofanexact-solutionalgorithm,themain,andoftenonly,measureofthealgorithm’sperformanceisitsrunningtime.Thisﬁxedmeasureof-tenlimitsourchoiceoftechniquesinthealgorithm’sdesign.Foranapproximationalgorithm,however,thereisanequallyimportantsecondmeasure,thatis,theper-formanceratioofthealgorithm,whichmeasureshowclosetheapproximational-v

viPrefacegorithm’soutputistotheoptimalsolution.Thismeasureaddsanewdimensiontothedesignandanalysisofapproximationalgorithms.Namely,wecannowstudythetradeoffbetweentherunningtimeandtheperformanceratioofapproximationalgo-rithms,andapplydifferentdesigntechniquestoachievedifferenttradeoffsbetweenthesetwomeasures.Inaddition,newtheoreticalissuesabouttheapproximationtoanoptimizationproblemneedtobeaddressed:Whatistheperformanceratioofanapproximationalgorithmforthisproblembasedoncertaintypesofdesignstrategy?Whatisthebestperformanceratioofanypolynomial-timeapproximationalgorithmforthisproblem?Doestheproblemhaveapolynomial-timeapproximationschemeorafullypolynomial-timeapproximationscheme?Thesequestionsarenotonlyofsigniﬁcanceinpracticeforthedesignofapproximationalgorithms;theyarealsoofgreattheoreticalinterest,withintriguingconnectionstotheNP-completenessthe-ory.Motivatedbythesetheoreticalquestionsandthegreatnumberofnewlydiscov-eredoptimizationproblems,peoplehavedevelopedmanynewdesigntechniquesforapproximationalgorithms,includingthegreedystrategy,therestrictionmethod,therelaxationmethod,partition,localsearch,powergraphs,andlinearandsemidef-initeprogramming.Acomprehensivesurveyofallthesemethodsandresultsinasinglebookisnotpossible.Weinsteadprovideinthisbookanintensivestudyofthemainmethods,withabundantapplicationsfollowingourdiscussionofeachmethod.Indeed,thisbookisorganizedaccordingtodesignmethodsinsteadofapplicationproblems.Thus,onecanstudyapproximationalgorithmsofthesamenatureto-gether,andlearnaboutthedesigntechniquesinamoreuniﬁedway.Tothisend,thebookisarrangedinthefollowingway:First,inChapter1,wegiveabriefintroduc-tiontotheconceptofNP-completenessandapproximationalgorithms.InChapter2,wegiveanin-depthanalysisofthegreedystrategy,includinggreedyalgorithmswithsubmodularpotentialfunctionsandthosewithnonsubmodularpotentialfunc-tions.InChapters3,4,and5,wecovervariousrestrictionmethods,includingpar-titionandGuillotinecutmethods,withapplicationstomanygeometricproblems.Inthenextfourchapters,westudytherelaxationmethods.InadditiontoageneraldiscussionoftherelaxationmethodinChapter6,wedevotethreechapterstoap-proximationalgorithmsbasedonlinearandsemideﬁniteprogramming,includingtheprimal-dualschemaanditsequivalencewiththelocalratiomethod.Finally,inChapter10,wepresentvariousinapproximabilityresultsbasedonrecentworkintheNP-completenesstheory.Anumberofexamplesandexercisesareprovidedforeachdesigntechnique.Theyaredrawnfromdiverseareasofresearch,includingcommunicationnetworkdesign,opticalnetworks,wirelessadhocnetworks,sensornetworks,bioinformatics,socialnetworks,industrialengineering,andinformationmanagementsystems.ThisbookhasgrownoutoflecturenotesusedbytheauthorsattheUniversityofMinnesota,UniversityofTexasatDallas,TsinghuaUniversity,GraduateSchoolofChineseAcademyofSciences,Xi’anJiaotongUniversity,ZhejiangUniversity,EastChinaNormalUniversity,DalianUniversityofTechnology,XinjiangUniver-sity,NankaiUniversity,LanzhouJiaotongUniversity,XidianUniversity,andHarbinInstituteofTechnology.Inatypicalone-semesterclassforﬁrst-yeargraduatestu-

Prefaceviidents,onemaycovertheﬁrsttwochapters,oneortwochaptersontherestrictionmethod,twoorthreechaptersontherelaxationmethod,andChapter10.Withmoreadvancedstudents,onemayalsoteachaseminarcoursefocusingononeofthegreedy,restriction,orrelaxationmethods,basedonthecorrespondingchaptersofthisbookandsupplementarymaterialfromrecentresearchpapers.Forinstance,aseminaroncombinatorialoptimizationemphasizingapproximationsbasedonlinearandsemideﬁniteprogrammingcanbeorganizedusingChapters7,8,and9.Thisbookhasbeneﬁtedmuchfromthehelpofourfriends,colleagues,andstu-dents.WeareindebtedtoPeng-JunWan,WeiliWu,XiuzhenCheng,JieWang,Yin-fengXu,ZhaoZhang,DeyingLi,HejiaoHuang,HongZhu,GuochuanZhang,WeiWang,ShugangGao,XiaofengGao,FengZou,LingDing,XianyueLi,MyT.Thai,DonghyunKim,J.K.Willson,andRoozbehEbrahimiSoorchaei,whomademuch-valuedsuggestionsandcorrectionstotheearlierdraftsofthebook.WearealsogratefultoProfessorsFrancesYao,RichardKarp,RonaldGraham,andFanChungfortheirencouragement.SpecialthanksareduetoProfessorAndrewYaoandtheInstituteforTheoreticalComputerScience,TsinghuaUniversity,forthegeneroussupportandstimulatingenvironmenttheyprovidedfortheﬁrsttwoauthorsduringtheirnumerousvisitstoTsinghuaUniversity.Dallas,TexasDing-ZhuDuStonyBrook,NewYorkKer-IKoBeijing,ChinaXiaodongHuAugust2011

资料库

近似算法的设计与分析（英文版）.pdf

相关推荐

课程资源

热门标签

最新资料