Standard

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 proceedingConference contributionResearchpeer-review

Harvard

Gimadi, E, Rykov, I & Tsidulko, O 2020, On PTAS for the Geometric Maximum Connected k-Factor Problem. in M Jaćimović, M Khachay, V Malkova & M Posypkin (eds), Optimization and Applications - 10th International Conference, OPTIMA 2019, Revised Selected Papers. Communications in Computer and Information Science, vol. 1145 CCIS, Springer Gabler, pp. 194-205, 10th International Conference on Optimization and Applications, OPTIMA 2019, Petrovac, Montenegro, 30.09.2019. https://doi.org/10.1007/978-3-030-38603-0_15

APA

Gimadi, E., Rykov, I., & Tsidulko, O. (2020). On PTAS for the Geometric Maximum Connected k-Factor Problem. In M. Jaćimović, M. Khachay, V. Malkova, & M. Posypkin (Eds.), Optimization and Applications - 10th International Conference, OPTIMA 2019, Revised Selected Papers (pp. 194-205). (Communications in Computer and Information Science; Vol. 1145 CCIS). Springer Gabler. https://doi.org/10.1007/978-3-030-38603-0_15

Vancouver

Gimadi E, Rykov I, Tsidulko O. On PTAS for the Geometric Maximum Connected k-Factor Problem. In Jaćimović M, Khachay M, Malkova V, Posypkin M, editors, Optimization and Applications - 10th International Conference, OPTIMA 2019, Revised Selected Papers. Springer Gabler. 2020. p. 194-205. (Communications in Computer and Information Science). doi: 10.1007/978-3-030-38603-0_15

Author

Gimadi, Edward ; Rykov, Ivan ; Tsidulko, Oxana. / On PTAS for the Geometric Maximum Connected k-Factor Problem. Optimization and Applications - 10th International Conference, OPTIMA 2019, Revised Selected Papers. editor / Milojica Jaćimović ; Michael Khachay ; Vlasta Malkova ; Mikhail Posypkin. Springer Gabler, 2020. pp. 194-205 (Communications in Computer and Information Science).

BibTeX

@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",
note = "Publisher Copyright: {\textcopyright} Springer Nature Switzerland AG 2020. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.; 10th International Conference on Optimization and Applications, OPTIMA 2019 ; Conference date: 30-09-2019 Through 04-10-2019",
year = "2020",
month = jan,
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{\'c}imovi{\'c} and Michael Khachay and Vlasta Malkova and Mikhail Posypkin",
booktitle = "Optimization and Applications - 10th International Conference, OPTIMA 2019, Revised Selected Papers",
address = "Germany",

}

RIS

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