An improved approximation algorithm for the disjoint 2-catalog segmentation problem

被引：0
|
作者：
Zhou, Houchun [1 ,2 ]
Zhang, Dexue [1 ]
机构：
[1] Linyi Teachers Coll, Dept Math, Linyi 276005, Shandong, Peoples R China
[2] Nanjing Normal Univ, Sch Math & Comp Sci, Nanjing 210097, Jiangsu, Peoples R China
来源：
OPERATIONS RESEARCH AND ITS APPLICATIONS | 2006年 / 6卷
基金：
中国国家自然科学基金;
关键词：
disjoint 2-catalog segmentation; approximation algorithm; semidefinite programming;
D O I：
暂无
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
For the disjoint 2-catalog segmentation problem (may be inequivalent), we propose a improved polynomial-time randomized approximation algorithm, and obtain a performance ratios rho which is not less than 0.5 for a wide range of this problem. As a result, the 0.699-approximation algorithm for the disjoint equivalent 2-catalog segmentation problem can be obtained.
引用
收藏
页码：350 / +
页数：2
相关论文
共 50 条
  • [41] A 2√2k-approximation algorithm for minimum power k edge disjoint st-paths
    Nutov, Zeev
    INFORMATION PROCESSING LETTERS, 2025, 188
  • [42] A 2+ε approximation algorithm for the k-MST problem
    Arora, S
    Karakostas, G
    MATHEMATICAL PROGRAMMING, 2006, 107 (03) : 491 - 504
  • [43] A 2-Approximation Algorithm for the Graph 2-Clustering Problem
    Il'ev, Victor
    Il'eva, Svetlana
    Morshinin, Alexander
    MATHEMATICAL OPTIMIZATION THEORY AND OPERATIONS RESEARCH, 2019, 11548 : 295 - 308
  • [44] Approximation Algorithm for the Balanced 2-Correlation Clustering Problem
    Ji, Sai
    Xu, Dachuan
    Du, Donglei
    Gai, Ling
    Zhao, Zhongrui
    TSINGHUA SCIENCE AND TECHNOLOGY, 2022, 27 (05) : 777 - 784
  • [45] A Local 2-Approximation Algorithm for the Vertex Cover Problem
    Astrand, Matti
    Floreen, Patrik
    Polishchuk, Valentin
    Rybicki, Joel
    Suomela, Jukka
    Uitto, Jara
    DISTRIBUTED COMPUTING, PROCEEDINGS, 2009, 5805 : 191 - 205
  • [46] An Improved Approximation Algorithm for the k-Level Facility Location Problem with Soft Capacities
    Chen-chen WU
    Da-chuan XU
    Acta Mathematicae Applicatae Sinica, 2017, 33 (04) : 1015 - 1024
  • [47] An Improved Approximation Algorithm for the k-Level Facility Location Problem with Soft Capacities
    Wu, Chen-chen
    Xu, Da-chuan
    ACTA MATHEMATICAE APPLICATAE SINICA-ENGLISH SERIES, 2017, 33 (04): : 1015 - 1024
  • [48] AN IMPROVED APPROXIMATION ALGORITHM FOR THE k-PRIZE-COLLECTING MINIMUM POWER COVER PROBLEM
    Wang, Wencheng
    Cheng, Binhui
    Li, Jianglin
    Chen, Yinhua
    Zhang, Tongquan
    JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION, 2024, 20 (04) : 1703 - 1718
  • [49] An improved primal-dual approximation algorithm for the k-means problem with penalties
    Ren, Chunying
    Xu, Dachuan
    Du, Donglei
    Li, Min
    MATHEMATICAL STRUCTURES IN COMPUTER SCIENCE, 2022, 32 (02) : 151 - 163
  • [50] Improved Approximation Algorithm for the Distributed Lower-Bounded k-Center Problem
    Liang, Ting
    Feng, Qilong
    Wu, Xiaoliang
    Xu, Jinhui
    Wang, Jianxin
    THEORY AND APPLICATIONS OF MODELS OF COMPUTATION, TAMC 2024, 2024, 14637 : 309 - 319
12345