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

共 42 条

[21] 3-Approximation algorithm for a two depot, heterogeneous traveling salesman problem
Yadlapalli, Sai
Rathinam, Sivakumar
Darbha, Swaroop
OPTIMIZATION LETTERS, 2012, 6 (01) : 141 - 152
[22] An improved approximation algorithm for the minimum 3-path partition problem
Chen, Yong
Goebel, Randy
Lin, Guohui
Su, Bing
Xu, Yao
Zhang, An
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2019, 38 (01) : 150 - 164
[23] An improved approximation algorithm for the minimum 3-path partition problem
Yong Chen
Randy Goebel
Guohui Lin
Bing Su
Yao Xu
An Zhang
Journal of Combinatorial Optimization, 2019, 38 : 150 - 164
[24] An Improved Approximation Algorithm for the s-t Path Movement Problem
Jindaluang, Wattana
Chawachat, Jakarin
Chouvatut, Varin
Fakcharoenphol, Jittat
Kantabutra, Sanpawat
CHIANG MAI JOURNAL OF SCIENCE, 2017, 44 (01): : 279 - 286
[25] An Approximation Algorithm for Shortest Path Based on the Hierarchical Networks
Ayeh, Mensah Dennis Nii
Gao, Hui
Chen, Duanbing
INFORMATION AND COMMUNICATION TECHNOLOGY FOR INTELLIGENT SYSTEMS (ICTIS 2017) - VOL 2, 2018, 84 : 461 - 472
[26] A (1-1/e)-approximation algorithm for the generalized assignment problem
Nutov, Z
Beniaminy, I
Yuster, R
OPERATIONS RESEARCH LETTERS, 2006, 34 (03) : 283 - 288
[27] WHEN TREES COLLIDE - AN APPROXIMATION ALGORITHM FOR THE GENERALIZED STEINER PROBLEM ON NETWORKS
AGRAWAL, A
KLEIN, P
RAVI, R
SIAM JOURNAL ON COMPUTING, 1995, 24 (03) : 440 - 456
[28] A 3/2-Approximation Algorithm for Multiple Depot Multiple Traveling Salesman Problem
Xu, Zhou
Rodrigues, Brian
ALGORITHM THEORY - SWAT 2010, PROCEEDINGS, 2010, 6139 : 127 - +
[29] Approximation Algorithm for the Minimum Connected k-Path Vertex Cover Problem
Li, Xiaosong
Zhang, Zhao
Huang, Xiaohui
COMBINATORIAL OPTIMIZATION AND APPLICATIONS (COCOA 2014), 2014, 8881 : 764 - 771
[30] A faster 2-approximation algorithm for the minmax p-traveling salesmen problem on a tree
Nagamochi, H
Okada, K
DISCRETE APPLIED MATHEMATICS, 2004, 140 (1-3) : 103 - 114

← 1 2 3 4 5 →