TransWikia.com

For which c, d is Gap2SAT[c, d] in P (such that 0<c<d<1)?

Computer Science Asked on January 17, 2021

For which $c, d$ is $Gap2SAT[c, d]$ in $P$ (such that $0<c<d<1$)?

(I know if d=1 then for each c it will be in P, however with which c,d such that $0<c<d<1$ can I simply return YES?)

One Answer

Assuming the Unique Games Conjecture, your problem is solved for MAX-CUT in Ryan O'Donnell and Yi Wu, An optimal SDP algorithm for Max-Cut, and equally optimal Long Code tests, who determined the gap curve for this problem.

I am not aware of any such work for MAX-2SAT, but Per Austrin has essentially determined the optimal approximation ratio (again, assuming the Unique Games Conjecture) in his paper Balanced MAX 2-SAT might not be the hardest.

In celebrated work, Prasad Raghavendra has essentially determined the optimal approximation ratio for any constraint-satisfaction problem, again assuming the Unique Games Conjecture.

Answered by Yuval Filmus on January 17, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP