1
$\begingroup$

Is there a way to find very rough minimum and maximum estimates for the travelling salesman problem? The estimates only need to be within the roughly same magnitude, but it's important that the minimum estimate is lower (or equal) to the actual distance and that the maximum estimate is higher (or equal) to the actual distance.

EDIT: Metric TSP unfortunately does not apply. To add some context: I'm searching for non-dominated fronts (pareto fronts) for a Multiobjective TSP, e.g. optimizing for multiple variables like travel time and distance. I'm using NSGA-II which requires an upper and lower bound for each objective function, which translates into rough estimates for single-objective TSP, with the constraint that the upper estimate has to be higher than the real max distance and vice versa.

|cite|improve this question
$\endgroup$
  • $\begingroup$ How rough? "Within roughly the same magnitude" gives a lot of leeway. For example, the length of the optimal tour is at least the sum of the lightest edge from each vertex and at most the sum of the heaviest edges. $\endgroup$ – David Richerby Apr 26 '16 at 20:48
  • $\begingroup$ Is there a similar approximation for the longest tour? I've looked at different papers but they're all aiming for accuracy; I'm looking for something within a factor of 10~100 that's relatively fast and easy to implement $\endgroup$ – tsorn Apr 27 '16 at 2:50
  • $\begingroup$ The 2-approximation algorithm mentioned in Bittu's answer runs in time $O(n\log n)$ (or faster). $\endgroup$ – Yuval Filmus Apr 27 '16 at 9:01
  • $\begingroup$ If you are solving practical instances then you might find the following book by leading experts in the area to be quite useful: press.princeton.edu/TOCs/c8451.html $\endgroup$ – Denis Pankratov Apr 27 '16 at 15:02
2
$\begingroup$

It is conjectured (but unproven) that the Held-Karp relaxation (not the Held-Karp algorithm) has an integrality ratio of 4/3 (on metric TSP). Various proofs exists for even better bounds if some assumptions are made.

Practically it performs even better, gaps of ~2% are normal, and there is a lot of literature about adding more cuts that get that gap (typically) a fair way below 1%, but that would not fit with your goal of "fast and easy to implement" anymore. Just the basic degree constraints + lazy sub-tour elimination is, when using an existing LP solver, both fast and easy, and a lot better than taking one of the well known upper bounds and dividing them by their approximation ratio (which tends to be give terrible results, because they typically approximate much better than their worst case, resulting in an overly optimistic lower bound).

|cite|improve this answer
$\endgroup$
1
$\begingroup$

There are efficient constant-factor approximation algorithms for your problem, which are described (for example) on the Wikipedia page. Such an approximation algorithm usually returns a tour whose value is at most $C$ times the value optimal tour (and at least the value of the optimal tour), where $C$ is some small constant (for the Christofides algorithm, $C = 1.5$).

|cite|improve this answer
$\endgroup$
1
$\begingroup$

You can look on this lecture notes: TSP-Aprrox

If your Problem is a metric TSP than there is 2-approx (Using Minimum Spanning Tree) and 1.5-approx algorithm for minimum TSP.

If your problem is not metric then there is no constant- approx algorithm for minimum TSP

Max TSP is as hard as Min TSP and again for Metric TSP there are constant approx Algorithms. You can check for algo here

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.