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 条

[31] An approximation algorithm for the maximum spectral subgraph problem
Cristina Bazgan
Paul Beaujean
Éric Gourdin
Journal of Combinatorial Optimization, 2022, 44 : 1880 - 1899
[32] A 2-approximation algorithm for the network substitution problem
Pisaruk, NN
OPERATIONS RESEARCH LETTERS, 2006, 34 (01) : 94 - 96
[33] A 2 + ɛ approximation algorithm for the k-MST problem
Sanjeev Arora
George Karakostas
Mathematical Programming, 2006, 107 : 491 - 504
[34] An approximation algorithm for the maximum spectral subgraph problem
Bazgan, Cristina
Beaujean, Paul
Gourdin, Eric
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2022, 44 (03) : 1880 - 1899
[35] An improved lower bound and approximation algorithm for binary constrained quadratic programming problem
Cheng Lu
Zhenbo Wang
Wenxun Xing
Journal of Global Optimization, 2010, 48 : 497 - 508
[36] Improved Approximation Algorithm for the Fault-Tolerant Facility Placement Problem with Rejection
Yu S.
American Journal of Mathematical and Management Sciences, 2020, 39 (02) : 122 - 128
[37] An Improved Constant-Factor Approximation Algorithm for Planar Visibility Counting Problem
Alipour, Sharareh
Ghodsi, Mohammad
Jafari, Amir
COMPUTING AND COMBINATORICS, COCOON 2016, 2016, 9797 : 209 - 221
[38] An improved lower bound and approximation algorithm for binary constrained quadratic programming problem
Lu, Cheng
Wang, Zhenbo
Xing, Wenxun
JOURNAL OF GLOBAL OPTIMIZATION, 2010, 48 (03) : 497 - 508
[39] Approximation algorithm for the multicovering problem
Gorgi, Abbass
El Ouali, Mourad
Srivastav, Anand
Hachimi, Mohamed
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2021, 41 (02) : 433 - 450
[40] Approximation algorithm for the multicovering problem
Abbass Gorgi
Mourad El Ouali
Anand Srivastav
Mohamed Hachimi
Journal of Combinatorial Optimization, 2021, 41 : 433 - 450

← 1 2 3 4 5 →