Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.1 6/24/83; site duke.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!gamma!epsilon!zeta!sabre!petrus!bellcore!decvax!mcnc!duke!aff
From: aff@duke.UUCP (Amr Fahmy)
Newsgroups: net.math
Subject: A new coding problem
Message-ID: <6218@duke.UUCP>
Date: Mon, 2-Sep-85 12:17:37 EDT
Article-I.D.: duke.6218
Posted: Mon Sep  2 12:17:37 1985
Date-Received: Thu, 5-Sep-85 06:39:52 EDT
Organization: Duke University
Lines: 53


		HERE IS A PROBLEM, I NEED A SOLUTION !!!

I worked on the following problem for a long time, no solution.
This is the second posting of this problem on net.math. The first 
posting was in the summer and I got only 1 reply. I think the fact 
that it was the summer vacation had a lot to do with the number of 
replies I got back.

If you know anything related, a solution, NP-completeness, clues, to the 
problem, please reply.

/*------------------------------------------------------------------------*/

The problem :

Let S be the set of all binary words of length n.
Let E be a set containg exactly L of the words in S.
Define 
         C(E)  =   sigma    min    diff(x,e)
                  x in S   e in E

                 where diff(x,y) = m  if x and y are two binary words that 
                 are different in exactly m bits. Of course m <= n.

to be the cost of the set E.

Now given the two integers n and L, the problem is to construct a set E
such that C(E) is minimum.

/*------------------------------------------------------------------------*/

Example :

Suppose n=4 and L=4, we can construct the following two sets :

E1 = { 0000,                               E2 = { 0000,
       0011,                                      0001, 
       1100,                                      1110,
       1111 }                                     1111 }

C(E1) = 16                                 C(E2) = 12

Of course the set E2 is more desirable than E1, in fact E2 is ONE of the
optimal sets I am lookoing for, you cannot find a set E3 with cost less
than 12 !!

/*------------------------------------------------------------------------*/

				Amr Fahmy

                                aff@duke
                                ..!mcnc!duke!aff