A universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything in between - Computer Science > Data Structures and AlgorithmsReport as inadecuate




A universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything in between - Computer Science > Data Structures and Algorithms - Download this document for free, or read online. Document in PDF available to download.

Abstract: In this paper we introduce -hybrid- Max 2-CSP formulas consisting of -simpleclauses-, namely conjunctions and disjunctions of pairs of variables, andgeneral 2-variable clauses, which can be any integer-valued functions of pairsof boolean variables. This allows an algorithm to use both efficient reductionsspecific to AND and OR clauses, and other powerful reductions that require thegeneral CSP setting. We use new reductions introduced here, and recentreductions such as -clause-learning- and -2-reductions- generalized to oursetting-s mixture of simple and general clauses.Parametrizing an instance by the fraction p of non-simple clauses, we give anexact exponential-time algorithm that is the fastest known polynomial-spacealgorithm for p=0 which includes the well-studied Max 2-Sat problem but alsoinstances with arbitrary mixtures of AND and OR clauses; the only efficientalgorithm for mixtures of AND, OR, and general integer-valued clauses; and tiedfor fastest for general Max 2-CSP p=1. Since a pure 2-Sat input instance maybe transformed to a general CSP instance in the course of being solved, thealgorithm-s efficiency and generality go hand in hand.Our algorithm analysis and optimization are a variation on the familiarmeasure-and-conquer approach, resulting in an optimizing mathematical programthat is convex not merely quasi-convex, and thus can be solved efficiently andwith a certificate of optimality. We produce a family of running-timeupper-bound formulas, each optimized for instances with a particular value of pbut valid for all instances.



Author: Serge Gaspers, Gregory B. Sorkin

Source: https://arxiv.org/



DOWNLOAD PDF




Related documents