Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques

Table of Contents

1. Altmetric Badge
   Book Overview
2. Altmetric Badge
   Chapter 1 Approximating Optimal Binary Decision Trees
3. Altmetric Badge
   Chapter 2 Santa Claus Meets Hypergraph Matchings
4. Altmetric Badge
   Chapter 3 Ordinal Embedding: Approximation Algorithms and Dimensionality Reduction
5. Altmetric Badge
   Chapter 4 Connected Vertex Covers in Dense Graphs
6. Altmetric Badge
   Chapter 5 Improved Approximation Guarantees through Higher Levels of SDP Hierarchies
7. Altmetric Badge
   Chapter 6 Sweeping Points
8. Altmetric Badge
   Chapter 7 Constraint Satisfaction over a Non-Boolean Domain: Approximation Algorithms and Unique-Games Hardness
9. Altmetric Badge
   Chapter 8 Fully Polynomial Time Approximation Schemes for Time-Cost Tradeoff Problems in Series-Parallel Project Networks
10. Altmetric Badge
    Chapter 9 Efficient Algorithms for Fixed-Precision Instances of Bin Packing and Euclidean TSP
11. Altmetric Badge
    Chapter 10 Approximating Maximum Subgraphs without Short Cycles
12. Altmetric Badge
    Chapter 11 Deterministic 7/8-Approximation for the Metric Maximum TSP
13. Altmetric Badge
    Chapter 12 Inapproximability of Survivable Networks
14. Altmetric Badge
    Chapter 13 Approximating Single Machine Scheduling with Scenarios
15. Altmetric Badge
    Chapter 14 Streaming Algorithms for k -Center Clustering with Outliers and with Anonymity
16. Altmetric Badge
    Chapter 15 A General Framework for Designing Approximation Schemes for Combinatorial Optimization Problems with Many Objectives Combined into One
17. Altmetric Badge
    Chapter 16 The Directed Minimum Latency Problem
18. Altmetric Badge
    Chapter 17 A Simple LP Relaxation for the Asymmetric Traveling Salesman Problem
19. Altmetric Badge
    Chapter 18 Approximating Directed Weighted-Degree Constrained Networks
20. Altmetric Badge
    Chapter 19 A Constant Factor Approximation for Minimum λ -Edge-Connected k -Subgraph with Metric Costs
21. Altmetric Badge
    Chapter 20 Budgeted Allocations in the Full-Information Setting
22. Altmetric Badge
    Chapter 21 Optimal Random Matchings on Trees and Applications
23. Altmetric Badge
    Chapter 22 Small Sample Spaces Cannot Fool Low Degree Polynomials
24. Altmetric Badge
    Chapter 23 Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size
25. Altmetric Badge
    Chapter 24 Tensor Products of Weakly Smooth Codes Are Robust
26. Altmetric Badge
    Chapter 25 On the Degree Sequences of Random Outerplanar and Series-Parallel Graphs
27. Altmetric Badge
    Chapter 26 Improved Bounds for Testing Juntas
28. Altmetric Badge
    Chapter 27 The Complexity of Distinguishing Markov Random Fields
29. Altmetric Badge
    Chapter 28 Reconstruction of Markov Random Fields from Samples: Some Observations and Algorithms
30. Altmetric Badge
    Chapter 29 Tight Bounds for Hashing Block Sources
31. Altmetric Badge
    Chapter 30 Improved Separations between Nondeterministic and Randomized Multiparty Communication
32. Altmetric Badge
    Chapter 31 Quantum and Randomized Lower Bounds for Local Search on Vertex-Transitive Graphs
33. Altmetric Badge
    Chapter 32 On the Query Complexity of Testing Orientations for Being Eulerian
34. Altmetric Badge
    Chapter 33 Approximately Counting Embeddings into Random Graphs
35. Altmetric Badge
    Chapter 34 Increasing the Output Length of Zero-Error Dispersers
36. Altmetric Badge
    Chapter 35 Euclidean Sections of $\ell_1^N$ with Sublinear Randomness and Error-Correction over the Reals
37. Altmetric Badge
    Chapter 36 The Complexity of Local List Decoding
38. Altmetric Badge
    Chapter 37 Limitations of Hardness vs. Randomness under Uniform Reductions
39. Altmetric Badge
    Chapter 38 Learning Random Monotone DNF
40. Altmetric Badge
    Chapter 39 Breaking the ε -Soundness Bound of the Linearity Test over GF(2)
41. Altmetric Badge
    Chapter 40 Dense Fast Random Projections and Lean Walsh Transforms
42. Altmetric Badge
    Chapter 41 Near Optimal Dimensionality Reductions That Preserve Volumes
43. Altmetric Badge
    Chapter 42 Sampling Hypersurfaces through Diffusion
44. Altmetric Badge
    Chapter 43 A 2-Source Almost-Extractor for Linear Entropy
45. Altmetric Badge
    Chapter 44 Extractors for Three Uneven-Length Sources
46. Altmetric Badge
    Chapter 45 The Power of Choice in a Generalized Pólya Urn Model
47. Altmetric Badge
    Chapter 46 Corruption and Recovery-Efficient Locally Decodable Codes
48. Altmetric Badge
    Chapter 47 Quasi-randomness Is Determined by the Distribution of Copies of a Fixed Graph in Equicardinal Large Sets