论文部分内容阅读
本文研究了限制形式的最大化货郎问题,称为具有边长为1或2的最大化货郎问题,简记为MaxTSP{1,2}。问题具体描述为:给定一个赋权完全图G=（V,E;w）,其中ω:E→｛1,2｝,寻找一个圈C,经过每个顶点恰好一次,目标是使权重ω（C）=∑e∈E（C）ω（e）达到最大。为了解决具有边长为1或2的最大化货郎问题,本文主要设计出了两个多项式时间的近似算法,它们的近似比分别为8/9和11/12。