Approzimating Alternative Solutions

摘要：

We study the approximability of alternative solutions for NP-problems. In particular, we show that approximating the second best solution is in many cases, such as MaxCut, MaxSat, Minimum Steiner Tree, and others, substantially easier than approximating a first solution. We prove that our polynomial-time approximation scheme for the second best solution of Minimum Steiner Tree is optimal. In contrast we also argue that for the problems Minimum Independent Dominating Set and Minimum Traveling Salesperson Problem a given optimal solution does not simplify finding a second best solution.

作者: Michael Krüger Harald Hempel

作者单位: Institut für Informatik, Friedrich-Schiller-Universitat Jena,D-07743 Jena, Germany

会议类型: 国际会议

会议名称: The 4th Annual International Computing and Combinatorics Conference,COCOON 2008(第14届国际计算和组合会议)

会议地点: 大连

会议语种:英文

页码: 204-214

在线出版日期: 2008-06-01（万方平台首次上网日期，不代表论文的发表时间）