An Efficient Approximation Algorithm for Maximum Simple Sharing Problem
Li Jian, Tao Zhang, Xie Zhi-yi, Hong Zhu · 2008
For many circuit design problems, it is imperative to carefully study the effect of physical implementation constraints. Under some circumstances, it is very difficult to fabricate wire crossings. In this paper, we introduce a crossing elimination model based on a node duplication method and we want to minimize the number of duplication. We relate it with an artificial problem, called the maximum simple sharing problem. First we prove it is NP-hard, then we show that a simple greedy algorithm can achieve an approximation factor of 3. We then introduce the maximum disjoint simple sharing problem, which is naturally a 2-approximation of the maximum simple sharing problem, and show that it can be solved optimally by reducing to the perfect matching problem in a series of carefully constructed graph. At last, we further improve the approximation factor to 12/7 with a local search technique.