↓ Skip to main content

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

Overview of attention for book
Cover of 'Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques'

Table of Contents

  1. Altmetric Badge
    Book Overview
  2. Altmetric Badge
    Chapter 1 Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
  3. Altmetric Badge
    Chapter 2 Inapproximability of NP-Complete Variants of Nash Equilibrium
  4. Altmetric Badge
    Chapter 3 Sparse Recovery with Partial Support Knowledge
  5. Altmetric Badge
    Chapter 4 On Capacitated Set Cover Problems
  6. Altmetric Badge
    Chapter 5 Bandwidth and Low Dimensional Embedding
  7. Altmetric Badge
    Chapter 6 O(1)-Approximations for Maximum Movement Problems
  8. Altmetric Badge
    Chapter 7 Optimal Lower Bounds for Universal and Differentially Private Steiner Trees and TSPs
  9. Altmetric Badge
    Chapter 8 Social Welfare in One-Sided Matching Markets without Money
  10. Altmetric Badge
    Chapter 9 Primal-Dual Schema and Lagrangian Relaxation for the k-Location-Routing Problem
  11. Altmetric Badge
    Chapter 10 Scheduling Resources for Throughput Maximization
  12. Altmetric Badge
    Chapter 11 Coloring and Maximum Independent Set of Rectangles
  13. Altmetric Badge
    Chapter 12 A Primal-Dual Approximation Algorithm for Min-Sum Single-Machine Scheduling Problems
  14. Altmetric Badge
    Chapter 13 A (1 + ln 2)-Approximation Algorithm for Minimum-Cost 2-Edge-Connectivity Augmentation of Trees with Constant Radius
  15. Altmetric Badge
    Chapter 14 Periodicity and Cyclic Shifts via Linear Sketches
  16. Altmetric Badge
    Chapter 15 An Approximation Algorithm for the Tree t-Spanner Problem on Unweighted Graphs via Generalized Chordal Graphs
  17. Altmetric Badge
    Chapter 16 Approximating the Closest Vector Problem Using an Approximate Shortest Vector Oracle
  18. Altmetric Badge
    Chapter 17 Opaque Sets
  19. Altmetric Badge
    Chapter 18 Exploring and Triangulating a Region by a Swarm of Robots
  20. Altmetric Badge
    Chapter 19 Improved Competitive Ratios for Submodular Secretary Problems (Extended Abstract)
  21. Altmetric Badge
    Chapter 20 Locating Depots for Capacitated Vehicle Routing
  22. Altmetric Badge
    Chapter 21 Satisfying Degree-d Equations over GF[2] n
  23. Altmetric Badge
    Chapter 22 Black-Box Reductions in Mechanism Design
  24. Altmetric Badge
    Chapter 23 Multiplicative Approximations of Random Walk Transition Probabilities
  25. Altmetric Badge
    Chapter 24 Approximation Schemes for the Betweenness Problem in Tournaments and Related Ranking Problems
  26. Altmetric Badge
    Chapter 25 Network-Design with Degree Constraints
  27. Altmetric Badge
    Chapter 26 Improved Approximation Algorithms for the Min-Max Tree Cover and Bounded Tree Cover Problems
  28. Altmetric Badge
    Chapter 27 Algorithmic Extensions of Cheeger’s Inequality to Higher Eigenvalues and Partitions
  29. Altmetric Badge
    Chapter 28 Nearly Optimal NP-Hardness of Vertex Cover on k-Uniform k-Partite Hypergraphs
  30. Altmetric Badge
    Chapter 29 A Linear Time Approximation Scheme for Maximum Quartet Consistency on Sparse Sampled Inputs
  31. Altmetric Badge
    Chapter 30 Viral Processes by Random Walks on Random Regular Graphs
  32. Altmetric Badge
    Chapter 31 Quantum Property Testing for Bounded-Degree Graphs
  33. Altmetric Badge
    Chapter 32 Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification
  34. Altmetric Badge
    Chapter 33 Testing Graph Blow-Up
  35. Altmetric Badge
    Chapter 34 On Sums of Locally Testable Affine Invariant Properties
  36. Altmetric Badge
    Chapter 35 Limits on the Rate of Locally Testable Affine-Invariant Codes
  37. Altmetric Badge
    Chapter 36 The Computational Complexity of Estimating MCMC Convergence Time
  38. Altmetric Badge
    Chapter 37 Streaming Algorithms with One-Sided Estimation
  39. Altmetric Badge
    Chapter 38 Everywhere-Tight Information Cost Tradeoffs for Augmented Index
  40. Altmetric Badge
    Chapter 39 A Canonical Form for Testing Boolean Function Properties
  41. Altmetric Badge
    Chapter 40 Independent Sets in Random Graphs from the Weighted Second Moment Method
  42. Altmetric Badge
    Chapter 41 Extractors and Lower Bounds for Locally Samplable Sources
  43. Altmetric Badge
    Chapter 42 A Deterministic Algorithm for the Frieze-Kannan Regularity Lemma
  44. Altmetric Badge
    Chapter 43 Dense Locally Testable Codes Cannot Have Constant Rate and Distance
  45. Altmetric Badge
    Chapter 44 Efficient Probabilistically Checkable Debates
  46. Altmetric Badge
    Chapter 45 An Efficient Partitioning Oracle for Bounded-Treewidth Graphs
  47. Altmetric Badge
    Chapter 46 Inflatable Graph Properties and Natural Property Tests
  48. Altmetric Badge
    Chapter 47 Fast Simulation of Large-Scale Growth Models
  49. Altmetric Badge
    Chapter 48 Improved Inapproximability Results for Counting Independent Sets in the Hard-Core Model
  50. Altmetric Badge
    Chapter 49 Proximity Oblivious Testing and the Role of Invariances
  51. Altmetric Badge
    Chapter 50 Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
  52. Altmetric Badge
    Chapter 51 Public Key Locally Decodable Codes with Short Keys
  53. Altmetric Badge
    Chapter 52 On Sampling from Multivariate Distributions
  54. Altmetric Badge
    Chapter 53 Almost Optimal Explicit Johnson-Lindenstrauss Families
  55. Altmetric Badge
    Chapter 54 Correlation Bounds for Poly-size $\mbox{\rm AC}^0$ Circuits with n 1 − o(1) Symmetric Gates
  56. Altmetric Badge
    Chapter 55 Clustering in Interfering Binary Mixtures
  57. Altmetric Badge
    Chapter 56 Approximating the Influence of Monotone Boolean Functions in $O(\sqrt{n})$ Query Complexity
  58. Altmetric Badge
    Chapter 57 On Approximating the Number of Relevant Variables in a Function
  59. Altmetric Badge
    Chapter 58 Query Complexity in Errorless Hardness Amplification
Overall attention for this book and its chapters
Altmetric Badge

Mentioned by

twitter
6 X users
wikipedia
2 Wikipedia pages
q&a
1 Q&A thread

Citations

dimensions_citation
6 Dimensions

Readers on

mendeley
8 Mendeley
You are seeing a free-to-access but limited selection of the activity Altmetric has collected about this research output. Click here to find out more.
Title
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Published by
Springer, Berlin, Heidelberg, January 2011
DOI 10.1007/978-3-642-22935-0
ISBNs
978-3-64-222934-3, 978-3-64-222935-0
Authors

Goldberg, Leslie Ann, Jansen, Klaus, Ravi, R, Rolim, José D. P

Editors

Leslie Ann Goldberg, Klaus Jansen, R. Ravi, José D. P. Rolim

X Demographics

X Demographics

The data shown below were collected from the profiles of 6 X users who shared this research output. Click here to find out more about how the information was compiled.
Mendeley readers

Mendeley readers

The data shown below were compiled from readership statistics for 8 Mendeley readers of this research output. Click here to see the associated Mendeley record.

Geographical breakdown

Country Count As %
Unknown 8 100%

Demographic breakdown

Readers by professional status Count As %
Researcher 1 13%
Unknown 7 88%
Readers by discipline Count As %
Mathematics 1 13%
Unknown 7 88%