Given a complete graph \(G=(V,E)\) on kn vertices with a non-negative weight function on E, the maximum weight k-cycle (k-path) partition problem aims to find a set of n vertex disjoint k-cycles (k-paths) such that these cycles (paths) cover all the vertices and the total edge weight of them is maximized. Here a k-cycle (k-path) is a cycle (path) containing precisely k vertices. In this paper, we obtain improved approximation algorithms for the maximum weight k-cycle (k-path) partition problem in graphs with weights one and two. For the maximum weight k-cycle partition problem with weights one and two, we develop an algorithm that has an approximation ratio of \(\frac{37}{48}\) for \(k=6\) , improving upon the state-of-the-art \(\frac{91}{120}\) -approximation algorithm. For the case of \(k=4\) , we prove that this algorithm has a tight approximation ratio of \(\frac{7}{8}\) that ties with the existing result. However, we show that this algorithm can be applied to the minimum weight k-cycle partition problem with weights one and two and achieve a tight approximation ratio of \(\frac{5}{4}\) . For the maximum weight 5-path partition problem with weights one and two, we propose a novel \(\frac{19}{24}\) -approximation algorithm, which is a combination of two separate algorithms.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Approximating the Maximum Weight Cycle/Path Partition in Graphs with Weights One and Two

  • Xinmeng Guo,
  • Wei Yu,
  • Zhaohui Liu

摘要

Given a complete graph \(G=(V,E)\) on kn vertices with a non-negative weight function on E, the maximum weight k-cycle (k-path) partition problem aims to find a set of n vertex disjoint k-cycles (k-paths) such that these cycles (paths) cover all the vertices and the total edge weight of them is maximized. Here a k-cycle (k-path) is a cycle (path) containing precisely k vertices. In this paper, we obtain improved approximation algorithms for the maximum weight k-cycle (k-path) partition problem in graphs with weights one and two. For the maximum weight k-cycle partition problem with weights one and two, we develop an algorithm that has an approximation ratio of \(\frac{37}{48}\) for \(k=6\) , improving upon the state-of-the-art \(\frac{91}{120}\) -approximation algorithm. For the case of \(k=4\) , we prove that this algorithm has a tight approximation ratio of \(\frac{7}{8}\) that ties with the existing result. However, we show that this algorithm can be applied to the minimum weight k-cycle partition problem with weights one and two and achieve a tight approximation ratio of \(\frac{5}{4}\) . For the maximum weight 5-path partition problem with weights one and two, we propose a novel \(\frac{19}{24}\) -approximation algorithm, which is a combination of two separate algorithms.