Minimizing Variable-Weighted X3SAT
Stefan Porschen, Galyna Plagge · 2010
Abstract—In this paper, we present an upper bound of O(2 0.1625n) for the minimum-weight exact 3-satisfiability problem (MINW-X3SAT) getting as input 3-CNF formulas over n real-valued weighted propositional variables. This problem is NP-hard and the best previous result is an exact algorithm solving MINW-XSAT with no restrictions on clause length in