Approximation algorithms with constant ratio for general cluster routing problems

Autor: Jian Sun, Qiaoxia Ming, Donglei Du, Gregory Gutin, Xiaoyan Zhang
Rok vydání: 2021
Předmět:
Zdroj: Journal of Combinatorial Optimization. 44:2499-2514
ISSN: 1573-2886
1382-6905
DOI: 10.1007/s10878-021-00772-8
Popis: 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)$$ with a metric cost function c and a partition $$V=C_{1}\cup C_{2}\cdots \cup C_{k}$$ of the vertex set. For a given subset $$V^{'}$$ of V and subset $$E^{'}$$ of E, the task is to find a walk T with minimum cost such that it visits each vertex in $$V^{\prime }$$ exactly once and covers each edge in $$E^{\prime }$$ at least once. Besides, for every $$i\in [k]$$ , all the vertices in $$T\cap 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.
Databáze: OpenAIRE
Externí odkaz: