An Efficient Approximation Algorithm for Maximum Simple Sharing Problem
DOI:
Author:
Affiliation:

Clc Number:

Fund Project:

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    Abstract:

    This paper introduces a crossing elimination model based on a node duplication method and the authors want to minimize the number of duplication. It is related with an artificial problem, called the maximum simple sharing problem. First it is proved to be NP-hard, then a simple greedy algorithm which achieves an approximation factor of 3. Next the maximum disjoint simple sharing problem is introduced, which is naturally a 2-approximation of the maximum simple sharing problem, and the paper shows that this problem can be solved optimally by reducing to the perfect matching problem in a series of carefully constructed graphs. At last, the approximation factor is further improved to 12/7 with a local search technique.

    Reference
    Related
    Cited by
Get Citation

李 建,张 韬,谢之易,朱 洪.最大简单共享问题的快速近似算法.软件学报,2008,19(3):492-499

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:March 29,2006
  • Revised:January 23,2007
  • Adopted:
  • Online:
  • Published:
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063