Slightly improved upper bound on the integrality ratio for the s−t Path TSP
| Autor: | Xianghui Zhong |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
021103 operations research
Applied Mathematics 0211 other engineering and technologies 02 engineering and technology Auxiliary function Management Science and Operations Research 01 natural sciences Upper and lower bounds Industrial and Manufacturing Engineering Linear programming relaxation Combinatorics 010104 statistics & probability Path (graph theory) Metric (mathematics) 0101 mathematics Software Mathematics |
| Zdroj: | Operations Research Letters. 48:627-629 |
| ISSN: | 0167-6377 |
| DOI: | 10.1016/j.orl.2020.07.015 |
| Popis: | In this paper we investigate the integrality ratio of the standard LP relaxation for the Metric s − t Path TSP . We make a near-optimal choice for an auxiliary function used in the analysis of Traub and Vygen which leads to an improved upper bound on the integrality ratio of 1.5273. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect