高哲成， 余 炜， 刘朝晖

（华东理工大学数学学院，上海 200237）

树上的最小-最大k旅行商问题（Min-Maxk-TSPT）是多旅行商问题在树形结构中的推广问题。在Min-Maxk-TSPT 中，给定一个无向树形图T=(V,E) ，其中V是点集，E是边集，一个仓库s∈V，一个边权函数w:E→N ，以及k个旅行商，k是与输入无关的固定值。该问题的目标是找到一个k条环游的集合，其中每条环游都从s点出发并最终返回s点，并且使得T中每个节点都至少被一条环游覆盖，同时最小化其中最长环游的边权和。在更一般的Min-Maxk-TSPT 中，给定了一个候选仓库集D⊆V，每条环游需要从D中某个仓库出发并返回该仓库，若在Min-Maxk-TSPT中用子树来代替环游，就得到了树上的最小−最大k树覆盖问题（Min-Maxk-TCPT），类似地可以定义多仓库Min-Maxk-TCPT。由于树上的一条返回出发点的环游经过某个子树上的边为两次，所以多仓库Min-Maxk-TSPT 与多仓库Min-Maxk-TCPT 是等价的。

当k≥2 时，Min-Maxk-TSPT 是NP 困难的[1]，因为Averbakh 等[2]证明了它可以归约到经典的平行机调度问题Pk||Cmax，因此本文着重于拟多项式可解性和近似性的结果。对于Min-Max 2-TSPT，Averbakh等[3]得到了4/3 近似算法，对于多仓库Min-Max 2-TSPT的一个变体，得到了一个3/2 近似算法，该变体的条件为 |D|=2 ，且两个旅行商必须从不同仓库出发。随后对于多仓库Min-Maxk-TSPT的给定D=V这一特殊情况，文献[2]给出了O(kk−1nk−1) 时间的(2−2/(k+1)) 近似算法。而Nagamochi等[4-5]也通过时间复杂度分别为O((k−1)!n) 和O(k2n) 的算法得到了相同的近似比。对于Min-M(axk-TSPT，N)agamochi等[5-6]还提出了时间复杂度为Onloglog1+ε/23 的 (2+ε)近似算法，其中 ε 为任意正常数。Becker 等[7]为Min-Maxk-TSPT 设计了多项式时间近似方案（PTAS），当仓库数量固定时，可以推广到多仓库Min-Maxk-TSPT。文献[5]和文献[7]中的结果实际上解决了k作为输入一部分的Min-Maxk-TSPT 及其多仓库问题。……