Approximation hardness of min-max tree covers

Zhou Xu, Qi Wen

Research output: Journal article publicationJournal articleAcademic researchpeer-review

21 Citations (Scopus)

Abstract

We prove the first inapproximability bounds to study approximation hardness for a min-max k-tree cover problem and its variants. The problem is to find a set of k trees to cover vertices of a given graph with metric edge weights, so as to minimize the maximum total edge weight of any of the k trees. Our technique can also be applied to improve inapproximability bounds for min-max problems that use other covering objectives, such as stars, paths, and tours.
Original languageEnglish
Pages (from-to)169-173
Number of pages5
JournalOperations Research Letters
Volume38
Issue number3
DOIs
Publication statusPublished - 1 May 2010

Keywords

  • Inapproximability bound
  • Min-max
  • Tree covers
  • Vehicle routing

ASJC Scopus subject areas

  • Software
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering
  • Applied Mathematics

Cite this