Back to Search
Start Over
An improved upper bound for the TSP in cubic 3-edge-connected graphs
- Source :
- Operations Research Letters. 33:467-474
- Publication Year :
- 2005
- Publisher :
- Elsevier BV, 2005.
-
Abstract
- We consider the travelling salesman problem (TSP) problem on (the metric completion of) 3-edge-connected cubic graphs. These graphs are interesting because of the connection between their optimal solutions and the subtour elimination LP relaxation. Our main result is an approximation algorithm better than the 3/2-approximation algorithm for TSP in general.
- Subjects :
- Discrete mathematics
Applied Mathematics
Computer Science::Neural and Evolutionary Computation
MathematicsofComputing_NUMERICALANALYSIS
Approximation algorithm
Computer Science::Computational Complexity
Management Science and Operations Research
Upper and lower bounds
Travelling salesman problem
Industrial and Manufacturing Engineering
Connection (mathematics)
Combinatorics
Linear programming relaxation
Metric (mathematics)
Cubic graph
Regular graph
Computer Science::Data Structures and Algorithms
Software
MathematicsofComputing_DISCRETEMATHEMATICS
Mathematics
Subjects
Details
- ISSN :
- 01676377
- Volume :
- 33
- Database :
- OpenAIRE
- Journal :
- Operations Research Letters
- Accession number :
- edsair.doi...........2cd3fc9ff4f4debdb0dd0109b94dd554
- Full Text :
- https://doi.org/10.1016/j.orl.2004.09.005