Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sun-barr!olivea!samsung!think.com!snorkelwacker.mit.edu!bloom-beacon!eru!hagbard!sunic!mcsun!inria!loria!loria.crin.fr
From: marquis@loria.crin.fr (Pierre MARQUIS)
Newsgroups: comp.theory
Subject: complexity
Message-ID: <2952@loria.crin.fr>
Date: 20 Nov 90 14:05:07 GMT
Sender: marquis@loria.crin.fr
Organization: CRIN & INRIA Lorraine, Nancy, France
Lines: 19

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