Approximation hardness for small occurrence instances of NP-hard problems
作者： Miroslav Chlebík , Janka Chlebíková
关键词:
摘要: The paper contributes to the systematic study (started by Berman and Karpinski) of explicit approximability lower bounds for small occurrence optimization problems.We present parametrized reductions some packing covering problems, including 3-Dimensional Matching, prove best known inapproximability results even highly restricted versions them. For example, we show that it is NP-hard approximate Max-3-DM within 139/138 on instances with exactly two occurrences each element. Previous hardness bounded occurence case problem required bound at least three, then no was known. New structural which improve 3-regular amplifiers hence numerous problems studied earlier Karpinski are also presented.
sussex.ac.uk
springer.com
sci-hub.st 参考文章(13)
Piotr Berman, Toshihiro Fujito, On Approximation Properties of the Independent Set Problem for Low Degree Graphs workshop on algorithms and data structures. ,vol. 32, pp. 115- 132 ,(1999) , 10.1007/3-540-60220-8_84
Piotr Berman, Marek Karpinski, On Some Tighter Inapproximability Results, Further Improvements Electronic Colloquium on Computational Complexity. ,vol. 5, ,(1998)
Miroslav Chlebík, Janka Chlebíková, Approximation Hardness of the Steiner Tree Problem on Graphs scandinavian workshop on algorithm theory. pp. 170- 179 ,(2002) , 10.1007/3-540-45471-3_18
Lars Engebretsen, Marek Karpinski, Approximation Hardness of TSP with Bounded Metrics international colloquium on automata languages and programming. pp. 201- 212 ,(2001) , 10.1007/3-540-48224-5_17
Piotr Berman, Marek Karpinski, On Some Tighter Inapproximability Results (Extended Abstract) international colloquium on automata languages and programming. pp. 200- 209 ,(1999) , 10.1007/3-540-48523-6_17
Magnús M. Halldórsson, Approximating k-Set Cover and Complementary Graph Coloring integer programming and combinatorial optimization. pp. 118- 131 ,(1996) , 10.1007/3-540-61310-2_10
Johan Håstad, Some optimal inapproximability results Journal of the ACM. ,vol. 48, pp. 798- 859 ,(2001) , 10.1145/502090.502098
Martin Thimm, On the approximability of the Steiner tree problem mathematical foundations of computer science. ,vol. 295, pp. 387- 402 ,(2003) , 10.1016/S0304-3975(02)00414-0
Christos H. Papadimitriou, Mihalis Yannakakis, Optimization, approximation, and complexity classes Journal of Computer and System Sciences. ,vol. 43, pp. 425- 440 ,(1991) , 10.1016/0022-0000(91)90023-X
Viggo Kann, Maximum bounded 3-dimensional matching is MAX SNP-complete Information Processing Letters. ,vol. 37, pp. 27- 35 ,(1991) , 10.1016/0020-0190(91)90246-E