An Efficient Approximation Algorithm for Maximum Simple Sharing Problem

Jian LiJournal of Software 2008 · DOI

Abstract

介绍了一种基于复制结点的消除线路交叉的模型.该模型提出了一个优化问题,就是最小化结点复制的数量.同时提出一个自定义问题——"最大简单共享问题",并证明最小化结点复制的数量与最大共享问题是等价的.证明了最大简单共享问题是NP-hard的,给出了一种简单的贪心算法,并证明该贪心算法的近似度为3.引入一个"最大互斥简单共享问题",该问题是最大简单共享问题的2-近似.将其转化为在一系列图上的完美匹配问题,使该问题可以在多项式时间内得到完美解决.最后,在最大互斥简单共享的基础上,用局部搜索的方法将近似度提高到12/7.
BibTeX
@article{li2008efficient,
  author = {Jian Li},
  title = {{An Efficient Approximation Algorithm for Maximum Simple Sharing Problem}},
  journal = {Journal of Software},
  year = {2008},
  doi = {10.3724/sp.j.1001.2008.00492},
}

Loading related content...

Figure