Approximation Algorithms

by Vazirani, Vijay V.

• ISBN13: 9783540653677
• ISBN10: 3540653678
• eBook ISBN(s): 9783662045657
• Format: Hardcover
• Copyright: 2001-08-01
• Publisher: Springer-Nature New York Inc
• More Book Details
• Purchase Benefits

Summary

This book covers the dominant theoretical approaches to the approximate solution of hard combinatorial optimization and enumeration problems. It contains elegant combinatorial theory, useful and interesting algorithms, and deep results about the intrinsic complexity of combinatorial problems. Its clarity of exposition and excellent selection of exercises will make it accessible and appealing to all those with a taste for mathematics and algorithms. Richard Karp,University Professor, University of California at Berkeley Following the development of basic combinatorial optimization techniques in the 1960s and 1970s, a main open question was to develop a theory of approximation algorithms. In the 1990s, parallel developments in techniques for designing approximation algorithms as well as methods for proving hardness of approximation results have led to a beautiful theory. The need to solve truly large instances of computationally hard problems, such as those arising from the Internet or the human genome project, has also increased interest in this theory. The field is currently very active, with the toolbox of approximation algorithm design techniques getting always richer. It is a pleasure to recommend Vijay Vazirani's well-written and comprehensive book on this important and timely topic. I am sure the reader will find it most useful both as an introduction to approximability as well as a reference to the many aspects of approximation algorithms. Làszlò Lovàsz, Senior Researcher, Microsoft Research

Table of Contents

Introduction	1	(14)
Lower bounding OPT	2	(3)
An approximation algorithm for cardinality vertex cover	3	(1)
Can the approximation guarantee the improved?	3	(2)
Well-characterized problems and min-max relations	5	(2)
Exercises	7	(3)
Notes	10	(5)
Part I. Combinatorial Algorithms
Set Cover	15	(12)
The greedy algorithm	16	(1)
Layering	17	(2)
Application to shortest superstring	19	(3)
Exercises	22	(4)
Notes	26	(1)
Steiner Tree and TSP	27	(11)
Metric Steiner tree	27	(3)
MST-based algorithm	28	(2)
Metric TSP	30	(3)
A simple factor 2 algorithm	31	(1)
Improving the factor to 3/2	32	(1)
Exercises	33	(4)
Notes	37	(1)
Multiway Cut and k-Cut	38	(9)
The multiway cut problem	38	(2)
The minimum k-cut problem	40	(4)
Exercises	44	(2)
Notes	46	(1)
k-Center	47	(7)
Parametric pruning applied to metric k-center	47	(3)
The weighted version	50	(2)
Exercises	52	(1)
Notes	53	(1)
Feedback Vertex Set	54	(7)
Cyclomatic weighted graphs	54	(3)
Layering applied to feedback vertex set	57	(3)
Exercises	60	(1)
Notes	60	(1)
Shortest Superstring	61	(7)
A factor 4 algorithm	61	(3)
Improving to factor 3	64	(2)
Achieving half the optimal compression	66	(1)
Exercises	66	(1)
Notes	67	(1)
Knapsack	68	(6)
A pseudo-polynomial time algorithm for knapsack	69	(1)
An FPTAS for knapsack	69	(2)
Strong NP-hardness and the existence of FPTAS's	71	(1)
Is an FPTAS the most desirable approximation algorithm?	72	(1)
Exercises	72	(1)
Notes	73	(1)
Bin Packing	74	(5)
An asymptotic PTAS	74	(3)
Exercises	77	(1)
Notes	78	(1)
Minimum Makespan Scheduling	79	(5)
Factor 2 algorithm	79	(1)
A PTAS for minimum makespan	80	(3)
Bin packing with fixed number of object sizes	81	(1)
Reducing makespan to restricted bin packing	81	(2)
Exercises	83	(1)
Notes	83	(1)
Euclidean TSP	84	(9)
The algorithm	84	(3)
Proof of correctness	87	(2)
Exercises	89	(1)
Notes	89	(4)
Part II. LP-Based Algorithms
Introduction to LP-Duality	93	(15)
The LP-duality theorem	93	(4)
Min-max relations and LP-duality	97	(3)
Two fundamental algorithm design techniques	100	(3)
A comparison of the techniques and the notion of integrality gap	101	(2)
Exercises	103	(4)
Notes	107	(1)
Set Cover via Dual Fitting	108	(11)
Dual-fitting-based analysis for the greedy set cover algorithm	108	(4)
Can the approximation guarantee be improved?	111	(1)
Generalizations of set cover	112	(4)
Dual fitting applied to constrained set multicover	112	(4)
Exercises	116	(2)
Notes	118	(1)
Rounding Applied to Set Cover	119	(6)
A simple rounding algorithm	119	(1)
Randomized rounding	120	(2)
Half-integrality of vertex cover	122	(1)
Exercises	123	(1)
Notes	124	(1)
Set Cover via the Primal-Dual Schema	125	(6)
Overview of the schema	125	(2)
Primal-dual schema applied to set cover	127	(2)
Exercises	129	(1)
Notes	129	(2)
Maximum Satisfiability	131	(9)
Dealing with large clauses	132	(1)
Derandomizing via the method of conditional expectation	132	(2)
Dealing with small clauses via LP-rounding	134	(2)
A 3/4 factor algorithm	136	(1)
Exercises	137	(2)
Notes	139	(1)
Scheduling on Unrelated Parallel Machines	140	(6)
Parametric pruning in an LP setting	140	(1)
Properties of extreme point solutions	141	(1)
The algorithm	142	(1)
Additional properties of extreme point solutions	143	(1)
Exercises	144	(1)
Notes	145	(1)
Multicut and Integer Multicommodity Flow in Trees	146	(9)
The problmes and their LP-relaxations	146	(3)
Primal-dual schema based algorithm	149	(3)
Exercises	152	(2)
Notes	154	(1)
Multiway Cut	155	(13)
An interesting LP-relaxation	155	(2)
Randomized rounding algorithm	157	(3)
Half-integrality of node multiway cut	160	(3)
Exercises	163	(4)
Notes	167	(1)
Multicut in General Graphs	168	(12)
Sum multicommodity flow	168	(2)
LP-rounding-based algorithm	170	(5)
Growing a region: the continous process	171	(1)
The discrete process	172	(1)
Finding successive regions	173	(2)
A tight example	175	(1)
Some applications of multicut	176	(1)
Exercises	177	(2)
Notes	179	(1)
Sparset Cut	180	(18)
Demands multicommodity flow	180	(1)
Linear programming formulation	181	(2)
Metrics, cut packings, and l1-embeddability	183	(3)
Cut packings for metrics	183	(2)
l1-embeddability of metrics	185	(1)
Low distortion l1-embeddings for metrics	186	(5)
Ensuring that a single edge is not overshrunk	187	(3)
Ensuring that no edge is overshrunk	190	(1)
LP-rounding-based algorithm	191	(1)
Applications	192	(3)
Edge expansion	192	(1)
Conductance	192	(1)
Balanced cut	193	(1)
Minimum cut linear arrangement	194	(1)
Exercises	195	(2)
Notes	197	(1)
Steiner Forest	198	(15)
LP-relaxation and dual	198	(1)
Primal-dual schema with synchronization	199	(5)
Analysis	204	(3)
Exercises	207	(5)
Notes	212	(1)
Steiner Network	213	(19)
The LP-relaxation and half-integrality	213	(4)
The technique of iterated rounding	217	(2)
Characterizing extreme point solutions	219	(2)
A counting argument	221	(3)
Exercises	224	(7)
Notes	231	(1)
Facility Location	232	(11)
An intuitive understanding of the dual	233	(1)
Relaxing primal complementary slackness conditions	234	(1)
Primal-dual schema based algorithm	235	(1)
Analysis	236	(3)
Running time	238	(1)
Tight example	238	(1)
Exercises	239	(3)
Notes	242	(1)
k-Median	243	(13)
LP-relaxation and dual	243	(1)
The high-level idea	244	(3)
Randomized rounding	247	(3)
Derandomization	248	(1)
Running time	249	(1)
Tight example	249	(1)
Integrality gap	250	(1)
A Lagrangian relaxation technique for approximation algorithms	250	(1)
Exercises	251	(3)
Notes	254	(2)
Semidefinite Programming	256	(17)
Strict quadratic programs and vector programs	256	(2)
Properties of positive semidefinite matrices	258	(1)
The semidefinite programming problem	259	(2)
Randomized rounding algorithm	261	(3)
Improving the guarantee for MAX-2SAT	264	(2)
Exercises	266	(3)
Notes	269	(4)
Part III. Other Topics
Shortest Vector	273	(21)
Bases, determinants, and orthogonality defect	274	(2)
The algorithms of Euclid and Gauss	276	(2)
Lower bounding OPT using Gram-Schmidt orthogonalization	278	(2)
Extension to n dimensions	280	(4)
The dual lattice and its algorithmic use	284	(4)
Exercises	288	(4)
Notes	292	(2)
Counting Problmes	294	(12)
Counting DNF solutions	295	(2)
Network reliability	297	(5)
Upperbounding the number of near-minimum cuts	298	(2)
Analysis	300	(2)
Exercises	302	(3)
Notes	305	(1)
Hardness of Approximation	306	(28)
Reductions, gaps, and hardness factors	306	(3)
The PCP theorem	309	(2)
Hardness of MAX-3SAT	311	(2)
Hardness of MAX-3SAT with bounded occurence of variables	313	(3)
Hardness of vertex cover and Steiner tree	316	(2)
Hardness of clique	318	(4)
Hardness of set cover	322	(7)
The two-prover one-round characterization of NP	322	(2)
The gadget	324	(1)
Reducing error probability by parallel repetition	325	(1)
The reduction	326	(3)
Exercises	329	(3)
Notes	332	(2)
Open Problems	334	(21)
Problems having constant factor algorithms	334	(2)
Other optimization problems	336	(2)
Counting problems	338	(5)
Appendix
A An Overview of Complexity Theory for the Algorithm Designer	343	(9)
A.1 Certificates and the class NP	343	(1)
A.2 Reductions and NP-completeness	344	(1)
A.3 NP-optimization problems and approximation algorithms	345	(2)
A.3.1 Approximation factor preserving reductions	347	(1)
A.4 Randomized complexity classes	347	(1)
A.5 Self-reducibility	348	(3)
A.6 Notes	351	(1)
B Basic Facts from Probability Theory	352	(3)
B.1 Expectation and moments	352	(1)
B.2 Deviations from the mean	353	(1)
B.3 Basic distributions	354	(1)
B.4 Notes	354	(1)
References	355	(16)
Problem Index	371	(4)
Subject Index	375