Timeline for Hardness of combinatorial optimization after adding one constraint
Current License: CC BY-SA 2.5
2 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 24, 2009 at 1:18 | comment | added | Andrew | Thanks. Any $f$ with this sort of switching behavior of course will work--so clearly there are examples. I'm looking for a less contrived example. For example, if bipartite matching became hard when fixing $u_i$ to be matched to $v_j$, that would be ideal (I know that's not the case for bipartite matching--it's just an example). Also, are there conditions that can be placed on $f$ that cause this condition to hold or not hold? | |
| Dec 24, 2009 at 1:08 | history | answered | Jonah Ostroff | CC BY-SA 2.5 |