Numerical 3-dimensional matching

Numerical 3-dimensional matching

Numerical 3-dimensional matching is a strongly NP-complete decision problem. It is given by three multisets of integers X, Y and Z, each containing k elements, and a bound b. The goal is to select a subset M of X\times Y\times Z such that every integer in X, Y and Z occurs exactly once and that for every triple (x,y,z) in the subset x + y + z = b holds. This problem is labeled as [SP16] in [1].

Contents

Example

Take X = {3,4,4}, Y = {1,4,6} and Z = {1,2,5}, and b = 10. This instance has a solution, namely {(3,6,1),(4,4,2),(4,1,5)}. Note that each triple sums to b = 10. The set {(3,6,1),(3,4,2),(4,1,5)} is not a solution for several reasons: not every number is used (a 4\in X is missing), a number is used too often (the 3\in X) and not every triple sums to b (since 3+4+2=9\neq b=10). 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 b = 11 for the same X, Y and Z, this problem would have no solution (all numbers sum to 30, which is not equal to k\cdot b=33 in this case).

Related problems

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".[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. ^ a b Garey, Michael R. and David S. Johnson (1979), Computers and Intractability; A Guide to the Theory of NP-Completeness. ISBN 0-7167-1045-5

Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • List of NP-complete problems — Here are some of the more commonly known problems that are NP complete when expressed as decision problems. This list is in no way comprehensive (there are more than 3000 known NP complete problems). Most of the problems in this list are taken… …   Wikipedia

  • Liste De Problèmes NP-Complets — Ceci est une liste des problèmes NP complets les plus connus en théorie de la complexité des algorithmes, exprimés sous la forme d un problèmes de la décision. Puisqu on connaît plus de 3000 problèmes NP complets, cette liste n est pas exhaustive …   Wikipédia en Français

  • Liste de problemes NP-complets — Liste de problèmes NP complets Ceci est une liste des problèmes NP complets les plus connus en théorie de la complexité des algorithmes, exprimés sous la forme d un problèmes de la décision. Puisqu on connaît plus de 3000 problèmes NP complets,… …   Wikipédia en Français

  • Liste de problèmes NP-complets — Ceci est une liste des problèmes NP complets les plus connus en théorie de la complexité des algorithmes, exprimés sous la forme d un problème de décision. Puisqu on connaît plus de 3000 problèmes NP complets, cette liste n est pas exhaustive. La …   Wikipédia en Français

  • Liste de problèmes np-complets — Ceci est une liste des problèmes NP complets les plus connus en théorie de la complexité des algorithmes, exprimés sous la forme d un problèmes de la décision. Puisqu on connaît plus de 3000 problèmes NP complets, cette liste n est pas exhaustive …   Wikipédia en Français

  • Mixture model — See also: Mixture distribution In statistics, a mixture model is a probabilistic model for representing the presence of sub populations within an overall population, without requiring that an observed data set should identify the sub population… …   Wikipedia

  • Antenna (radio) — Whip antenna on car …   Wikipedia

  • CIE 1931 color space — In the study of color perception, one of the first mathematically defined color spaces is the CIE 1931 XYZ color space, created by the International Commission on Illumination (CIE) in 1931.[1][2] The CIE XYZ color space was derived from a series …   Wikipedia

  • Global climate model — AGCM redirects here. For Italian competition regulator, see Autorità Garante della Concorrenza e del Mercato. Climate models are systems of differential equations based on the basic laws of physics, fluid motion, and chemistry. To “run” a model,… …   Wikipedia

  • computer science — computer scientist. the science that deals with the theory and methods of processing information in digital computers, the design of computer hardware and software, and the applications of computers. [1970 75] * * * Study of computers, their… …   Universalium

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”