Numerical 3-dimensional matching

Numerical 3-dimensional matching is an NP-complete decision problem. It is given by three multisets of integers , and , each containing elements, and a bound . The goal is to select a subset of such that every integer in , and occurs exactly once and that for every triple in the subset holds. This problem is labeled as [SP16] in.[1]

Example

Take , and , and . This instance has a solution, namely . Note that each triple sums to . The set is not a solution for several reasons: not every number is used (a is missing), a number is used too often (the ) and not every triple sums to (since ). However, there is at least one solution to this problem, which is the property we are interested in with decision problems. If we would take for the same , and , this problem would have no solution (all numbers sum to , which is not equal to in this case).

Every instance of the Numerical 3-dimensional matching problem is an instance of both the 3-partition problem, and the 3-dimensional matching problem.

Proof of NP-completeness

NP-completeness of the 3-partition problem is stated by Garey and Johnson in "Computers and Intractability; A Guide to the Theory of NP-Completeness", which references to this problem with the code [SP16].[1] It is done by a reduction from 3-dimensional matching via 4-partition. To prove NP-completeness of the numerical 3-dimensional matching, the proof is similar, but a reduction from 3-dimensional matching via the numerical 4-dimensional matching problem should be used.

References

  1. Garey, Michael R. and David S. Johnson (1979), Computers and Intractability; A Guide to the Theory of NP-Completeness. ISBN 0-7167-1045-5
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.