↓ 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 A New Point of NP-Hardness for 2-to-1 Label Cover
  3. Altmetric Badge
    Chapter 2 Inapproximability of Treewidth, One-Shot Pebbling, and Related Layout Problems
  4. Altmetric Badge
    Chapter 3 Additive Approximation for Near-Perfect Phylogeny Construction
  5. Altmetric Badge
    Chapter 4 Improved Spectral-Norm Bounds for Clustering
  6. Altmetric Badge
    Chapter 5 Primal-Dual Approximation Algorithms for Node-Weighted Network Design in Planar Graphs
  7. Altmetric Badge
    Chapter 6 What’s the Frequency, Kenneth?: Sublinear Fourier Sampling Off the Grid
  8. Altmetric Badge
    Chapter 7 Improved Hardness Results for Profit Maximization Pricing Problems with Unlimited Supply
  9. Altmetric Badge
    Chapter 8 Online Flow Time Scheduling in the Presence of Preemption Overhead
  10. Altmetric Badge
    Chapter 9 Prize-Collecting Survivable Network Design in Node-Weighted Graphs
  11. Altmetric Badge
    Chapter 10 Approximating Minimum-Cost Connected T -Joins
  12. Altmetric Badge
    Chapter 11 iBGP and Constrained Connectivity
  13. Altmetric Badge
    Chapter 12 Online Scheduling of Jobs with Fixed Start Times on Related Machines
  14. Altmetric Badge
    Chapter 13 A Systematic Approach to Bound Factor Revealing LPs and Its Application to the Metric and Squared Metric Facility Location Problems
  15. Altmetric Badge
    Chapter 14 Approximating Bounded Occurrence Ordering CSPs
  16. Altmetric Badge
    Chapter 15 On the NP-Hardness of Max-Not-2
  17. Altmetric Badge
    Chapter 16 The Remote Set Problem on Lattices
  18. Altmetric Badge
    Chapter 17 Approximation Algorithms for Generalized and Variable-Sized Bin Covering
  19. Altmetric Badge
    Chapter 18 Approximating Minimum Linear Ordering Problems
  20. Altmetric Badge
    Chapter 19 New Approximation Results for Resource Replication Problems
  21. Altmetric Badge
    Chapter 20 Maximum Matching in Semi-streaming with Few Passes
  22. Altmetric Badge
    Chapter 21 Improved Inapproximability for TSP
  23. Altmetric Badge
    Chapter 22 Approximation Algorithm for Non-boolean MAX k -CSP
  24. Altmetric Badge
    Chapter 23 Planarizing an Unknown Surface
  25. Altmetric Badge
    Chapter 24 The Projection Games Conjecture and the NP-Hardness of ln n -Approximating Set-Cover
  26. Altmetric Badge
    Chapter 25 New and Improved Bounds for the Minimum Set Cover Problem
  27. Altmetric Badge
    Chapter 26 Hardness of Vertex Deletion and Project Scheduling
  28. Altmetric Badge
    Chapter 27 Approximation Guarantees for the Minimum Linear Arrangement Problem by Higher Eigenvalues
  29. Altmetric Badge
    Chapter 28 Circumventing d -to-1 for Approximation Resistance of Satisfiable Predicates Strictly Containing Parity of Width Four
  30. Altmetric Badge
    Chapter 29 Spectral Norm of Symmetric Functions
  31. Altmetric Badge
    Chapter 30 Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
  32. Altmetric Badge
    Chapter 31 Testing Permanent Oracles – Revisited
  33. Altmetric Badge
    Chapter 32 Limitations of Local Filters of Lipschitz and Monotone Functions
  34. Altmetric Badge
    Chapter 33 Testing Lipschitz Functions on Hypergrid Domains
  35. Altmetric Badge
    Chapter 34 Extractors for Polynomials Sources over Constant-Size Fields of Small Characteristic
  36. Altmetric Badge
    Chapter 35 Multiple-Choice Balanced Allocation in (Almost) Parallel
  37. Altmetric Badge
    Chapter 36 Optimal Hitting Sets for Combinatorial Shapes
  38. Altmetric Badge
    Chapter 37 Tight Bounds for Testing k -Linearity
  39. Altmetric Badge
    Chapter 38 Pseudorandomness for Linear Length Branching Programs and Stack Machines
  40. Altmetric Badge
    Chapter 39 A Discrepancy Lower Bound for Information Complexity
  41. Altmetric Badge
    Chapter 40 On the Coin Weighing Problem with the Presence of Noise
  42. Altmetric Badge
    Chapter 41 Information Complexity versus Corruption and Applications to Orthogonality and Gap-Hamming
  43. Altmetric Badge
    Chapter 42 An Explicit VC-Theorem for Low-Degree Polynomials
  44. Altmetric Badge
    Chapter 43 Tight Bounds on the Threshold for Permuted k -Colorability
  45. Altmetric Badge
    Chapter 44 Sparse and Lopsided Set Disjointness via Information Theory
  46. Altmetric Badge
    Chapter 45 Maximal Empty Boxes Amidst Random Points
  47. Altmetric Badge
    Chapter 46 Rainbow Connectivity of Sparse Random Graphs
  48. Altmetric Badge
    Chapter 47 Invertible Zero-Error Dispersers and Defective Memory with Stuck-At Errors
  49. Altmetric Badge
    Chapter 48 Two-Sided Error Proximity Oblivious Testing
  50. Altmetric Badge
    Chapter 49 Mirror Descent Based Database Privacy
  51. Altmetric Badge
    Chapter 50 Analysis of k -Means++ for Separable Data
  52. Altmetric Badge
    Chapter 51 A Sharper Local Lemma with Improved Applications
  53. Altmetric Badge
    Chapter 52 Finding Small Sparse Cuts by Random Walk
  54. Altmetric Badge
    Chapter 53 On Deterministic Sketching and Streaming for Sparse Recovery and Norm Estimation
  55. Altmetric Badge
    Chapter 54 A New Upper Bound on the Query Complexity for Testing Generalized Reed-Muller codes
  56. Altmetric Badge
    Chapter 55 A Combination of Testability and Decodability by Tensor Products
  57. Altmetric Badge
    Chapter 56 Extractors for Turing-Machine Sources
Attention for Chapter 21: Improved Inapproximability for TSP
Altmetric Badge

Mentioned by

wikipedia
1 Wikipedia page

Citations

dimensions_citation
5 Dimensions

Readers on

mendeley
5 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.
Chapter title
Improved Inapproximability for TSP
Chapter number 21
Book title
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Published by
Springer, Berlin, Heidelberg, January 2012
DOI 10.1007/978-3-642-32512-0_21
Book ISBNs
978-3-64-232511-3, 978-3-64-232512-0
Authors

Michael Lampis, Lampis, Michael

Mendeley readers

Mendeley readers

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

Geographical breakdown

Country Count As %
Unknown 5 100%

Demographic breakdown

Readers by professional status Count As %
Professor 1 20%
Student > Ph. D. Student 1 20%
Unknown 3 60%
Readers by discipline Count As %
Computer Science 1 20%
Engineering 1 20%
Unknown 3 60%