Journal of the ACM Bibliography

Michel Conforti and Gérard Cornuéjols. A class of logic problems solvable by linear programming. Journal of the ACM, 42(5):1107-1113, September 1995. [BibTeX entry]

In propositional logic, several problems, such as satisfiability, MAX SAT and logical inference, can be formulated as integer programs. In this paper, we consider sets of clauses for which the corresponding integer programs can be solved as linear programs. We prove that balanced sets of clauses have this property. Copyright 1995 by ACM, Inc.

The abstract is also available as a LaTeX file, a DVI file, or a PostScript file.

Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems -- computations on discrete structures; G.2.1 [Discrete Mathematics]: Combinatorics -- combinatorial algorithms

General Terms: Algorithms

Additional Key Words and Phrases: Balanced matrices, linear programming, propositional logic

Selected references


  • Journal of the ACM homepage
  • Bibliography top level
  • Journal of the ACM Author Index
  • Search the HBP database