@inproceedings{4b4995d3a12447609d70e679a958181f,
title = "On PTAS for the Geometric Maximum Connected k-Factor Problem",
abstract = "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.",
keywords = "Asymptotically optimal algorithm, Connected k-factor problem, Normed space, NP-hard problem, Polynomial time approximation scheme",
author = "Edward Gimadi and Ivan Rykov and Oxana Tsidulko",
year = "2020",
month = "1",
day = "1",
doi = "10.1007/978-3-030-38603-0_15",
language = "English",
isbn = "9783030386023",
series = "Communications in Computer and Information Science",
publisher = "Springer Gabler",
pages = "194--205",
editor = "Milojica Jaćimović and Michael Khachay and Vlasta Malkova and Mikhail Posypkin",
booktitle = "Optimization and Applications - 10th International Conference, OPTIMA 2019, Revised Selected Papers",
address = "Germany",
}