Approximation hardness of min-max tree covers |
| |
| Authors: | Zhou Xu Qi Wen |
| |
| Institution: | a Department of Logistics and Maritime Studies, The Hong Kong Polytechnic University, Hong Kong
b Department of Management Sciences, The City University of Hong Kong, Hong Kong |
| |
| 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. |
| |
| Keywords: | Inapproximability bound Min-max Vehicle routing Tree covers |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
