We are feeling experimental and want to create a new dish. There are
various ingredients we
can choose from and we'd like to use as many of them as possible, but
some ingredients don't
go well with others. If there are n possible ingredients (numbered 1
to n), we write down an
n x n matrix giving the discord between any pair of ingredients. This
discord is a real number
between 0.0 and 1.0, where 0.0 means (they go together perfectly) and
1.0 means (they really
don't go together.) Here's an example matrix when there are ve
possible ingredients.
1 2 3 4 5
1 0.0 0.4 0.2 0.9 1.0
2 0.4 0.0 0.1 1.0 0.2
3 0.2 0.1 0.0 0.8 0.5
4 0.9 1.0 0.8 0.0 0.2
5 1.0 0.2 0.5 0.2 0.0
In this case, ingredients 2 and 3 go together pretty well whereas 1
and 5 clash badly. Notice that this matrix is necessarily symmetric;
and that the diagonal entries are always 0:0. Any set of ingredients
incurs a penalty which is the sum of all discord values between pairs
of ingredients.For instance, the set of ingredients {1; 3; 5} incurs a
penalty of 0.2+1.0+0.5 = 1.7. We want this penalty to be small.
EXPERIMENTAL CUISINE
Input: n, the number of ingredients to choose from; D, the nxn
"discord" matrix; some
number p >= 0
Output: The maximum number of ingredients we can choose with penalty
<= p.
How do we show that if EXPERIMENTAL CUISINE is solvable in polynomial
time, then so is 3SAT.
Any Help would be appriciated.
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
