Approximation algorithms with constant ratio for general cluster routing problems

Xiaoyan Zhang (), Donglei Du (), Gregory Gutin (), Qiaoxia Ming and Jian Sun ()
Additional contact information
Xiaoyan Zhang: Nanjing Normal University
Donglei Du: University of New Brunswick
Gregory Gutin: University of London
Qiaoxia Ming: Nanjing Normal University
Jian Sun: Beijing University of Technology

Journal of Combinatorial Optimization, 2022, vol. 44, issue 4, No 19, 2499-2514

Abstract: Abstract Due to their ubiquity and extensive applications, graph routing problems have been widely studied in the fields of operations research, computer science and engineering. An important example of a routing problem is the traveling salesman problem. In this paper, we consider two variants of the general cluster routing problem. In these variants, we are given a complete undirected graph $$G=(V,E)$$ G = ( V , E ) with a metric cost function c and a partition $$V=C_{1}\cup C_{2}\cdots \cup C_{k}$$ V = C 1 ∪ C 2 ⋯ ∪ C k of the vertex set. For a given subset $$V^{'}$$ V ′ of V and subset $$E^{'}$$ E ′ of E, the task is to find a walk T with minimum cost such that it visits each vertex in $$V^{\prime }$$ V ′ exactly once and covers each edge in $$E^{\prime }$$ E ′ at least once. Besides, for every $$i\in [k]$$ i ∈ [ k ] , all the vertices in $$T\cap C_i$$ T ∩ C i are required to be visited consecutively in T. We design two combinatorial approximation algorithms with ratios 21/11 and 2.75 for the two variants, respectively; both ratios match the approximation ratios for the corresponding variants of the cluster traveling salesman problem, a special case of general cluster routing problem.

Keywords: Graph routing problem; Traveling salesman problem; Combinatorial approximation algorithm; General cluster routing problem (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-021-00772-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:44:y:2022:i:4:d:10.1007_s10878-021-00772-8

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-021-00772-8

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().