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] | Tong, Weitian (Tong, Weitian.) [2] | Goebel, Randy (Goebel, Randy.) [3] | Unfold

Indexed by:

EI

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:

Approximation algorithms Computational complexity Optical communication Traveling salesman problem

Community:

  • [ 1 ] [Huang, Liqin]College of Physics and Information Engineering, Fuzhou University, Fuzhou, Fujian; 350108, China
  • [ 2 ] [Tong, Weitian]Department of Computing Science, University of Alberta, Edmonton; AB; T6G 2E8, Canada
  • [ 3 ] [Goebel, Randy]Department of Computing Science, University of Alberta, Edmonton; AB; T6G 2E8, Canada
  • [ 4 ] [Liu, Tian]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, Guohui]Department of Computing Science, University of Alberta, Edmonton; AB; T6G 2E8, Canada

Reprint 's Address:

  • [lin, guohui]department of computing science, university of alberta, edmonton; ab; t6g 2e8, canada

Show more details

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

30 Days PV: 2

Affiliated Colleges:

Online/Total:114/10763621
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