A domination algorithm for \0,1\-instances of the travelling salesman problem

Abstract: We present an approximation algorithm for

0, 1

-instances of the travelling salesman problem which performs well with respect to combinatorial dominance. More precisely, we give a polynomial-time algorithm which has domination ratio

1 - n^{- 1 / 29}

. In other words, given a

0, 1

-edge-weighting of the complete graph

K_{n}

on

n

vertices, our algorithm outputs a Hamilton cycle

H^{*}

of

K_{n}

with the following property: the proportion of Hamilton cycles of

K_{n}

whose weight is smaller than that of

H^{*}

is at most

n^{- 1 / 29}

. Our analysis is based on a martingale approach. Previously, the best result in this direction was a polynomial-time algorithm with domination ratio

1 / 2 - o (1)

for arbitrary edge-weights. We also prove a hardness result showing that, if the Exponential Time Hypothesis holds, there exists a constant

C

such that

n^{- 1 / 29}

cannot be replaced by

e x p (- (l o g n)^{C})

in the result above.

Recommendations

Cites work

Cited in

(3)

This page was built for publication: A domination algorithm for \(\{0,1\}\)-instances of the travelling salesman problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2811158)