DIMACS TR: 2001-33
Pseudo-Boolean Optimization
Authors: Endre Boros and Peter L. Hammer
ABSTRACT
This survey examines the state of the art of a variety of problems
related to pseudo-Boolean optimization, i.e. to the optimization
of set functions represented by closed algebraic expressions. The
main parts of the survey examine general pseudo-Boolean
optimization, the specially important case of quadratic
pseudo-Boolean optimization (to which every pseudo-Boolean
optimization can be reduced), several other important special
classes, and approximation algorithms.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2001/2001-33.ps.gz
DIMACS Home Page