A number of recent authors have given exponential-time algorithms for optimization problems such as Max Cut and Max Independent Set, or for the more general class of Constraint Satisfaction Problems (CSPs). In this paper, we introduce the the class of Generalized Constraint Satisfaction Problems (GCSPs), where the score functions are polynomial-valued rather than real-valued functions. We show that certain reductions used for solving CSPs can be extended to identities for the “partition function” of a GCSP, leading to relatively e±cient exponential-time (polynomial-space) algorithms for solving a GCSP. This also enables us (at the cost of only a polynomial factor in time) to modify existing
algorithms for optimizing CSPs into algorithms that count solutions or sample uniformly at random. Using an extra variable allows us to solve Max Bisection or calculate the partition function of the Ising Model, problems that were previously inaccessible with this approach.
By: Alexander D. Scott; Gregory B. Sorkin
Published in: RC23935 in 2006
LIMITED DISTRIBUTION NOTICE:
This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.
Questions about this service can be mailed to reports@us.ibm.com .