Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with MAX-2-SAT:
TR04-032 | 5th February 2004
Ryan Williams

A new algorithm for optimal constraint satisfaction and its implications

We present a novel method for exactly solving (in fact, counting solutions to) general constraint satisfaction optimization with at most two variables per constraint (e.g. MAX-2-CSP and MIN-2-CSP), which gives the first exponential improvement over the trivial algorithm; more precisely, it is a constant factor improvement in the base of ... more >>>

TR16-163 | 25th October 2016
Matthew Hastings

Local Maxima and Improved Exact Algorithm for MAX-2-SAT

Given a MAX-2-SAT instance, we define a local maximum to be an assignment such that changing any single variable reduces the number of satisfied clauses. We consider the question of the number of local maxima hat an instance of MAX-2-SAT can have. We give upper bounds in both the sparse ... more >>>

ISSN 1433-8092 | Imprint