Publication | Closed Access
The traveling salesman problem
105
Citations
32
References
2012
Year
Unknown Venue
Mathematical ProgrammingEngineeringComputational ComplexityArbitrary Metric SpaceDiscrete OptimizationOperations ResearchTraveling Salesman ProblemSalesman ProblemCombinatorial OptimizationApproximation TheoryMechanism DesignLinear OptimizationCombinatorial ProblemComputer ScienceInteger ProgrammingRoute PlanningOptimization ProblemOptimal TourVehicle Routing ProblemHeuristic Search
The Traveling Salesman Problem (TSP) is among the most famous NP-hard optimization problems. We design for this problem a randomized polynomial-time algorithm that computes a (1+µ)-approximation to the optimal tour, for any fixed µ>0, in TSP instances that form an arbitrary metric space with bounded intrinsic dimension.
| Year | Citations | |
|---|---|---|
Page 1
Page 1