Timeline for Solve NP-hard type problems with linear programming
Current License: CC BY-SA 4.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 25, 2023 at 14:06 | comment | added | Rodrigo de Azevedo | If you have a convex polytope whose vertices are integral, then you can solve integer programs via linear programming. But these are extremely special instances | |
| Dec 24, 2023 at 15:46 | history | edited | RobPratt |
edited tags
|
|
| Dec 24, 2023 at 10:10 | history | edited | Daniele Tampieri | CC BY-SA 4.0 |
Minor grammar improvements and Math Jaxing
|
| Dec 24, 2023 at 4:23 | review | Close votes | |||
| Jan 1 at 3:04 | |||||
| Dec 24, 2023 at 3:00 | comment | added | Jason Gaitonde | I am not exactly sure what you’re asking, but there is provably no polynomial size linear program such that any projection of the feasible region yields the TSP polytope (i.e. the convex hull of the indicator vectors of Hamiltonian cycles). This is a famous result of Fiorini, Massar, Pokutta, Tiwary and de Wolf (arxiv.org/abs/1111.0837). | |
| S Dec 24, 2023 at 1:36 | review | First questions | |||
| Dec 24, 2023 at 4:05 | |||||
| S Dec 24, 2023 at 1:36 | history | asked | Juan Carlos | CC BY-SA 4.0 |