𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Approximation hardness of min–max tree covers

✍ Scribed by Zhou Xu; Qi Wen

Publisher
Elsevier Science
Year
2010
Tongue
English
Weight
367 KB
Volume
38
Category
Article
ISSN
0167-6377

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

Min–max tree covers of graphs
Min–max tree covers of graphs
✍ G. Even; N. Garg; J. Könemann; R. Ravi; A. Sinha 📂 Article 📅 2004 🏛 Elsevier Science 🌐 English ⚖ 225 KB
Approximation Algorithms for Min–Max Tre
Approximation Algorithms for Min–Max Tree Partition
✍ Nili Guttmann-Beck; Refael Hassin 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 298 KB

We consider the problem of partitioning the node set of a graph into p equal sized subsets. The objective is to minimize the maximum length, over these subsets, of a minimum spanning tree. We show that no polynomial algorithm with bounded Ž 2 . error ratio can be given for the problem unless P s NP.

Approximation results for min-max path c
Approximation results for min-max path cover problems in vehicle routing
✍ Zhou Xu; Liang Xu; Chung-Lun Li 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 410 KB

## Abstract This article studies a min‐max path cover problem, which is to determine a set of paths for __k__ capacitated vehicles to service all the customers in a given weighted graph so that the largest path cost is minimized. The problem has wide applications in vehicle routing, especially when