2001 ApproximationAlgorithms

• (Vazirani, 2001) ⇒ Vijay V. Vazirani. (2001). “Approximation Algorithms.” In: Springer. ISBN:3540653678

Subject Headings: Approximation Algorithm.

Cited By

• ~1,469 http://scholar.google.com/scholar?cites=14484105971157271497

2006

• M. Dorigo, M. Birattari, and T. Stutzle. (2006). “Ant colony optimization.” In: IEEE Computational Intelligence Magazine
  • Cited by ~3367 http://scholar.google.com/scholar?cites=13661364366239527917&as_sdt=2005&sciodt=2000

2003

• S. Guha, A. Meyerson, N. Mishra, R. Motwani, and L. O'Callaghan. (2003). “Clustering data streams: Theory and practice.” In: IEEE Transactions on …,
  • A data stream is an ordered sequence of points $\big. x_1, \ldots, x_n\bigr.$ that must be accessed in order and that can be read only once or a small number of times. Each reading of the sequence is called a linear scan or a pass. The stream model is motivated by emerging applications ...
  • Cited by ~723 http://scholar.google.com/scholar?cites=13952523987732769420

Quotes

Book Overview

• Approximation algorithms are currently a central and fast-developing area of research in theoretical computer science. This monograph covers the basic techniques used in the latest research work, techniques that everyone in the field should know, and shows that they form the beginnings of a promising theory. The author consolidates progress made so far, including some very recent results, and makes a strong effort to convey the beauty and excitement of work in the field.
  • 1 Introduction 1
  • 2 Set Cover 15
  • 3 Steiner Tree and TSP 27
  • 4 Multiway Cut and k-Cut 38
  • 5 k-Center 47
  • 6 Feedback Vertex Set 54
  • 7 Shortest Superstring 61
  • 8 Knapsack 68
  • 9 Bin Packing 74
  • 10 Minimum Makespan Scheduling 79
  • 11 Euclidean TSP 84
  • 12 Introduction to LP-Duality 93
  • 13 Set Cover via Dual Fitting 108
  • 14 Rounding Applied to Set Cover 119
  • 15 Set Cover via the Primal-Dual Schema 125
  • 16 Maximum Satisfiability 131
  • 17 Scheduling on Unrelated Parallel Machines 140
  • 18 Multicut and Integer Multicommodity Flow in Trees 146
  • 19 Multiway Cut 155
  • 20 Multicut in General Graphs 168
  • 21 Sparsest Cut 180
  • 22 Steiner Forest 198
  • 23 Steiner Network 213
  • 24 Facility Location 232
  • 25 k-Median 243
  • 26 Semidefinite Programming 256
  • 27 Shortest Vector 273
  • 28 Counting Problems 294
  • 29 Hardness of Approximation 306
  • 30 Open Problems 334
  • App. A An Overview of Complexity Theory for the Algorithm Designer 343
  • App. B Basic Facts from Probability Theory 352

References

---

,

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2001 ApproximationAlgorithms	Vijay V. Vazirani			Approximation Algorithms		Springer	http://books.google.com/books?id=EILqAmzKgYIC			2001