|
|||||
|
|
The inequality-satisfiability problem |
|
| Authors: | Dorit S Hochbaum Erick Moreno-Centeno |
| Institution: | a Department of Industrial Engineering and Operations Research, 4181 Etcheverry Hall, Mail Code 1777, University of California, Berkeley, CA 94720-1777, USA b Walter A. Haas School of Business, University of California, Berkeley, USA |
| 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. |
| Keywords: | Satisfiability (SAT) Inequality-satisfiability Or-inequalities Parting directions |
| 本文献已被 ScienceDirect 等数据库收录！ | |