The inequality-satisfiability problem Academic Article

abstract

• We define a generalization of the satisfiability problem (SAT) where each "clause" is an or-list of inequalities in n variables. This problem is NP-complete even when containing only two inequalities per "clause", but solvable in polynomial time when either the number of variables or the number of "clauses" is fixed. 2007 Elsevier B.V. All rights reserved.

authors

• Moreno-Centeno, Erick

published proceedings

• OPERATIONS RESEARCH LETTERS

author list (cited authors)

• Hochbaum, D. S., & Moreno-Centeno, E.

citation count

• 2

complete list of authors

• Hochbaum, Dorit S||Moreno-Centeno, Erick

publication date

• January 2008

publisher

• Elsevier  Publisher

published in

• Operations Research Letters  Journal

keywords

• Inequality-satisfiability
• Or-inequalities
• Parting Directions
• Satisfiability (sat)

Digital Object Identifier (DOI)

• 10.1016/j.orl.2007.05.005

start page

• 229

end page

• 233

volume

• 36

issue

• 2

URL

• http%3A%2F%2Fdx.doi.org%2F10.1016%2Fj.orl.2007.05.005

user-defined tag

• 10 Reduced Inequalities