资源描述：
《Combinatorial Optimization》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、AlexanderSchrijverCombinatorialOptimizationPolyhedraandEciencySeptember1,2002SpringerBerlinHeidelbergNewYorkBarcelonaHongKongLondonMilanParisTokyoPrefaceThebookbyGeneLawlerfrom1976wasthe rstofaseriesofbooksallen-titled`CombinatorialOptimization',someembellishedwithasubtitle
2、:`Net-worksandMatroids',`AlgorithmsandComplexity',`TheoryandAlgorithms'.Whyaddinganotherbooktothisillustriousseries?Thejusti cationiscon-tainedinthesubtitleofthepresentbook,`PolyhedraandEciency'.ThisisshorthandforPolyhedralCombinatoricsandEcientAlgorithms.Pioneeredbythewor
3、kofJackEdmonds,polyhedralcombinatoricshasprovedtobeamostpowerful,coherent,andunifyingtoolthroughoutcom-binatorialoptimization.Notonlyithasledtoecient(thatis,polynomial-time)algorithms,butalso,conversely,ecientalgorithmsoftenimplypoly-hedralcharacterizationsandrelatedmin-ma
4、xrelations.Itmakesthetwosidescloselyintertwined.Weaimato eringbothanintroductiontoandanin-depthsurveyofpoly-hedralcombinatoricsandecientalgorithms.Withinthespanofpolyhedralmethods,wetrytopresentabroadpictureofpolynomial-timesolvablecom-binatorialoptimizationproblems
5、morepre
6、cisely,ofthoseproblemsthathavebeenprovedtobepolynomial-timesolvable.Nexttothat,wegointoafewprominentNP-completeproblemswherepolyhedralmethodsweresuc-cesfulinobtaininggoodboundsandapproximations,likethestablesetandthetravelingsalesmanproblem.Nevertheless,whileweobviouslyhopet
7、hatthequestionNP=P?"willbesettledsoononewayortheother,werealizethatintheastonishingeventthatNP=Pwillbeproved,thisbookwillbehighlyincomplete.Byde nition,beinginPmeansbeingsolvablebya`deterministicse-quentialpolynomial-time'algorithm,andinourdiscussionsofalgorithmsandcomplexi
8、tywerestrictourselvesmainlytothischaracteristic.Asaconse-quence,wedonotcover(butyetoccasionallytouchoroutline)theimportantworkonapproximative,randomized,andparallelalgorithmsandcomplex-ity,areasthatarerecentlyinexcitingmotion.Wealsoneglectapplications,modelling,andcomputatio
9、nalmethodsforNP-completeproblems.Advanceddatastructuresaretreatedonlymodera
