Skip to content
Back to outputs

Weighted amplifiers and inapproximability results for Travelling Salesman problem

Research output: Contribution to journal › Article › peer-review

Standard

Weighted amplifiers and inapproximability results for Travelling Salesman problem. / Chlebík, Miroslav; Chlebikova, Janka.

In: Journal of Combinatorial Optimisation, 19.10.2020.

Research output: Contribution to journal › Article › peer-review

Harvard

Chlebík, M & Chlebikova, J 2020, 'Weighted amplifiers and inapproximability results for Travelling Salesman problem', Journal of Combinatorial Optimisation. https://doi.org/10.1007/s10878-020-00659-0

APA

Chlebík, M., & Chlebikova, J. (2020). Weighted amplifiers and inapproximability results for Travelling Salesman problem. Journal of Combinatorial Optimisation. https://doi.org/10.1007/s10878-020-00659-0

Vancouver

Chlebík M, Chlebikova J. Weighted amplifiers and inapproximability results for Travelling Salesman problem. Journal of Combinatorial Optimisation. 2020 Oct 19. https://doi.org/10.1007/s10878-020-00659-0

Author

Chlebík, Miroslav ; Chlebikova, Janka. / Weighted amplifiers and inapproximability results for Travelling Salesman problem. In: Journal of Combinatorial Optimisation. 2020.

Bibtex

@article{a41060a1aaf54a02864c413ffbe2dabd,
title = "Weighted amplifiers and inapproximability results for Travelling Salesman problem",
abstract = "The expander graph constructions and their variants are the main tool used in gap preserving reductions to prove approximation lower bounds of combinatorial optimisation problems. In this paper we introduce the weighted amplifiers and weighted low occurrence of CONSTRAINT SATISFACTION problems as intermediate steps in the NP-hard gap reductions. Allowing the weights in intermediate problems is rather natural for the edge-weighted problems as TRAVELLING SALESMAN or STEINER TREE. We demonstrate the technique for TRAVELLING SALESMAN and use the parametrised weighted amplifiers in the gap reductions to allow more flexibility in fine-tuning their expanding parameters. The purpose of this paper is to point out effectiveness of these ideas, rather than to optimise the expander{\textquoteright}s parameters. Nevertheless, we show that already slight improvement of known expander values modestly improve the current best approximation hardness value for TSP from 123/122 (Karpinski et al., 2015) to 117/116 . This provides a new motivation for study of expanding properties of random graphs in order to improve approximation lower bounds of TSP and other edge-weighted optimisation problems.",
keywords = "Travelling Salesman Problem, Approximation hardness 1",
author = "Miroslav Chleb{\'i}k and Janka Chlebikova",
year = "2020",
month = oct,
day = "19",
doi = "10.1007/s10878-020-00659-0",
language = "English",
journal = "Journal of Combinatorial Optimisation",
issn = "1382-6905",
publisher = "Springer Netherlands",

}

RIS

TY - JOUR

T1 - Weighted amplifiers and inapproximability results for Travelling Salesman problem

AU - Chlebík, Miroslav

AU - Chlebikova, Janka

PY - 2020/10/19

Y1 - 2020/10/19

N2 - The expander graph constructions and their variants are the main tool used in gap preserving reductions to prove approximation lower bounds of combinatorial optimisation problems. In this paper we introduce the weighted amplifiers and weighted low occurrence of CONSTRAINT SATISFACTION problems as intermediate steps in the NP-hard gap reductions. Allowing the weights in intermediate problems is rather natural for the edge-weighted problems as TRAVELLING SALESMAN or STEINER TREE. We demonstrate the technique for TRAVELLING SALESMAN and use the parametrised weighted amplifiers in the gap reductions to allow more flexibility in fine-tuning their expanding parameters. The purpose of this paper is to point out effectiveness of these ideas, rather than to optimise the expander’s parameters. Nevertheless, we show that already slight improvement of known expander values modestly improve the current best approximation hardness value for TSP from 123/122 (Karpinski et al., 2015) to 117/116 . This provides a new motivation for study of expanding properties of random graphs in order to improve approximation lower bounds of TSP and other edge-weighted optimisation problems.

AB - The expander graph constructions and their variants are the main tool used in gap preserving reductions to prove approximation lower bounds of combinatorial optimisation problems. In this paper we introduce the weighted amplifiers and weighted low occurrence of CONSTRAINT SATISFACTION problems as intermediate steps in the NP-hard gap reductions. Allowing the weights in intermediate problems is rather natural for the edge-weighted problems as TRAVELLING SALESMAN or STEINER TREE. We demonstrate the technique for TRAVELLING SALESMAN and use the parametrised weighted amplifiers in the gap reductions to allow more flexibility in fine-tuning their expanding parameters. The purpose of this paper is to point out effectiveness of these ideas, rather than to optimise the expander’s parameters. Nevertheless, we show that already slight improvement of known expander values modestly improve the current best approximation hardness value for TSP from 123/122 (Karpinski et al., 2015) to 117/116 . This provides a new motivation for study of expanding properties of random graphs in order to improve approximation lower bounds of TSP and other edge-weighted optimisation problems.

KW - Travelling Salesman Problem

KW - Approximation hardness 1

U2 - 10.1007/s10878-020-00659-0

DO - 10.1007/s10878-020-00659-0

M3 - Article

JO - Journal of Combinatorial Optimisation

JF - Journal of Combinatorial Optimisation

SN - 1382-6905

ER -

ID: 22727255