↓ Skip to main content

Automata, Languages and Programming

Overview of attention for book
Automata, Languages and Programming
Springer Science & Business Media

Table of Contents

  1. Altmetric Badge
    Book Overview
  2. Altmetric Badge
    Chapter 1 Algorithms, Games, and the Internet
  3. Altmetric Badge
    Chapter 2 Automata, Circuits, and Hybrids: Facets of Continuous Time
  4. Altmetric Badge
    Chapter 3 Languages, Rewriting Systems, and Verification of Infinite-State Systems
  5. Altmetric Badge
    Chapter 4 Integrating Semantics for Object—Oriented System Models
  6. Altmetric Badge
    Chapter 5 Modelling with Partial Orders — Why and Why Not?
  7. Altmetric Badge
    Chapter 6 Theoretical Aspects of Evolutionary Algorithms
  8. Altmetric Badge
    Chapter 7 Improvements of the Alder—Strassen Bound: Algebras with Nonzero Radical
  9. Altmetric Badge
    Chapter 8 On Generating All Minimal Integer Solutions for a Monotone System of Linear Inequalities
  10. Altmetric Badge
    Chapter 9 Division Is In Uniform TC0
  11. Altmetric Badge
    Chapter 10 A Framework for Index Bulk Loading and Dynamization
  12. Altmetric Badge
    Chapter 11 A Characterization of Temporal Locality and Its Portability across Memory Hierarchies
  13. Altmetric Badge
    Chapter 12 The Complexity of Constructing Evolutionary Trees Using Experiments
  14. Altmetric Badge
    Chapter 13 Hidden Pattern Statistics
  15. Altmetric Badge
    Chapter 14 Combinatorics and Algorithms on Low-Discrepancy Roundings of a Real Sequence
  16. Altmetric Badge
    Chapter 15 All-Pairs Shortest Paths Computation in the BSP Model
  17. Altmetric Badge
    Chapter 16 Approximating the Minimum Spanning Tree Weight in Sublinear Time
  18. Altmetric Badge
    Chapter 17 Approximation Hardness of TSP with Bounded Metrics
  19. Altmetric Badge
    Chapter 18 The RPR 2 Rounding Technique for Semidefinite Programs
  20. Altmetric Badge
    Chapter 19 Approximation Algorithms for Partial Covering Problems
  21. Altmetric Badge
    Chapter 20 On the Online Bin Packing Problem
  22. Altmetric Badge
    Chapter 21 Quick k-Median, k-Center, and Facility Location for Sparse Graphs
  23. Altmetric Badge
    Chapter 22 Parameterized Complexity: Exponential Speed-Up for Planar Graph Problems
  24. Altmetric Badge
    Chapter 23 Subexponential Parameterized Algorithms Collapse the W-Hierarchy
  25. Altmetric Badge
    Chapter 24 Improved Lower Bounds on the Randomized Complexity of Graph Properties
  26. Altmetric Badge
    Chapter 25 New Imperfect Random Source with Applications to Coin-Flipping
  27. Altmetric Badge
    Chapter 26 Recognizing More Unsatisfiable Random 3-SAT Instances Efficiently
  28. Altmetric Badge
    Chapter 27 Weisfeiler-Lehman Refinement Requires at Least a Linear Number of Iterations
  29. Altmetric Badge
    Chapter 28 On Interactive Proofs with a Laconic Prover
  30. Altmetric Badge
    Chapter 29 Quantum Complexities of Ordered Searching, Sorting, and Element Distinctness
  31. Altmetric Badge
    Chapter 30 Lower Bounds in the Quantum Cell Probe Model
  32. Altmetric Badge
    Chapter 31 Axiomatizations for Probabilistic Bisimulation
  33. Altmetric Badge
    Chapter 32 Noninterference for Concurrent Programs
  34. Altmetric Badge
    Chapter 33 Distributed Controller Synthesis for Local Specifications
  35. Altmetric Badge
    Chapter 34 A Distributed Abstract Machine for Safe Ambients
  36. Altmetric Badge
    Chapter 35 Towards Quantitative Verification of Probabilistic Transition Systems
  37. Altmetric Badge
    Chapter 36 Efficient Generation of Plane Triangulations without Repetitions
  38. Altmetric Badge
    Chapter 37 The Longest Common Subsequence Problem for Sequences with Nested Arc Annotations
  39. Altmetric Badge
    Chapter 38 Visibility-Based Pursuit-Evasion in a Polygonal Region by a Searcher
  40. Altmetric Badge
    Chapter 39 A New Method for Balancing Binary Search Trees
  41. Altmetric Badge
    Chapter 40 Permutation Editing and Matching via Embeddings
  42. Altmetric Badge
    Chapter 41 Testing Hypergraph Coloring
  43. Altmetric Badge
    Chapter 42 Total Colorings of Degenerated Graphs
  44. Altmetric Badge
    Chapter 43 Decidable Properties of Graphs of All-Optical Networks
  45. Altmetric Badge
    Chapter 44 Majority Consensus and the Local Majority Rule
  46. Altmetric Badge
    Chapter 45 Solvability of Equations in Free Partially Commutative Groups Is decidable
  47. Altmetric Badge
    Chapter 46 Rational Transformations of Formal Power Series
  48. Altmetric Badge
    Chapter 47 Combinatorics of Three-Interval Exchanges
  49. Altmetric Badge
    Chapter 48 Decision Questions Concerning Semilinearity, Morphisms, and Commutation of Languages
  50. Altmetric Badge
    Chapter 49 The Star Problem in Trace Monoids: Reductions Beyond C4
  51. Altmetric Badge
    Chapter 50 The Trace Coding Problem Is Undecidable
  52. Altmetric Badge
    Chapter 51 Combinatorics of Periods in Strings
  53. Altmetric Badge
    Chapter 52 Minimal Tail-Biting Trellises for Certain Cyclic Block Codes Are Easy to Construct
  54. Altmetric Badge
    Chapter 53 Effective Lossy Queue Languages
  55. Altmetric Badge
    Chapter 54 Model Checking of Unrestricted Hierarchical State Machines
  56. Altmetric Badge
    Chapter 55 Symbolic Trace Analysis of Cryptographic Protocols
  57. Altmetric Badge
    Chapter 56 Tree Automata with One Memory, Set Constraints, and Ping-Pong Protocols
  58. Altmetric Badge
    Chapter 57 Fair Simulation Relations, Parity Games, and State Space Reduction for Büchi Automata
  59. Altmetric Badge
    Chapter 58 Hypergraphs in Model Checking: Acyclicity and Hypertree-Width versus Clique-Width
  60. Altmetric Badge
    Chapter 59 From Finite State Communication Protocols to High-Level Message Sequence Charts
  61. Altmetric Badge
    Chapter 60 Fractional Path Coloring with Applications to WDM Networks
  62. Altmetric Badge
    Chapter 61 Performance Aspects of Distributed Caches Using TTL-Based Consistency
  63. Altmetric Badge
    Chapter 62 Routing in Trees
  64. Altmetric Badge
    Chapter 63 Online Packet Routing on Linear Arrays and Rings
  65. Altmetric Badge
    Chapter 64 Faster Gossiping on Butterflies
  66. Altmetric Badge
    Chapter 65 Realizability and Verification of MSC Graphs
  67. Altmetric Badge
    Chapter 66 Reasoning about Sequential and Branching Behaviours of Message Sequence Graphs
  68. Altmetric Badge
    Chapter 67 A Set-Theoretic Framework for Assume-Guarantee Reasoning
  69. Altmetric Badge
    Chapter 68 Foundations for Circular Compositional Reasoning
  70. Altmetric Badge
    Chapter 69 A PTAS for Minimizing Weighted Completion Time on Uniformly Related Machines
  71. Altmetric Badge
    Chapter 70 The Buffer Minimization Problem for Multiprocessor Scheduling with Conflicts
  72. Altmetric Badge
    Chapter 71 On Minimizing Average Weighted Completion Time of Multiprocessor Tasks with Release Dates
  73. Altmetric Badge
    Chapter 72 On the Approximability of Average Completion Time Scheduling under Precedence Constraints
  74. Altmetric Badge
    Chapter 73 Optimistic Asynchronous Multi-party Contract Signing with Reduced Number of Rounds
  75. Altmetric Badge
    Chapter 74 Information-Theoretic Private Information Retrieval: A Unified Construction
  76. Altmetric Badge
    Chapter 75 Secure Multiparty Computation of Approximations
  77. Altmetric Badge
    Chapter 76 Secure Games with Polynomial Expressions
  78. Altmetric Badge
    Chapter 77 On the Completeness of Arbitrary Selection Strategies for Paramodulation
  79. Altmetric Badge
    Chapter 78 An Axiomatic Approach to Metareasoning on Nominal Algebras in HOAS
  80. Altmetric Badge
    Chapter 79 Knuth-Bendix Constraint Solving Is NP-Complete
  81. Altmetric Badge
    Chapter 80 Amalgamation in CASL via Enriched Signatures
  82. Altmetric Badge
    Chapter 81 Lower Bounds for the Weak Pigeonhole Principle Beyond Resolution
  83. Altmetric Badge
    Chapter 82 Time and Space Bounds for Reversible Simulation
  84. Altmetric Badge
    Chapter 83 Finite-State Dimension
  85. Altmetric Badge
    Chapter 84 The Complexity of Computing the Size of an Interval
  86. Altmetric Badge
    Chapter 85 Communication Gap for Finite Memory Devices
  87. Altmetric Badge
    Chapter 86 Separating Quantum and Classical Learning
Attention for Chapter 17: Approximation Hardness of TSP with Bounded Metrics
Altmetric Badge

Mentioned by

q&a
1 Q&A thread

Readers on

mendeley
18 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
Approximation Hardness of TSP with Bounded Metrics
Chapter number 17
Book title
Automata, Languages and Programming
Published by
Springer, Berlin, Heidelberg, July 2001
DOI 10.1007/3-540-48224-5_17
Book ISBNs
978-3-54-042287-7, 978-3-54-048224-6
Authors

Lars Engebretsen, Marek Karpinski

Timeline

Login to access the full chart related to this output.

If you don’t have an account, click here to discover Explorer

Mendeley readers

Mendeley readers

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

Geographical breakdown

Country Count As %
Russia 2 11%
United Kingdom 1 6%
Unknown 15 83%

Demographic breakdown

Readers by professional status Count As %
Researcher 4 22%
Student > Bachelor 3 17%
Student > Master 3 17%
Student > Ph. D. Student 3 17%
Other 1 6%
Other 2 11%
Unknown 2 11%
Readers by discipline Count As %
Computer Science 13 72%
Mathematics 2 11%
Physics and Astronomy 1 6%
Unknown 2 11%