A strongly polynomial time approximation algorithm for the min-max clustered cycle cover problem

被引:0
|
作者
Pan, Pengxiang [1 ]
Zhu, Hongtao [2 ]
机构
[1] Taizhou Univ, Sch Elect & Informat Engn, Taizhou 318000, Zhejiang, Peoples R China
[2] Univ Sains Malaysia, Sch Math Sci, George Town 11800, Pulau Pinang, Malaysia
关键词
Combinatorial optimization; Cycle cover; Clustered; Approximation algorithm;
D O I
10.1016/j.tcs.2024.115050
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We reconsider the min-max clustered cycle cover (MM-CCC) problem, which is described as follows. Given an undirected complete graph G = (V, E ; w ) with a positive integer k , where the vertex set V is partitioned into h clusters V 1 , ... , V h , and w : E -> & Ropf;+ is an edge-weight function satisfying the triangle inequality, it is asked to find k cycles such that they traverse all vertices and the vertices in each cluster are required to be traversed consecutively. The objective is to minimize the weight of the maximum weight cycle. We propose a strongly polynomial time 16- approximation algorithm for the MM-CCC problem. The result improves the previous algorithm in terms of running time.
引用
收藏
页数:7
相关论文
共 50 条
  • [1] Approximation Algorithms for Min-Max Cycle Cover Problems
    Xu, Wenzheng
    Liang, Weifa
    Lin, Xiaola
    IEEE TRANSACTIONS ON COMPUTERS, 2015, 64 (03) : 600 - 613
  • [2] Improved approximation algorithms for some min-max and minimum cycle cover problems
    Yu, Wei
    Liu, Zhaohui
    THEORETICAL COMPUTER SCIENCE, 2016, 654 : 45 - 58
  • [3] Approximation Algorithm for Min-Max Correlation Clustering Problem with Outliers
    Ji, Sai
    Li, Min
    Liang, Mei
    Zhang, Zhenning
    COMBINATORIAL OPTIMIZATION AND APPLICATIONS, COCOA 2021, 2021, 13135 : 668 - 675
  • [4] Improved approximation algorithms for some min-max postmen cover problems with applications to the min-max subtree cover
    Yu, Wei
    MATHEMATICAL METHODS OF OPERATIONS RESEARCH, 2023, 97 (01) : 135 - 157
  • [5] Better Inapproximability Bounds and Approximation Algorithms for Min-Max Tree/Cycle/Path Cover Problems
    Yu, Wei
    Liu, Zhaohui
    COMPUTING AND COMBINATORICS, COCOON 2017, 2017, 10392 : 542 - 554
  • [6] Approximation Algorithms for Min-Max Path Cover Problems with Service Handling Time
    Xu, Zhou
    Xu, Liang
    ALGORITHMS AND COMPUTATION, PROCEEDINGS, 2009, 5878 : 383 - 392
  • [7] Approximation Algorithms for the Min-Max Mixed Rural Postmen Cover Problem and Its Variants
    Huang, Liting
    Yu, Wei
    Liu, Zhaohui
    COMPUTING AND COMBINATORICS, COCOON 2022, 2022, 13595 : 36 - 48
  • [8] Approximation Algorithms for the Min-Max Mixed Rural Postmen Cover Problem and Its Variants
    Huang, Liting
    Yu, Wei
    Liu, Zhaohui
    ALGORITHMICA, 2024, 86 (04) : 1135 - 1162
  • [9] Approximation algorithms for some min-max postmen cover problems
    Yu, Wei
    Liu, Zhaohui
    Bao, Xiaoguang
    ANNALS OF OPERATIONS RESEARCH, 2021, 300 (01) : 267 - 287
  • [10] Better approximability results for min-max tree/cycle/path cover problems
    Yu, Wei
    Liu, Zhaohui
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2019, 37 (02) : 563 - 578