Timeline for Is the following problem NP-Hard?
Current License: CC BY-SA 2.5
29 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 13, 2011 at 17:17 | history | edited | András Salamon | CC BY-SA 2.5 |
more corrections; it is probably not worth polishing this further, as it shows roughly the kind of phrasing that is enough to elicit a nice reduction from an expert
|
| S Mar 13, 2011 at 8:09 | history | suggested | Jacob | CC BY-SA 2.5 |
grammar and latex
|
| Mar 13, 2011 at 1:52 | review | Suggested edits | |||
| S Mar 13, 2011 at 8:09 | |||||
| Mar 11, 2011 at 5:22 | history | edited | Kaveh |
edited tags
|
|
| Nov 10, 2010 at 20:03 | history | edited | Suresh Venkat |
edited tags
|
|
| Nov 10, 2010 at 15:57 | comment | added | Peter Shor | @Tusyoshi: I think we're still working out which problems should be allowed and which shouldn't (and remarkably, I think we're coming to a reasonable consensus). Your suggestion that it might not be suitable certainly contributed the process, so it was actually quite useful. | |
| Nov 10, 2010 at 12:55 | comment | added | Tsuyoshi Ito | Ok, ok, I was wrong even to suggest the possibility that the question might not be suitable on this website! (But to be honest, I am personally satisfied because I have learned which questions should be allowed and should not be allowed from the comments on this question.) Let me clarify two things: (1) No one has voted to close this question. (2) No one has stated that he/she thought that this question was a homework. On the contrary, several people (including me) stated that this question did not look like a homework, which is consistent with the asker’s comment. | |
| Nov 10, 2010 at 10:39 | comment | added | András Salamon | 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. | |
| Nov 10, 2010 at 10:13 | vote | accept | user2094 | ||
| Nov 10, 2010 at 7:00 | comment | added | Xorlev | Why even close those sorts of questions? It seems like the best way to draw in more people to theoretical CS. Taking a hardline "no easy problems" position is more likely to just drive a good chunk of userbase away. To a lot of people, ideas like these can be a dark art and having somewhere to go can be most helpful. If you only want "hard interesting questions" you're going to lose a lot of people. | |
| Nov 9, 2010 at 11:34 | comment | added | Tsuyoshi Ito | @arnab: Done. - | |
| Nov 9, 2010 at 11:33 | answer | added | Tsuyoshi Ito | timeline score: 16 | |
| Nov 8, 2010 at 22:42 | comment | added | Peter Shor | @user2094, I actually never thought this was a homework problem (homework problems tend to be somewhat more crisply formulated, and have fewer constraints that are extraneous to the solution). And indeed, Tsuyoshi's suggestion of Exact Cover by 3-Sets seems the best problem to use for reduction. My comment was to suggest to leave this question open, since I think we should only close easy homework problems. | |
| Nov 8, 2010 at 18:12 | comment | added | Suresh Venkat | @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) | |
| Nov 8, 2010 at 17:52 | comment | added | arnab | @Tsuyoshi: you should put your comment as an answer! | |
| Nov 8, 2010 at 17:28 | history | edited | user2094 | CC BY-SA 2.5 |
added 20 characters in body
|
| Nov 8, 2010 at 17:24 | comment | added | user2094 | I can assure the sceptics that this is not a homework question. Alone, I would have spent weeks and weeks trying to solve it. Thanks to the help of Tsuyoshi, I can concentrate on other things that are in the core of my work. Thanks. | |
| Nov 8, 2010 at 15:21 | comment | added | Suresh Venkat | just my .02, but this didn't sound like a homework problem to me. | |
| Nov 8, 2010 at 14:15 | comment | added | Tsuyoshi Ito | @Peter: Thanks, and I agree. I wrote the answer because I assumed that this was not a homework problem (I hope that my assumption was correct). Next time I will remember to ask motivations. | |
| Nov 8, 2010 at 14:04 | comment | added | Peter Shor | @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. | |
| Nov 8, 2010 at 13:10 | comment | added | Tsuyoshi Ito | The problem is NP-hard because it contains the Exact Cover by 3-Sets as a special case (set X=1 and consider the case where every customer wants exactly three goods). I am not sure if we want questions at this level. | |
| Nov 8, 2010 at 12:40 | comment | added | Tsuyoshi Ito | I corrected some obvious errors in markup, but please make sure everything is shown as you intended. More on rereading your question. | |
| Nov 8, 2010 at 12:39 | history | edited | Tsuyoshi Ito | CC BY-SA 2.5 |
fixed markup
|
| Nov 8, 2010 at 10:38 | answer | added | Raphael | timeline score: -3 | |
| Nov 8, 2010 at 10:27 | comment | added | user2094 | Yes Y is common. I edited the question. thank you for your interest. | |
| Nov 8, 2010 at 10:27 | history | edited | user2094 | CC BY-SA 2.5 |
added 177 characters in body
|
| Nov 8, 2010 at 10:24 | comment | added | user2094 | the (-1) is to limit the number of pieces whose weight is greater than 1 kg, so the constraint favor the pieces of 1kg. | |
| Nov 8, 2010 at 10:21 | comment | added | Suresh Venkat | The constraint \sum (p_i -1) < Y is a little odd. Why the "-1" ? and is it the same Y for all customers ? | |
| Nov 8, 2010 at 9:50 | history | asked | user2094 | CC BY-SA 2.5 |