On PTAS for the Geometric Maximum Connected k-Factor Problem

Результат исследования: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаярецензирование

Аннотация

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.

Язык оригиналаанглийский
Название основной публикацииOptimization and Applications - 10th International Conference, OPTIMA 2019, Revised Selected Papers
РедакторыMilojica Jaćimović, Michael Khachay, Vlasta Malkova, Mikhail Posypkin
ИздательSpringer Gabler
Страницы194-205
Число страниц12
ISBN (печатное издание)9783030386023
DOI
СостояниеОпубликовано - 1 янв 2020
Событие10th International Conference on Optimization and Applications, OPTIMA 2019 - Petrovac, Черногория
Продолжительность: 30 сен 20194 окт 2019

Серия публикаций

НазваниеCommunications in Computer and Information Science
Том1145 CCIS
ISSN (печатное издание)1865-0929
ISSN (электронное издание)1865-0937

Конференция

Конференция10th International Conference on Optimization and Applications, OPTIMA 2019
СтранаЧерногория
ГородPetrovac
Период30.09.201904.10.2019

Fingerprint Подробные сведения о темах исследования «On PTAS for the Geometric Maximum Connected k-Factor Problem». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать

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