NP难解问题的近似算法

Introduction
DoritS.Hochbaum
0.1Whatcanapproximationalgorithmsdoforyou:anillustrativeexample
0.2Fundamentalsandconcepts
0.3Objectivesandorganizationofthisbook
0.4Acknowledgments
IApproximationAlgorithmsforScheduling
LeslieA.Hall
1.1Introduction
1.2SequencingwithReleaseDatestoMinimizeLateness
1.2.1Jackson'srule
1.2.2Asimple3/2-approximationalgorithm
1.2.3Apolynomialapproximationscheme
1.2.4Precedenceconstraintsandpreprocessing
1.3Identicalparallelmachines:beyondlistscheduling
1.3.1P|rj,prec|Lmax::listschedulingrevisited
1.3.2TheLPTruleforP‖Cmax
1.3.3TheLPTruleforP|rj|Cmax
1.3.4Otherresultsforidenticalparallelmachines
1.4Unrelatedparallelmachines
1.4.1A2-approximationalgorithmbasedonlinearprogramming
1.4.2Anapproximationalgorithmforminimizingcostandmakespan
1.4.3Arelatedresultfromnetworkscheduling
1.5Shopscheduling
1.5.1Agreedy2-approximationalgorithmforopenshops
1.5.2Analgorithmwithanabsoluteerrorbound
1.5.3A(2+E)-approximationalgorithmforfixedjobandflowshops
1.5.4Thegeneraljobshop:unit-timeoperations
1.6Lowerboundsonapproximationformakespanscheduling
1.6.1Identicalparallelmachinesandprecedenceconstraints
1.6.2Unrelatedparallelmachines
1.6.3Shopscheduling
1.7Min-sumobjectives
1.7.1Sequencingwithreleasedatestominimizesumof
completiontimes
1.7.2Sequencingwithprecedenceconstraints
1.7.3Unrelatedparallelmachines
1.8Finalremarks
2ApproximationAlgorithmsforBinPacking:ASurvey
E.G.Coffman,Jr.,M.R.Garey,andD.S.Johnson
2.1Introduction
2.2Worst-caseanalysis
2.2.1Nextfit
2.2.2Firstfit
2.2.3Bestfit,worstfit,andalmostanyfitalgorithms
2.2.4Bounded-spaceonlinealgorithms
2.2.5Arbitraryonlinealgorithms
2.2.6Semi-onlinealgorithms
2.2.7Firstfitdecreasingandbestfitdecreasing
2.2.8Othersimpleofflinealgorithms
2.2.9Special-caseoptimality,approximationschemes,and
asymptoticallyoptimalalgorithms
2.2.10Otherworst-casequestions
2.3Average-caseanalysis
2.3.1Bounded-spaceonlinealgorithms
2.3.2Arbitraryonlinealgorithms
2.3.3Offiinealgorithms
2.3.4Otheraverage-casequestions
2.4Conclusion
ApproximatingCoveringandPackingProblems:SetCover,VertexCover,
IndependentSet,andRelatedProblems
DoritS.Hachbaum
3.1Introduction
3.1.1Definitions,formulationsandapplications
3.1.2Lowerboundsonapproximations
3.1.3Overviewofchapter
3.2Thegreedyalgorithmforthesetcoverproblem
3.3TheLP-algorithmforsetcover
3.4Thefeasibledualapproach
3.5Usingotherrelaxationstoderivedualfeasiblesolutions
3.6Approximatingthemulticoverproblem
3.7Theoptimaldualapproachforthevertexcoverandindependent
setproblems:preprocessing
3.7.1ThecomplexityoftheLP-relaxationofvertexcoverand
independentset
3.7.2Easilycolorablegraphs
3.7.3Agreedyalgorithmforindependentsetinunweightedgraphs
3.7.4Alocal-ratiotheoremandsubgraphremoval
3.7.5Additionalalgorithmswithoutpreprocessing
3.7.6Summaryofapproximationsforvertexcoverand
independentset
3.8Integerprogrammingwithtwovariablesperinequality
3.8.1Thehalfintegralityandthelinearprogrammingrelaxation
3.8.2Computingallapproximatesolution
3.8.3TheequivalenceofIP2to2-SATand2-SATtovertexcover
3.8.4Propertiesofbinaryintegerprograms
3.8.5DualfeasiblesolutionsforIP2
3.9Themaximumcoverageproblemandthegreedy
3.9.1Tilegreedyapproach
3.9.2Applicationsofthemaxinmumcoverageproblem
4ThePrimal-DualMethudforApproximationAlgorithmsand
ItsApplicatiuntoNetworkDesignProblems
MichelX.GoemansandDavidP.Williamson
4.1Introduction
4.2Theclassicalprimal-dualmethod
4.3Thcprimal-dualmethodI'm'approximationalgorithms
4.4Amodelofnetworkdesignproblems
4.4.10-Ifunctions
4.5Downwardsmonotonefunctions
4.5.1Theedge-coveringproblem
4.5.2Lowercapacitatedpartitioningproblems
4.5.3Location-designandlocation-routingproblems
4.5.4ProofofTheorems4.5and4.6
4.60-1properfunctions
4.6.1ThegeneralizedSternertreeproblem
4.6.2TheT-joinproblem
4.6.3Theminimum-weightperfectmatchingproblem
4.6.4Point-to-pointconnectionproblems
4.6.5Exactpartitioningproblems
4.7Generalproperfunctions
4.8Extensions
4.8.1Mininmmmulticutintrees
4.8.2Theprize-collectingproblems
4.8.3Vertexconnectivityproblems
4.9Conclusions
5CutProblemsandTheirApplicationtoDivide-and-Conquer
DavidB.Shmoys
5.1Introduction
5.2Minimummulticutsandmaximummulticommodityflow
5.2.1Multicuts,maximummulticommodityflow,and
aweakdualitytheorem
5.2.2Fractionalmulticuts,pipesystems,andastrongdualitytheorem
5.2.3Solvingthelinearprograms
5.2.4Findingagoodmulticut
5.3Sparsestcutsandmaximumconcurrentflow
5.3.1Thesparsestcutproblem
5.3.2Reducingthesparsestcutproblemtotheminimummulticut
problem
5.3.3Embeddingsandthesparsestcutproblem
5.3.4Findingagoodembedding
5.3.5Themaximumconcurrentflowproblem
5.4Minimumfeedbackarcsetsandrelatedproblems
5.4.1AnLP-basedapproximationalgorithm
5.4.2AnalyzingthealgorithmFeedback
5.4.3Findingagoodpartition
5.5Findingbalancedcutsandotherapplications
5.5.1Findingbalancedcuts
5.5.2Applicationsofbalancedcuttheorems
5.6Conclusions
ApproximationAlgorithmsforFindingHighlyConnectedSuhgraphs
SamirKhulJer
6.1Introduction
6.1.1Outlineofchapterandtechniques
6.2Edge-connectivityproblems
6.2.1Weightededge-connectivity
6.2.2Unweightededge-connectivity
6.3Vertex-connectivityproblems
6.3.1Weightedvertex-connectivity
6.3.2Unweightedvertex-connectivity
6.4Strong-connectivityproblems
6.4.1Polynomialtimeapproximationalgorithms
6.4.2Nearlylinear-timeimplementation
6.5Connectivityaugmentation
6.5.1increasingedgeconnectivityfromIto2
6.5.2IncreasingvertexconnectivityfromIto2
6.5.3Increasingedge-connectivityto3.
AlgorithmsforFindingLowDegreeStructures
BalajiRaghavachari
7.1Introduction
7.2Toughnessanddegree
7.3MatchingsandMDST
7.4MDSTwithinoneofoptimal
7.4.1Witnesssets
7.4.2The△*+1algorithm
7.4.3Performanceanalysis
7.5Localsearchtechniques
7.5.1MDSTproblem
7.5.2Constrainedforestproblems
7.5.3Two-connectedsubgraphs
7.6Problemswithedgeweights-pointsinEuclideanspaces
7.7Openproblems
8ApproximationAlgorithmsforGeometricProblems
MarshallBernandDavidEppstein
8.1Introduction
8.1.1Overviewoftopics
8.1.2Specialnatureofgeometricproblems
8.2Travelingsalesmanproblem
8.2.1Christofides'algorithm
8.2.2Heuristics
8.2.3TSPwithneighborhoods
8.3Steinertreeproblem
8.3.1Steinerratios
8.3.2Betterapproximations
8.4Minimumweighttriangulation
8.4.1TriangulationwithoutSteinerpoints
8.4.2Steinertriangulation
8.5Clustering
8.5.1Minmaxk-clustering
8.5.2k-minimumspanningtree
8.6Separationproblems
8.6.1Polygonseparation
8.6.2Polyhedronseparation
8.6.3Pointsetseparation
8.7Oddsandends
8.7.1Coveringorthogonalpolygonsbyrectangles
8.7.2Packingsquareswithfixedcomers
8.7.3Largestcongruentsubsets
8.7.4Polygonbisection
8.7.5Graphembedding
8.7.6Low-degreespanningtrees
8.7.7Shortestpathsinspace
8.7.8Longestsubgraphproblems
8.8Conclusions
9VariousNotionsofApproximations:Good,Better,Best,andMore
DoritS.Hochbaum
9.1Introduction
9.1.1Overviewofchapter
9.2Good:fixedconstantapproximations
9.2.1Theweightedundirectedvertexfeedbacksetproblem
9.2.2Theshortestsuperstringproblem
9.2.3Howmaximizationversusminimizationaffectsapproximations
9.3Better:approximationschemes
9.3.1Afullypolynomialapproximationschemeforthe
knapsackproblem
9.3.2Theminimummakespanandthetechniqueof
dualapproximations
9.3.3Geometricpackingandcovering--theshiftingtechnique
9.4Best:unlessNP=P
9.4.1Thek-centerproblem
9.4.2Apowerfulapproximationtechniqueforbottleneckproblems
9.4.3Bestpossibleparallelapproximationalgorithms
9.5Betterthanbest
9.5.1AFPASforbinpacking
9.5.2A9/8-approximationalgorithmfor~dgecoloringofmultigraphs
andbeyond
9.6Wonderful:withinoneunitofoptimum
10HardnessofApproximations
SanjeerAroraandCarstenLund
10.1Introduction
10.2Howtoproveinapproximabilityresults
10.2.1Thecanonicalproblems
10.2.2Inapproximabilityresultsforthecanonicalproblems
10.2.3Gappreservingreductions
10.3InapproximabilityresultsforproblemsinclassI
10.3.1Max-SNP
10.4InapproximabilityresultsforproblemsinclassII
10.4.1SETCOVER
10.5Inapproximabilityresultslorproblemsinclass111
10.5.1LABELCOVER(maximizationversion),.
10.5.2LABELCOVER(mtnversion)
10.5.3Nearestlatticevectorproblem
10.6InapproximabilityresultsforproblemsinclassIV
10.6.1CLIQUE
10.6.2COLORING
10.7Inapproximabilityresultsataglance
10.7.1Howtoproveotherhardnessresults:acasestudy
10.8prohabilisticallycheckableproofsandinapproximability
10.8.1ThePCPtheorem
10.8.2ConnectiontoinapproximabilityofMAX-3SAT
10.8.3Wherethegapcomesfrom
10.9Openproblems
10.10Chapternotes
11RandomizedApproximationAlgorithmsinCombinatorialOptimization
RajeevMotwani,Joseph(Seffi)Naor,andPrabhakarRaghavan
11.1Introduction
11.2Roundinglinearprograms
11.2.1Theintegermulticommodityflowproblem
11.2.2Coveringandpackingproblems
11.2.3Themaximumsatisfiabilityproblem
11.2.4Relatedwork
11.3Semidefiniteprogramming
11.3.1Themaximumcutproblem
11.3.2Thegraphcoloringproblem
11.4Concludingremarks
11.4.1Derandomizafionandparallelization
11.4.2Computationalexperience
11.4.3Openproblems
12TheMarkovChainMonteCarloMethod:AnApproachto
ApproximateCountingandIntegration
MarkJerrumandAlistairSinclair
12.1Introduction
12.2Anillustrativeexample
12.3Twotechniquesforboundingthemixingtime
12.3.1Canonicalpaths
12.3.2Conductance
12.4Amorecomplexexample:monomer-dimersystems
12.5Moreapplications
12.5.1Thepermanent
12.5.2Volumeofconvexbodies
12.5.3Statisticalphysics
12.5.4Matroidbases:anopenproblem
12.6TheMetropolisalgorithmandsimulatedannealing
Appendix
13OnlineComputation
SandyIraniandAnnaR.Karlin
13.1Introduction
13.2Threeexamplesofcompetitiveanalysis
13.2.1Paging
13.2.2Thek-serverproblem
13.2.3Metricaltasksystems
13.3Theoreticalunderpinnings:deterministicalgorithms
13.3.1Lowerbounds
13.3.2Designprinciples
13.3.3Boundingcompetitiveness
13.4Theoreticalunderpinnings:randomizedalgorithms
13.4.1Example:paging
13.4.2Lowerbounds
13.4.3Therelationshipsbetweentheadversaries
13.5Thek-serverproblemrevisited
13.5.1History.
13.5.2Notationandpropertiesofworkfunctions.
13.5.3TheworkfunctionalgorithmWFA
13.5.4Proofof(2k-1)-competitiveness
13.5.5Thedualitylemma
13.5.6Thepotentialfunction
13.5.7Quasi-convexityandthedualitylemma
13.6Onlineloadbalancingandvirtualcircuitrouting
13.6.1Loadbalancingonunrelatedmachines
13.6.2Onlinevirtualcircuitrouting
13.6.3Recentresults
13.7Variantsofcompetitiveanalysis
13.8Conclusionsanddirectionsforfutureresearch
GlossaryofProblems
Index