A 3/2-approximation algorithm for the multiple Hamiltonian path problem with no prefixed endpoints

Jun Wu; Yongxi Cheng; Zhen Yang; Feng Chu

doi:10.1016/j.orl.2023.07.003

A 3/2-approximation algorithm for the multiple Hamiltonian path problem with no prefixed endpoints

Jun Wu
, Yongxi Cheng
, Zhen Yang
, Feng Chu

管理学院

Xi'an Jiaotong University
Université Paris-Saclay

科研成果: 期刊稿件 › 文章 › 同行评审

4 引用（Scopus）

摘要

We study the multiple Hamiltonian path problem (MHPP) defined on a complete undirected graph G with n vertices. The edge weights of G are non-negative and satisfy the triangle inequality. The MHPP seeks to find a collection of k paths with exactly one visit to each vertex of G with the minimum total edge weight, where endpoints of the paths are not prefixed. We present a 3/2-approximation algorithm for MHPP with time complexity O(n³) for arbitrary k≥1.

源语言	英语
页（从-至）	473-476
页数	4
期刊	Operations Research Letters
卷	51
期	5
DOI	https://doi.org/10.1016/j.orl.2023.07.003
出版状态	已出版 - 9月 2023

访问文件

10.1016/j.orl.2023.07.003

其它文件与链接

链接到 Scopus 的出版物

引用此

@article{ef41589b7a234f5c8fb080ee224143dc,

title = "A 3/2-approximation algorithm for the multiple Hamiltonian path problem with no prefixed endpoints",

abstract = "We study the multiple Hamiltonian path problem (MHPP) defined on a complete undirected graph G with n vertices. The edge weights of G are non-negative and satisfy the triangle inequality. The MHPP seeks to find a collection of k paths with exactly one visit to each vertex of G with the minimum total edge weight, where endpoints of the paths are not prefixed. We present a 3/2-approximation algorithm for MHPP with time complexity O(n3) for arbitrary k≥1.",

keywords = "Approximation algorithm, Christofides heuristic, Multiple Hamiltonian path problem",

author = "Jun Wu and Yongxi Cheng and Zhen Yang and Feng Chu",

note = "Publisher Copyright: {\textcopyright} 2023 Elsevier B.V.",

year = "2023",

month = sep,

doi = "10.1016/j.orl.2023.07.003",

language = "英语",

volume = "51",

pages = "473--476",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

number = "5",

}

TY - JOUR

T1 - A 3/2-approximation algorithm for the multiple Hamiltonian path problem with no prefixed endpoints

AU - Wu, Jun

AU - Cheng, Yongxi

AU - Yang, Zhen

AU - Chu, Feng

PY - 2023/9

Y1 - 2023/9

N2 - We study the multiple Hamiltonian path problem (MHPP) defined on a complete undirected graph G with n vertices. The edge weights of G are non-negative and satisfy the triangle inequality. The MHPP seeks to find a collection of k paths with exactly one visit to each vertex of G with the minimum total edge weight, where endpoints of the paths are not prefixed. We present a 3/2-approximation algorithm for MHPP with time complexity O(n3) for arbitrary k≥1.

AB - We study the multiple Hamiltonian path problem (MHPP) defined on a complete undirected graph G with n vertices. The edge weights of G are non-negative and satisfy the triangle inequality. The MHPP seeks to find a collection of k paths with exactly one visit to each vertex of G with the minimum total edge weight, where endpoints of the paths are not prefixed. We present a 3/2-approximation algorithm for MHPP with time complexity O(n3) for arbitrary k≥1.

KW - Approximation algorithm

KW - Christofides heuristic

KW - Multiple Hamiltonian path problem

UR - https://www.scopus.com/pages/publications/85166185757

U2 - 10.1016/j.orl.2023.07.003

DO - 10.1016/j.orl.2023.07.003

M3 - 文章

AN - SCOPUS:85166185757

SN - 0167-6377

VL - 51

SP - 473

EP - 476

JO - Operations Research Letters

JF - Operations Research Letters

IS - 5

ER -

A 3/2-approximation algorithm for the multiple Hamiltonian path problem with no prefixed endpoints

摘要

访问文件

其它文件与链接

学术指纹

引用此