A LP-based Approximation Algorithm for generalized Traveling Salesperson Path Problem

被引：0

作者：

Sun, Jian ^{[1
]}

Gutin, Gregory ^{[2
]}

Zhang, Xiaoyan ^{[3
,4
]}

机构：

[1] Beijing Univ Technol, Dept Operat Res & Informat Engn, Beijing 100124, Peoples R China

[2] Royal Holloway Univ London, Dept Comp Sci, Egham TW20 0EX, Surrey, England

[3] Nanjing Normal Univ, Sch Math Sci, Nanjing 210023, Jiangsu, Peoples R China

[4] Nanjing Normal Univ, Inst Math, Nanjing 210023, Jiangsu, Peoples R China

来源：

COMBINATORIAL OPTIMIZATION AND APPLICATIONS, COCOA 2021 | 2021年 / 13135卷

基金：

中国国家自然科学基金;

关键词：

Hamiltonian path; LP rounding; Generalized TSP path problem; Approximation algorithm;

D O I：

10.1007/978-3-030-92681-6_50

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Hamiltonian path problem is one of the fundamental problems in graph theory, the aim is to find a path in the graph that visits each vertex exactly once. In this paper, we consider a generalizedized problem: given a complete weighted undirected graph G = (V, E, c), two specified vertices s and t, let V' and E' be subsets of V and E, respectively. We aim to find an s-t path which visits each vertex of V' and each edge of E' exactly once with minimum cost. Based on LP rounding technique, we propose a 9-root 33/2-approximation algorithm.

引用

页码：641 / 652

页数：12