Timeline for Hardness of combinatorial optimization after adding one constraint
Current License: CC BY-SA 2.5
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 29, 2009 at 9:04 | comment | added | Andrew | Flipping it around like that is an interesting way of thinking about the question. I'm not exactly sure what it means to trivialize a perfect matching problem--something along the lines that a greedy algorithm will be optimal? Anyhow, this is definitely the sort of thing I would like to learn more about. Do you know of any relevant terminology or references that can be used to describe the difference between subset sum and matching in this regard? | |
| Dec 25, 2009 at 21:14 | comment | added | Jonah Ostroff | (Er, where n is the number of vertices.) | |
| Dec 25, 2009 at 21:13 | comment | added | Jonah Ostroff | By contrast, it's pretty unlikely that you can trivialize the problem of finding a perfect matching in a graph by adding just one edge. I haven't read all that much about this, but I'd even go so far as to guess that you need O(n) edges in general to make this easy. | |
| Dec 25, 2009 at 21:09 | comment | added | Jonah Ostroff | Well, in all the examples we've seen, it might even be misleading to say that the question gets harder when you constrain the domain. What's really happening is that the question got easier because we added a new option, and then we took that option away to make it hard again. So we should look at hard problems and ask whether just one new option can make it trivial. For instance, in the problem of choosing numbers from a list which sum to a given value, this is made trivial by introducing just that value to your list. | |
| Dec 25, 2009 at 20:11 | vote | accept | Andrew | ||
| Dec 25, 2009 at 6:00 | comment | added | Andrew | Thanks, this is definitely getting closer to what I'm trying to understand (and apologies for not knowing how to ask the question crisply the first time). For the more general part, should I open up a new thread? (i.e. Is there some way of describing functions that determines whether they get harder or easier to optimize as you condition on more variable assignments?) My suspicion is that most practical functions get easier to optimize as you assign more variables, but I'd like to better understand when this is not the case. Thanks again. | |
| Dec 24, 2009 at 15:39 | history | answered | Jonah Ostroff | CC BY-SA 2.5 |