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 条
  • [1] AN IMPROVED APPROXIMATION ALGORITHM FOR THE 2-CATALOG SEGMENTATION PROBLEM USING SEMIDEFINITE PROGRAMMING RELAXATION
    Wu, Chenchen
    Xu, Dachuan
    Zhao, Xin-Yuan
    JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION, 2012, 8 (01) : 117 - 126
  • [2] IMPROVED RANDOMIZED ALGORITHM FOR THE EQUIVALENT 2-CATALOG SEGMENTATION PROBLEM
    袁玉波
    徐成贤
    NumericalMathematicsAJournalofChineseUniversities(EnglishSeries), 2005, (02) : 36 - 43
  • [3] Improved approximation algorithms for the max-bisection and the disjoint 2-catalog segmentation problems
    Xu, Zi
    Du, Donglei
    Xu, Dachuan
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2014, 27 (02) : 315 - 327
  • [4] Improved approximation algorithms for the max-bisection and the disjoint 2-catalog segmentation problems
    Zi Xu
    Donglei Du
    Dachuan Xu
    Journal of Combinatorial Optimization, 2014, 27 : 315 - 327
  • [5] Approximating the 2-catalog segmentation problem using semidefinite programming relaxations
    Xu, DC
    Ye, YY
    Zhang, JW
    OPTIMIZATION METHODS & SOFTWARE, 2003, 18 (06) : 705 - 719
  • [6] An Improved Approximation Algorithm for the Traveling Tournament Problem
    Yamaguchi, Daisuke
    Imahori, Shinji
    Miyashiro, Ryuhei
    Matsui, Tomomi
    ALGORITHMICA, 2011, 61 (04) : 1077 - 1091
  • [7] An Improved Approximation Algorithm for the Traveling Tournament Problem
    Yamaguchi, Daisuke
    Imahori, Shinji
    Miyashiro, Ryuhei
    Matsui, Tomomi
    ALGORITHMS AND COMPUTATION, PROCEEDINGS, 2009, 5878 : 679 - +
  • [8] An Improved Approximation Algorithm for the Traveling Tournament Problem
    Daisuke Yamaguchi
    Shinji Imahori
    Ryuhei Miyashiro
    Tomomi Matsui
    Algorithmica, 2011, 61
  • [9] An improved approximation algorithm for the clustered traveling salesman problem
    Bao, Xiaoguang
    Liu, Zhaohui
    INFORMATION PROCESSING LETTERS, 2012, 112 (23) : 908 - 910
  • [10] An Improved Approximation Algorithm for the Most Points Covering Problem
    Ghasemalizadeh, Hossein
    Razzazi, Mohammadreza
    THEORY OF COMPUTING SYSTEMS, 2012, 50 (03) : 545 - 558
12345