Anzeige
Erschienen in:
25.06.2021
Approximation algorithms with constant ratio for general cluster routing problems
Erschienen in: Journal of Combinatorial Optimization | Ausgabe 4/2022
EinloggenAktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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)\) 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.