On PTAS for the Geometric Maximum Connected k-Factor Problem

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review


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.

Original languageEnglish
Title of host publicationOptimization and Applications - 10th International Conference, OPTIMA 2019, Revised Selected Papers
EditorsMilojica Jaćimović, Michael Khachay, Vlasta Malkova, Mikhail Posypkin
PublisherSpringer Gabler
Number of pages12
ISBN (Print)9783030386023
Publication statusPublished - 1 Jan 2020
Event10th International Conference on Optimization and Applications, OPTIMA 2019 - Petrovac, Montenegro
Duration: 30 Sep 20194 Oct 2019

Publication series

NameCommunications in Computer and Information Science
Volume1145 CCIS
ISSN (Print)1865-0929
ISSN (Electronic)1865-0937


Conference10th International Conference on Optimization and Applications, OPTIMA 2019


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

Fingerprint Dive into the research topics of 'On PTAS for the Geometric Maximum Connected k-Factor Problem'. Together they form a unique fingerprint.

Cite this