Maximum bounded 3-dimensional matching is MAX SNP-complete

作者： Viggo Kann

DOI: 10.1016/0020-0190(91)90246-E

关键词: min/max kd-tree 、 Graph 、 3-dimensional matching 、 Mathematics 、 Bounded function 、 Combinatorics

摘要: … We prove that maximum 3-dimensional matching is a MAX SNP-hard problem. Ef the … is MAX SNP-complete. As corollaries we prove that maximum covering by 3-sets and maximum …

参考文章(6)

Piotr Berman, Georg Schnitger, On the complexity of approximating the independent set problem symposium on theoretical aspects of computer science. pp. 256- 268 ,(1989) , 10.1007/BFB0028990

Michael Randolph Garey, Johnson: computers and intractability: a guide to the theory of np- completeness (freeman ,(1979)

Michael R. Garey, David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness ,(1979)

Christos Papadimitriou, Mihalis Yannakakis, Optimization, approximation, and complexity classes symposium on the theory of computing. pp. 229- 234 ,(1988) , 10.1145/62212.62233

Nicos Christofides, Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem ,(1976)

Narendra Karmarkar, Richard M. Karp, An efficient approximation scheme for the one-dimensional bin-packing problem 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982). pp. 312- 320 ,(1982) , 10.1109/SFCS.1982.61