Timeline for Is this minimization problem NP-Complete ?
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:19 | history | edited | CommunityBot |
replaced http://math.stackexchange.com/ with https://math.stackexchange.com/
|
|
| Jun 5, 2016 at 3:29 | history | edited | Sean Lawton | CC BY-SA 3.0 |
Minor edits.
|
| Aug 30, 2011 at 11:45 | comment | added | aaaaaa | The reason I think that the problem is np-complete is that here without checking all possible combinations it is very difficult to find the optimum config. What do you think about the np-completeness of this problem? | |
| Aug 30, 2011 at 11:45 | comment | added | aaaaaa | If I refine problem like this: How much of the n+k columns can be covered using m subsets each of size atmost b then I think it is possible to formulate it as a maximum independent set problem. We will form a graph of n+k vertices where each vertex corresponds to one column but the definition of edges is not clear to me (this is the main problem I am trying to solve). Then the maximum independent set of this graph will give us the maximum subset (of the n+k columns) that can be covered. | |
| Aug 29, 2011 at 3:21 | comment | added | aaaaaa | @all: Sorry, I typed it wrongly. It will be B has no "zero" rows or columns. Thanks for pointing that. I changed that in the main question. | |
| Aug 29, 2011 at 3:19 | history | edited | aaaaaa | CC BY-SA 3.0 |
deleted 2 characters in body
|
| Aug 28, 2011 at 21:59 | comment | added | Andreas Blass | @Prasenjit: I assume that Francois interpreted "no non-zero rows or columns" the same way I did, which would mean that B is the zero matrix. (A row or column (or any other sort of vector) is non-zero if at least one entry is non-zero.) I also assume that you meant something else. Please tell us what you meant. | |
| Aug 28, 2011 at 17:08 | comment | added | aaaaaa | @Martin and Thierry: Sorry for posting it twice. I will keep in mind what you have said next time I post. | |
| Aug 28, 2011 at 14:46 | comment | added | Thierry Zell | Prasenjit: to expand on Martin's remark, it is considered extremely poor form to post identical questions on MO and SE at the same time. The recommended course of action is to post it on SE, and then only repost on MO after about a week, if it looks like the SE question is going nowhere. | |
| Aug 28, 2011 at 14:07 | comment | added | Martin Sleziak | This question was also posted here: math.stackexchange.com/questions/60322/… | |
| Aug 28, 2011 at 14:03 | comment | added | François G. Dorais | Are you sure you want B to have "no non-zero rows or columns"? | |
| Aug 28, 2011 at 14:02 | history | edited | François G. Dorais |
edited tags
|
|
| Aug 28, 2011 at 13:36 | history | asked | aaaaaa | CC BY-SA 3.0 |