The Evergreen Game: The Promise of Polynomials to Boost Boolean MAX-CSP Solvers

After a long absence from Generalized Satisfiability research, we re-enter the field from the point of view of empirical algorithmics (see e.g. http://www.cs.ubc.ca/~hutter/EARG.shtml).

This paper introduces a simple game that sheds new light on MAX-CSP.

@TECHREPORT{Evergreen:April-07,
AUTHOR = "Ahmed Abdelmeged and Christine D. Hang and Daniel Rinehart and Karl J. Lieberherr",
TITLE = "{The Evergreen Game: The Promise of Polynomials to Boost Boolean MAX-CSP Solvers}",
INSTITUTION = "Northeastern University",
YEAR = 2007,
MONTH = "April",
NUMBER = "NU-CCIS-07-03"
}

Paper.

Software available

Methematica source. This code greatly helps to play the Evergreen(3,2) game well. Produced by Daniel Rinehart.

Symmetric Instance Generator. A simple program to generate symmetric formulas for the two relations NOT(A) and OR(B,C). Produced by Ahmed Abdelmeged.