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 条
  • [21] An improved approximation algorithm for the partial Latin square extension problem
    Gomes, CP
    Regis, RG
    Shmoys, DB
    OPERATIONS RESEARCH LETTERS, 2004, 32 (05) : 479 - 484
  • [22] An O(log n)-Approximation Algorithm for the Edge-Disjoint Paths Problem in Eulerian Planar Graphs
    Kawarabayashi, Ken-Ichi
    Kobayashi, Yusuke
    ACM TRANSACTIONS ON ALGORITHMS, 2013, 9 (02)
  • [23] An Approximation Algorithm for the 2-Dispersion Problem
    Amano, Kazuyuki
    Nakano, Shin-ichi
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2020, E103D (03) : 506 - 508
  • [24] An Improved Approximation Algorithm for the Minimum Power Cover Problem with Submodular Penalty
    Dai, Han
    COMPUTATION, 2022, 10 (10)
  • [25] An improved approximation algorithm for the minimum 3-path partition problem
    Chen, Yong
    Goebel, Randy
    Lin, Guohui
    Su, Bing
    Xu, Yao
    Zhang, An
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2019, 38 (01) : 150 - 164
  • [26] An improved approximation algorithm for the minimum 3-path partition problem
    Yong Chen
    Randy Goebel
    Guohui Lin
    Bing Su
    Yao Xu
    An Zhang
    Journal of Combinatorial Optimization, 2019, 38 : 150 - 164
  • [27] An Improved Approximation Algorithm for the s-t Path Movement Problem
    Jindaluang, Wattana
    Chawachat, Jakarin
    Chouvatut, Varin
    Fakcharoenphol, Jittat
    Kantabutra, Sanpawat
    CHIANG MAI JOURNAL OF SCIENCE, 2017, 44 (01): : 279 - 286
  • [28] Improved Approximation Algorithm for Vertex Cover Problem using Articulation Points
    Patel, Smit
    Kamath, Sowmya S.
    2014 INTERNATIONAL CONFERENCE ON COMPUTING, COMMUNICATION AND NETWORKING TECHNOLOGIES (ICCCNT, 2014,
  • [29] Improved approximation algorithm for universal facility location problem with linear penalties
    Xu, Yicheng
    Xu, Dachuan
    Du, Donglei
    Wu, Chenchen
    THEORETICAL COMPUTER SCIENCE, 2019, 774 (143-151) : 143 - 151
  • [30] AN APPROXIMATION ALGORITHM FOR FULLY PLANAR EDGE-DISJOINT PATHS
    Huang, Chien-Chung
    Mari, Mathieu
    Mathieu, Claire
    Schewior, Kevin
    Vygen, Jens
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2021, 35 (02) : 752 - 769
12345