Covering a tree with rooted subtrees -parameterized and approximation algorithms

Lin Chen, Daniel Marx

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

17 Scopus citations

Abstract

We consider the multiple traveling salesman problem on a weighted tree. In this problem there are m salesmen located at the root initially. Each of them will visit a subset of vertices and return to the root. The goal is to assign a tour to every salesman such that every vertex is visited and the longest tour among all salesmen is minimized. The problem is equivalent to the subtree cover problem, in which we cover a tree with rooted subtrees such that the weight of the maximum weighted subtree is minimized. The classical machine scheduling problem can be viewed as a special case of our problem when the given tree is a star. We provide approximation and parameterized algorithms for this problem. We first present a PTAS (Polynomial Time Approximation Scheme). We then observe that, the problem remains NP-hard even if tree height and edge weight are constant, and present an FPT algorithm for this problem parameterized by the largest tour length. To achieve the FPT algorithm, we first formulate the problem as an integer linear program having a certain "tree-fold" structure. Then we show that an ILP with such a structure is FPT, which is a generalization of an earlier FPT result for n-fold integer programming by Hemmecke, Onn and Romanchuk [5]. This extension of n-fold ILP may be of independent interest.

Original languageEnglish
Title of host publication29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018
EditorsArtur Czumaj
PublisherAssociation for Computing Machinery
Pages2801-2820
Number of pages20
ISBN (Electronic)9781611975031
DOIs
StatePublished - 2018
Event29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018 - New Orleans, United States
Duration: Jan 7 2018Jan 10 2018

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Conference

Conference29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018
Country/TerritoryUnited States
CityNew Orleans
Period01/7/1801/10/18

Keywords

  • Approximation schemes
  • Fixed parameter tractable
  • Integer programming
  • Scheduling

Fingerprint

Dive into the research topics of 'Covering a tree with rooted subtrees -parameterized and approximation algorithms'. Together they form a unique fingerprint.

Cite this