Home>Results

  • Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
成果搜索

[期刊论文]

A 0.5358-approximation for Bandpass-2

Share
Edit Delete 报错

author:

Huang, Liqin (Huang, Liqin.) [1] (Scholars:黄立勤) | Tong, Weitian (Tong, Weitian.) [2] | Goebel, Randy (Goebel, Randy.) [3] | Unfold

Indexed by:

EI Scopus SCIE

Abstract:

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.

Keyword:

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

Community:

  • [ 1 ] [Huang, Liqin]Fuzhou Univ, Coll Phys & Informat Engn, Fuzhou 350108, Fujian, Peoples R China
  • [ 2 ] [Tong, Weitian]Univ Alberta, Dept Comp Sci, Edmonton, AB T6G 2E8, Canada
  • [ 3 ] [Goebel, Randy]Univ Alberta, Dept Comp Sci, Edmonton, AB T6G 2E8, Canada
  • [ 4 ] [Lin, Guohui]Univ Alberta, Dept Comp Sci, Edmonton, AB T6G 2E8, Canada
  • [ 5 ] [Liu, Tian]Peking Univ, Inst Software, Sch Elect Engn & Comp Sci, Key Lab High Confidence Software Technol,Minist E, Beijing 100871, Peoples R China

Reprint 's Address:

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

Show more details

Version:

Related Article:

Source :

JOURNAL OF COMBINATORIAL OPTIMIZATION

ISSN: 1382-6905

Year: 2015

Issue: 3

Volume: 30

Page: 612-626

1 . 0 8

JCR@2015

0 . 9 0 0

JCR@2023

ESI Discipline: MATHEMATICS;

ESI HC Threshold:86

JCR Journal Grade:2

CAS Journal Grade:3

Cited Count:

WoS CC Cited Count: 4

SCOPUS Cited Count: 3

30 Days PV: 0

Online/Total:127/10272148
Address:FZU Library(No.2 Xuyuan Road, Fuzhou, Fujian, PRC Post Code:350116) Contact Us:0591-22865326
Copyright:FZU Library Technical Support:Beijing Aegean Software Co., Ltd. 闽ICP备05005463号-1