Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
On PTAS for the Geometric Maximum Connected k-Factor Problem. / Gimadi, Edward; Rykov, Ivan; Tsidulko, Oxana.
Optimization and Applications - 10th International Conference, OPTIMA 2019, Revised Selected Papers. ed. / Milojica Jaćimović; Michael Khachay; Vlasta Malkova; Mikhail Posypkin. Springer Gabler, 2020. p. 194-205 (Communications in Computer and Information Science; Vol. 1145 CCIS).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
}
TY - GEN
T1 - On PTAS for the Geometric Maximum Connected k-Factor Problem
AU - Gimadi, Edward
AU - Rykov, Ivan
AU - Tsidulko, Oxana
N1 - Publisher Copyright: © Springer Nature Switzerland AG 2020. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.
PY - 2020/1/1
Y1 - 2020/1/1
N2 - 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.
AB - 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.
KW - Asymptotically optimal algorithm
KW - Connected k-factor problem
KW - Normed space
KW - NP-hard problem
KW - Polynomial time approximation scheme
UR - http://www.scopus.com/inward/record.url?scp=85078414202&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-38603-0_15
DO - 10.1007/978-3-030-38603-0_15
M3 - Conference contribution
AN - SCOPUS:85078414202
SN - 9783030386023
T3 - Communications in Computer and Information Science
SP - 194
EP - 205
BT - Optimization and Applications - 10th International Conference, OPTIMA 2019, Revised Selected Papers
A2 - Jaćimović, Milojica
A2 - Khachay, Michael
A2 - Malkova, Vlasta
A2 - Posypkin, Mikhail
PB - Springer Gabler
T2 - 10th International Conference on Optimization and Applications, OPTIMA 2019
Y2 - 30 September 2019 through 4 October 2019
ER -
ID: 23262750