scientific article; zbMATH DE number 1754594
From MaRDI portal
Publication:4535019
zbMATH Open0986.90082MaRDI QIDQ4535019FDOQ4535019
Authors: Lars Engebretsen, Marek Karpinski 
Publication date: 12 June 2002
Full work available at URL: http://link.springer.de/link/service/series/0558/bibs/2076/20760201
Title of this publication is not available (Why is that?)
Recommendations
- TSP with bounded metrics
- On the Approximation Hardness of Some Generalizations of TSP
- Approximating TSP on metrics with bounded global growth
- On the approximation hardness of dense TSP and other path problems
- A (slightly) improved approximation algorithm for metric TSP
- Approximating the Metric TSP in Linear Time
- Approximating the metric TSP in linear time
- A deterministic better-than-3/2 approximation algorithm for metric TSP
- Truly tight bounds for TSP heuristics
- Approximation hardness of Travelling Salesman via weighted amplifiers
Programming involving graphs or networks (90C35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Abstract computational complexity for mathematical programming problems (90C60)
Cited In (20)
- Hardness of Approximation Results for the Problem of Finding the Stopping Distance in Tanner Graphs
- TSP with bounded metrics
- On the Complexity of the Metric TSP under Stability Considerations
- On the Approximation Hardness of Some Generalizations of TSP
- Approximation algorithms for the maximum Hamiltonian path problem with specified endpoint(s)
- Differential approximation results for the traveling salesman and related problems
- On the approximation hardness of dense TSP and other path problems
- Cooperative TSP
- Restricted common superstring and restricted common supersequence
- Approximation algorithms for some vehicle routing problems
- Polynomial approximation algorithms with performance guarantees: an introduction-by-example
- A $$(1+{\varepsilon })$$ ( 1 + ε ) -Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs
- Estimating the Held-Karp lower bound for the geometric TSP
- When the greedy algorithm fails
- Approximating TSP on metrics with bounded global growth
- Differential approximation results for the traveling salesman problem with distances 1 and 2
- A $(1+\varepsilon)$-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs
- On the \({\mathcal {H}}\)-free extension complexity of the TSP
- Differential approximation of NP-hard problems with equal size feasible solutions
- Affine reductions for LPs and SDPs
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4535019)
