marquis@loria.crin.fr (Pierre MARQUIS) (11/20/90)
Does anybody know the complexity of the following matching problem ?
(in particular, is it NP-complete ?)
Let us consider a set S = {s1, ..., sn} and a cost function C from
the cartesian product S X S to the set of the natural integers N.
We assume that C is symetric, that is C(x,y) = C(y,x) for all (x,y) in S X S.
Find MM = {(si1, si2), (si3, si4), ..., (sim-1, sim)} such that:
- each sij is in S
- sij <> sik when ij <> ik
- Card(MM) is maximum
- C(si1,si2) + C(si3,si4) + ... + C(sim-1,sim) is maximum.
Please e-mail me your answers (references are welcome too). Thanks in advance.
Pierre Marquis
CRIN / INRIA-Lorraine
B.P. 239
54506 Vandoeuvre les Nancy Cedex
FRANCE
e-mail: marquis@loria.crin.fr