Combinatorial Optimization Exact and Approximate：组合优化的精确近似....docVIP

CombinatorialOptimization:

ExactandApproximateAlgorithms

f

h

C

b

d

g

a

e

d

1

g

11

f

a

1

h

1

C

2

e

1

b

LucaTrevisan

StanfordUniversity

March19,2011

i

Foreword

TheseareminimallyeditedlecturenotesfromtheclassCS261:OptimizationandAlgorith-micParadigmsthatItaughtatStanfordintheWinter2011term.Thefollowing18lecturescovertopicsinapproximationalgorithms,exactoptimization,andonlinealgorithms.

IgratefullyacknowledgethesupportoftheNationalScienceFoundation,undergrantCCF1017403.Anyopinions,findingsandconclusionsorrecommendationsexpressedinthesenotesaremyownanddonotnecessarilyreflecttheviewsoftheNationalScienceFoundation.

LucaTrevisan,SanFrancisco,March19,2011.

cc]①∈

BYNCNO◎2011byLucaTrevisan

ThisworkislicensedundertheCreativeCommonsAttribution-NonCommercial-NoDerivs

3.0UnportedLicense.Toviewacopyofthislicense,visit/

licenses/by-nc-nd/3.0/orsendalettertoCreativeCommons,171SecondStreet,Suite300,SanFrancisco,California,94105,USA.

ii

iii

Contents

Forewordi

11Introduction

1

1.1Overview 1

1.2TheVertexCoverProblem .3

1.2.1Definitions 3

1.2.2TheAlgorithm 4

72SteinerTreeApproximation

7

2.1ApproximatingtheMetricSteinerTreeProblem 7

2.2MetricversusGeneralSteinerTree 10

3TSPandEulerianCycles13

3.1TheTravelingSalesmanProblem 13

3.2A2-approximateAlgorithm 16

3.3EulerianCycles 18

3.4EulerianCyclesandTSPApproximation 19

4TSPandSetCover21

4.1BetterApproximationoftheT