文献类型：期刊文献

英文题名：Better approximability results for min-max tree/cycle/path cover problems

作者：Yu, Wei[1];Liu, Zhaohui[1]

机构：[1]East China Univ Sci & Technol, Dept Math, 130 Meilong Rd, Shanghai 200237, Peoples R China

年份：2019

卷号：37

期号：2

起止页码：563

外文期刊名：JOURNAL OF COMBINATORIAL OPTIMIZATION

收录：;EI(收录号：20191006598874);WOS:【SCI-EXPANDED(收录号:WOS:000460000100010)】；

基金：This research is supported in part by the National Natural Science Foundation of China under Grants Numbers 11671135, 11301184.

语种：英文

外文关键词：Approximation hardness; Approximation algorithm; Tree cover; Cycle cover; Path cover; Traveling salesman problem

摘要：We study the problem of covering the vertices of an undirected weighted graph with a given number of trees (cycles, paths) to minimize the weight of the maximum weight tree (cycle, path). Improved inapproximability lower bounds are proved and better approximation algorithms are designed for several variants of this problem.