5
$\begingroup$

I'm not expert on complexity theory and combinatorial optimization. I want to know if the following problem (or similar) is known in the scientific literature, and if you think it is NP-complete. Thank you in advance for your help.

Input:

Two parameters X and Y, which can be equal.
n customers C1, C2, ... Cn
m types of goods M1, M2 ... Mm

There are X pieces available for each good Mi: a piece of 1kg, another piece of 2kg, ...., a piece of X kg.
Every customer wants to buy a certain number of goods. For example, the client C1 may be interested in buying goods M1, M4, M8 and M9. A customer is satisfied if he can find all the goods he wants to buy. In addition, the weights of the parts he was able to purchase must satisfy a constraint that I'll explain below.

Output: How many customers can be satisfied?

The constraint on the weights is as follows: Take for example the client C1 who is interested in buying goods M1, M4, M8 and M9. Assume that C1 was able to purchase all four goods. Let P1, P2, P3, P4 be the weights of the pieces he was able to buy. C1 is satisfied if $\sum_i P_i -1 <Y$.

Edit: Note that the limit Y is common for all customers. The intuition behind the constraint is that we want to limit the number of pieces whose weight is not equal to 1kg.

Improve this question
$\endgroup$
17
  • 13
    $\begingroup$ @Tsuyoshi: We certainly don't want homework problems at this level. I'm in favor of allowing other problems at this level, because I think we want to reach out to other areas of computer science, and they aren't necessarily going to know the difference between an easy problem and a hard, interesting problem. On the other hand, we could require people from other areas of CS to tell us why they're interested in the problem; this would screen out homework problems. $\endgroup$
    – Peter Shor
    Commented Nov 8, 2010 at 14:04
  • 7
    $\begingroup$ just my .02, but this didn't sound like a homework problem to me. $\endgroup$
    – Suresh Venkat
    Commented Nov 8, 2010 at 15:21
  • 4
    $\begingroup$ @Tsuyoshi: you should put your comment as an answer! $\endgroup$
    – arnab
    Commented Nov 8, 2010 at 17:52
  • 7
    $\begingroup$ @user2094, if you're comfortable giving us more information about yourself/the application you're interested in, this could provide a good example of how this site helps with outreach (per Peter's comment) $\endgroup$
    – Suresh Venkat
    Commented Nov 8, 2010 at 18:12
  • 4
    $\begingroup$ I agree with @Xorlev, there is currently no place to publish NP-hardness results as they are now rather routine. This site already has several examples of new reductions, and it seems a good use of the site: it is a nice win-win situation, a match between something often rather easy to a complexity theorist, and something rather hard (but potentially valuable) to someone who is not. $\endgroup$
    – András Salamon
    Commented Nov 10, 2010 at 10:39

2 Answers 2

Reset to default
16
$\begingroup$

(I have posted this answer as a comment on the question, but I am reposting it with a little more detail.)

This problem is NP-hard as follows.

As is usual in a proof of NP-hardness, suppose that a natural number K is also given as part of input, and consider the yes/no problem of deciding whether at least K customers are satisfied. Then this problem is NP-complete, even if it is restricted to the case where X=1, m=3K and each customer wants to buy exactly three goods. (Note that if X=1, the value of Y is irrelevant as long as Y>0.) In this case, the problem is equivalent to the NP-complete problem called Exact Cover by 3-Sets.

See Garey and Johnson for more on complexity theory and NP-completeness, including the definition of the Exact Cover by 3-Sets and the proof of its NP-completeness.

Improve this answer
$\endgroup$
-3
$\begingroup$

As the problem is phrased there is no dependency between the customers so it should be easy to solve: check your constraint for every customer independently. This is clearly fast (linear in the number of purchased pieces times number of customers).

Improve this answer
$\endgroup$
3
  • $\begingroup$ It doesn't seem like the OP forbids customers interested in the same items, so there could be a dependency in the sense that we might satisfy more customers by excluding some customers who, for instance, want to buy the whole stock available for a given item. $\endgroup$
    – Anthony Labarre
    Commented Nov 8, 2010 at 11:48
  • 1
    $\begingroup$ The dependency between customers is that they may want to buy the same good. Since there are at most X pieces of each good, if more than X customers want the same good, some of them are satisfied and others not. $\endgroup$
    – user2094
    Commented Nov 8, 2010 at 12:06
  • $\begingroup$ This is not how I understood the meaning of X. As stated above, each good is a composite of X pieces with different weights. There is no statement about the number of available goods/pieces. Please clarify the question. $\endgroup$
    – Raphael
    Commented Nov 8, 2010 at 13:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.