Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(3)
Traveling Salesman Problem
Worst Case Analysis
Travelling Salesman Problem
Related Publications
(1)
Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
Subscribe
Academic
Publications
Worstcase analysis of a new heuristic for the travelling salesman problem
Worstcase analysis of a new heuristic for the travelling salesman problem,N. Christofides
Edit
Worstcase analysis of a new heuristic for the travelling salesman problem
(
Citations: 411
)
BibTex

RIS

RefWorks
Download
N. Christofides
Published in 1976.
Cumulative
Annual
Citation Context
(261)
...Some results of this nature are known (see [
6
, 10, 13, 14]), but there are still many open questions...
Sylvia Boyd
,
et al.
Finding low cost TSP and 2matching solutions using certain halfinteg...
...If we would like the heuristic to run in guaranteed polynomial time, we can approximate the optimal path using Christofides’ heuristic for the symmetric TSP [
19
]...
Stefano Basagni
,
et al.
Coordinated and controlled mobility of multiple sinks for maximizing t...
...Practical implementations of the algorithms will rely on heuristics or on polynomialtime approximation schemes, such as LinKernighan’s [16] or Christofides’ [
17
]...
Marco Pavone
,
et al.
Adaptive and Distributed Algorithms for Vehicle Routing in a Stochasti...
...It was shown by Goemans and Bertsimas [11] that the cost of the minimum cost spanning tree is at most twice the optimal value of the Steiner tree LP relaxation, and hence the minimum cost spanning tree costs at most twice the objective value of any feasible solution to this LP. For the traveling salesman problem, it was shown by Wolsey [30], and independently by Shmoys and Williamson [25], that the Christofides algorithm [
2
] gives a ...
Anke van Zuylen
.
Deterministic Sampling Algorithms for Network Design
...Certainly a more efficient strategy could be designed – a minimum spanning tree gives an approximation factor of two with O(m 2 ) computational cost, while a matching step will give an approximation factor of 3/2 with O(m 3 ) cost [
22
]...
Robert Hummel
,
et al.
Mission design for compressive sensing with mobile robots
Sort by:
Citations
(411)
Finding low cost TSP and 2matching solutions using certain halfinteger subtour vertices
(
Citations: 5
)
Sylvia Boyd
,
Robert Carr
Journal:
Discrete Optimization
, vol. 8, no. 4, pp. 525539, 2011
Coordinated and controlled mobility of multiple sinks for maximizing the lifetime of wireless sensor networks
(
Citations: 1
)
Stefano Basagni
,
Alessio Carosi
,
Chiara Petrioli
,
Cynthia A. Phillips
Journal:
Wireless Networks  WINET
, vol. 17, no. 3, pp. 759778, 2011
Adaptive and Distributed Algorithms for Vehicle Routing in a Stochastic and Dynamic Environment
(
Citations: 2
)
Marco Pavone
,
Emilio Frazzoli
,
Francesco Bullo
Journal:
IEEE Transactions on Automatic Control  IEEE TRANS AUTOMAT CONTR
, vol. 56, no. 6, pp. 12591274, 2011
Deterministic Sampling Algorithms for Network Design
(
Citations: 1
)
Anke van Zuylen
Journal:
Algorithmica
, vol. 60, no. 1, pp. 110151, 2011
Mission design for compressive sensing with mobile robots
Robert Hummel
,
Sameera Poduri
,
Franz Hover
,
Urbashi Mitra
,
Guarav Sukhatme
Conference:
International Conference on Robotics and Automation  ICRA
, pp. 23622367, 2011