Timeline for Greedy MAX SAT approximation ratio
Current License: CC BY-SA 3.0
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 9, 2014 at 23:55 | comment | added | mathemagic | I see the modification now: $(x \vee y) \wedge (x \vee z) \wedge \neg x$. Thank you again. | |
| Mar 9, 2014 at 23:33 | comment | added | mathemagic | Thank you both. The Johnson's algorihm, as I find it, usually has the order of variables determined in advance. That leads to tight examples for 2/3 ratio such as $(x \vee \neg y) \wedge (\neg x \vee y) \wedge \neg y$ where we set $x=1, y=0$. However, such example doesn't work for the algorithm described. Do you by chance see, how to adapt it? | |
| Mar 9, 2014 at 23:27 | history | answered | Sasho Nikolov | CC BY-SA 3.0 |