On PTAS for the Geometric Maximum Connected k-Factor Problem

On PTAS for the Geometric Maximum Connected k-Factor Problem Full article

Journal

Communications in Computer and Information Science
ISSN: 1865-0929

Output data

Year: 2020, Volume: 1145, Pages: 194-205 Pages count : 12 DOI: 10.1007/978-3-030-38603-0_15

Tags

Asymptotically optimal algorithm; Connected k-factor problem; Normed space; NP-hard problem; Polynomial time approximation scheme

Authors

Gimadi E. ^1,2 , Rykov I. ^1,2 , Tsidulko O. ^1,2

Affiliations

1	Sobolev Institute of Mathematics, 4 Acad. Koptyug avenue, Novosibirsk, 630090, Russian Federation
2	Department of Mechanics and Mathematics, Novosibirsk State University, 1 Pirogova Street, Novosibirsk, 630090, Russian Federation

We consider the Connected k-factor problem (k-CFP): given a complete edge-weighted n-vertex graph, the goal is to find a connected k-regular spanning subgraph of maximum or minimum total weight. The problem is called geometric, if the vertices of a graph correspond to a set of points in a normed space (formula presented) and the weight of an edge is the distance between its endpoints. The k-CFP is a natural generalization of the well-known Traveling Salesman Problem, which is equivalent to the 2-CFP. In this paper we complement the known (formula presented)-approximation algorithm for the maximum k-CFP from [Baburin et al., 2007] with an approximation algorithm for the geometric k-CFP, that guarantees a relative error (formula presented). Together these two algorithms form an asymptotically optimal algorithm for the geometric k-CFP with an arbitrary value of k in an arbitrary normed space of fixed dimension d. Finally, the asymptotically optimal algorithm can be easily transformed into a PTAS for the considered geometric problem. © Springer Nature Switzerland AG 2020.

Gimadi E. , Rykov I. , Tsidulko O.
On PTAS for the Geometric Maximum Connected k-Factor Problem
Communications in Computer and Information Science. 2020. V.1145. P.194-205. DOI: 10.1007/978-3-030-38603-0_15 WOS Scopus OpenAlex

Web of science:	WOS:000656909000015
Scopus:	2-s2.0-85078414202
OpenAlex:	W2999513600

Пока нет цитирований