Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > JENS GRAMM:
All reports by Author Jens Gramm:

TR00-037 | 26th May 2000
Jens Gramm, Edward Hirsch, Rolf Niedermeier, Peter Rossmanith

New Worst-Case Upper Bounds for MAX-2-SAT with Application to MAX-CUT

The maximum 2-satisfiability problem (MAX-2-SAT) is:
given a Boolean formula in $2$-CNF, find a truth
assignment that satisfies the maximum possible number
of its clauses. MAX-2-SAT is MAXSNP-complete.
Recently, this problem received much attention in the
contexts of approximation (polynomial-time) algorithms
... more >>>




ISSN 1433-8092 | Imprint