文献类型：期刊文献

英文题名：Better Inapproximability Bounds and Approximation Algorithms for Min-Max Tree/Cycle/Path Cover Problems

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

机构：[1] Department of Mathematics, East China University of Science and Technology, Shanghai, 200237, China

年份：2017

卷号：10392 LNCS

起止页码：542

外文期刊名：Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

收录：EI(收录号：20173504107557)

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

语种：英文

外文关键词：Forestry - Combinatorial optimization - Undirected graphs - Traveling salesman problem - Trees (mathematics)

摘要：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. ? 2017, Springer International Publishing AG.