A 0.5358-approximation for Bandpass-2

被引：4

作者：

Huang, Liqin ^{[1
]}

Tong, Weitian ^{[2
]}

Goebel, Randy ^{[2
]}

Liu, Tian ^{[3
]}

Lin, Guohui ^{[2
]}

机构：

[1] Fuzhou Univ, Coll Phys & Informat Engn, Fuzhou 350108, Fujian, Peoples R China

[2] Univ Alberta, Dept Comp Sci, Edmonton, AB T6G 2E8, Canada

[3] Peking Univ, Inst Software, Sch Elect Engn & Comp Sci, Key Lab High Confidence Software Technol,Minist E, Beijing 100871, Peoples R China

来源：

JOURNAL OF COMBINATORIAL OPTIMIZATION | 2015年 / 30卷 / 03期

基金：

加拿大自然科学与工程研究理事会;

关键词：

The Bandpass problem; Maximum weight b-matching; Acyclic; 2-matching; Approximation algorithm; Worst case performance ratio; ALGORITHM;

D O I：

10.1007/s10878-013-9656-2

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

The Bandpass-2 problem is a variant of the maximum traveling salesman problem arising from optical communication networks using wavelength-division multiplexing technology, in which the edge weights are dynamic rather than fixed. The previously best approximation algorithm for this NP-hard problem has a worst-case performance ratio of Here we present a novel scheme to partition the edge set of a 4-matching into a number of subsets, such that the union of each of them and a given matching is an acyclic 2-matching. Such a partition result takes advantage of a known structural property of the optimal solution, leading to a -approximation algorithm for the Bandpass-2 problem.

引用

页码：612 / 626

页数：15

共 20 条

[1]

[Anonymous], 1984, Upr. Sist.

[2]

[Anonymous], 2005, Graph Theory

[3] A POLYNOMIAL ALGORITHM FOR B-MATCHINGS - AN ALTERNATIVE APPROACH [J].

ANSTEE, RP .

INFORMATION PROCESSING LETTERS, 1987, 24 (03) :153-157

[4] On local search for weighted k-set packing [J].

Arkin, EM ;

Hassin, R .

MATHEMATICS OF OPERATIONS RESEARCH, 1998, 23 (03) :640-648

[5] The bandpass problem: combinatorial optimization and library of problems [J].

Babayev, Djangir A. ;

Bell, George I. ;

Nuriyev, Urfat G. .

JOURNAL OF COMBINATORIAL OPTIMIZATION, 2009, 18 (02) :151-172

[6]

Bell GI, 2004, ANN INFORMS M DENV C

[7]

Chandra B, 1999, PROCEEDINGS OF THE TENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P169

[8]

Chen Z-Z, 2012, LNCS, V7402, P185

[9] Improved deterministic approximation algorithms for Max TSP [J].

Chen, ZZ ;

Okamoto, Y ;

Wang, LS .

INFORMATION PROCESSING LETTERS, 2005, 95 (02) :333-342

[10]

Gabow HN., 1983, PROC 15 ACM S THEORY, P448, DOI [DOI 10.1145/800061.808776, 10.1145/800061.808776]

← 1 2 →