Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques

Table of Contents

1. Altmetric Badge
   Book Overview
2. Altmetric Badge
   Chapter 1 Designing Networks with Existing Traffic to Support Fast Restoration
3. Altmetric Badge
   Chapter 2 Simultaneous Source Location
4. Altmetric Badge
   Chapter 3 Computationally-Feasible Truthful Auctions for Convex Bundles
5. Altmetric Badge
   Chapter 4 Randomized Approximation Algorithms for Set Multicover Problems with Applications to Reverse Engineering of Protein and Gene Networks
6. Altmetric Badge
   Chapter 5 On the Crossing Spanning Tree Problem
7. Altmetric Badge
   Chapter 6 A 3/4-Approximation Algorithm for Maximum ATSP with Weights Zero and One
8. Altmetric Badge
   Chapter 7 Maximum Coverage Problem with Group Budget Constraints and Applications
9. Altmetric Badge
   Chapter 8 The Greedy Algorithm for the Minimum Common String Partition Problem
10. Altmetric Badge
    Chapter 9 Approximating Additive Distortion of Embeddings into Line Metrics
11. Altmetric Badge
    Chapter 10 Polylogarithmic Inapproximability of the Radio Broadcast Problem
12. Altmetric Badge
    Chapter 11 On Systems of Linear Equations with Two Variables per Equation
13. Altmetric Badge
    Chapter 12 An Auction-Based Market Equilibrium Algorithm for the Separable Gross Substitutability Case
14. Altmetric Badge
    Chapter 13 Cost-Sharing Mechanisms for Network Design
15. Altmetric Badge
    Chapter 14 Approximating Max k CSP Using Random Restrictions
16. Altmetric Badge
    Chapter 15 Approximation Schemes for Broadcasting in Heterogenous Networks
17. Altmetric Badge
    Chapter 16 Centralized Deterministic Broadcasting in Undirected Multi-hop Radio Networks
18. Altmetric Badge
    Chapter 17 Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
19. Altmetric Badge
    Chapter 18 Cuts and Orderings: On Semidefinite Relaxations for the Linear Ordering Problem
20. Altmetric Badge
    Chapter 19 Min-Max Multiway Cut
21. Altmetric Badge
    Chapter 20 The Chromatic Number of Random Regular Graphs
22. Altmetric Badge
    Chapter 21 Estimating the Distance to a Monotone Function
23. Altmetric Badge
    Chapter 22 Edge Coloring with Delays
24. Altmetric Badge
    Chapter 23 Small Pseudo-random Families of Matrices: Derandomizing Approximate Quantum Encryption
25. Altmetric Badge
    Chapter 24 The Sketching Complexity of Pattern Matching
26. Altmetric Badge
    Chapter 25 Non-Abelian Homomorphism Testing, and Distributions Close to Their Self-convolutions
27. Altmetric Badge
    Chapter 26 Robust Locally Testable Codes and Products of Codes
28. Altmetric Badge
    Chapter 27 A Stateful Implementation of a Random Function Supporting Parity Queries over Hypercubes
29. Altmetric Badge
    Chapter 28 Strong Refutation Heuristics for Random k -SAT
30. Altmetric Badge
    Chapter 29 Counting Connected Graphs and Hypergraphs via the Probabilistic Method
31. Altmetric Badge
    Chapter 30 Improved Randomness Extraction from Two Independent Sources
32. Altmetric Badge
    Chapter 31 The Diameter of Randomly Perturbed Digraphs and Some Applications
33. Altmetric Badge
    Chapter 32 Maximum Weight Independent Sets and Matchings in Sparse Random Graphs
34. Altmetric Badge
    Chapter 33 Estimating Frequency Moments of Data Streams Using Random Linear Combinations
35. Altmetric Badge
    Chapter 34 Fooling Parity Tests with Parity Gates
36. Altmetric Badge
    Chapter 35 Distribution-Free Connectivity Testing
37. Altmetric Badge
    Chapter 36 Testing the Independence Number of Hypergraphs
38. Altmetric Badge
    Chapter 37 A Note on Approximate Counting for k -DNF