Slightly Improved Upper Bound on the Integrality Ratio for the $s-t$ Path TSP

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.

Slightly Improved Upper Bound on the Integrality Ratio for the $s - t$ Path TSP

文献摘要

讨论

讲解博客

AI智能校验

Slightly Improved Upper Bound on the Integrality Ratio for the $s - t$ Path TSP

文献摘要

讨论

讲解博客

AI智能校验

Slightly Improved Upper Bound on the Integrality Ratio for the s−ts−t Path TSP

文献摘要

讨论

|讲解博客

|AI智能校验

Slightly Improved Upper Bound on the Integrality Ratio for the s−ts−t Path TSP

文献摘要

讨论

|讲解博客

|AI智能校验

Slightly Improved Upper Bound on the Integrality Ratio for the $s - t$ Path TSP

讲解博客

AI智能校验

Slightly Improved Upper Bound on the Integrality Ratio for the $s - t$ Path TSP

讲解博客

AI智能校验