[net.math] A new coding problem

aff@duke.UUCP (Amr F. Fahmy) (06/26/85)

Here is an interesting problem that I am sure you will enjoy working on.

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

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 !!

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

Now lets talk algorithms, the set E2 above was found using an exhaustive
search. The exhaustive search is very expensive. There are some ways
of decreasing the space of search but still it is expensive. What I
would like is a polynomial time algorithm to solve the problem.

I have worked on this problem for sometime now, I have no clues, and I do
not know if the problem is NP-complete. If you are interested please
send your comments, solutions, proofs... etc to aff@duke thanks a lot
in advance to who ever replies back.

				Amr Fahmy

                                aff@duke
                                ..!mcnc!duke!aff

aff@duke.UUCP (Amr Fahmy) (09/02/85)

		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

richard@boulder.UUCP (Richard Byrd) (09/13/85)

>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.

This seems to be a special case of the p-median problem or 
min-sum multicenter problem which comes up in operations research applications.
In the general case "S" is an arbitrary set (or perhaps a graph) 
with a distance function. You may find some information in the O.R.
literature under "Location Problems" or "Facility Location"

Garey and Johnson's book "Computers and Intractability" mentions it on p.220.
They say that in the general case the problem is NP-complete for general 
L (in your notation), but if L is fixed the problem is polynomial solvable
(unfortunately in the size of S, I think).
Of course you have a special distance function for which the
problem may be easier.

An approach which may help sometimes is the following.
You can set up the problem as an integer program.

min sum dij*xij
subj. to  sumj xij =1 for all i
               xij <= xjj for all i,j
          sumj xjj <= L
               xij >= 0 for all i,j    
where xjj=1 means word j is in E
      xij=1 word j is a closest word in E to word i
      dij is distance from i to j

I have heard that it very often happens that the corresponding
continuous LP has an integer solution.  Of course the LP can be very large.