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

author:

Huang, L. (Huang, L..) [1] | Tong, W. (Tong, W..) [2] | Goebel, R. (Goebel, R..) [3] | Liu, T. (Liu, T..) [4] | Lin, G. (Lin, G..) [5]

Indexed by:

Scopus

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 227426. 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 70-2128≈0.5358-approximation algorithm for the Bandpass-2 problem. © 2013, Springer Science+Business Media New York.

Keyword:

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

Community:

  • [ 1 ] [Huang, L.]College of Physics and Information Engineering, Fuzhou University, Fuzhou, Fujian, 350108, China
  • [ 2 ] [Tong, W.]Department of Computing Science, University of Alberta, Edmonton, AB T6G 2E8, Canada
  • [ 3 ] [Goebel, R.]Department of Computing Science, University of Alberta, Edmonton, AB T6G 2E8, Canada
  • [ 4 ] [Liu, T.]Key Laboratory of High Confidence Software Technologies, Ministry of Education, Institute of Software, School of Electronic Engineering and Computer Science, Peking University, Beijing, 100871, China
  • [ 5 ] [Lin, G.]Department of Computing Science, University of Alberta, Edmonton, AB T6G 2E8, Canada

Reprint 's Address:

  • [Lin, G.]Department of Computing Science, University of AlbertaCanada

Email:

Show more details

Related Keywords:

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 HC Threshold:86

JCR Journal Grade:2

CAS Journal Grade:3

Cited Count:

WoS CC Cited Count:

SCOPUS Cited Count: 3

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 0

Affiliated Colleges:

Online/Total:158/10272684
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