Efficient Algorithms for Certain Satisfiability and Linear Programming Problems.
Abstract
We present efficient algorithms for certain of Linear Equations solving, Linear Programming, and SATisfiability testing. LE, LP, and SAT have all been studied in both the theoretical and the applied areas of Computer Science. Although many algorithms have been developed for these problems, there are large gaps between today's best algorithms and the best theoretical lower bounds. We do not eliminate these gaps, but instead present efficient algorithsm for LE, LP, and SAT (and for testing the truth of Quantified Boolean Formulas) for the cases in which there are at most two variables or literals per equation, inequality, or clause. These subcases seem to be the 'hardest' ones that are not as hard as the general problems. The algorithms for LE(2), 2-SAT, and 2-QBF are linear-time algorithms, and they are optimal except for constant factors. Our algorithm for the subcase of LP has a nonlinear worst-case bound, but the bound is better than for any general LP algorithm such as the polynomial-time algorithm by Khachiyan, and the algorithm seems to be of practical as well as theoretical importance. In the algorithms, we associate graphs with given problem instances. By performing searches on the graphs (in the LP case combined with a binary search technique), we contrast a solution or a satisfying truth assignment if one exists. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 01, 1980
- Accession Number
- ADA095411
Entities
People
- Bengt Ingemar Aspvall
Organizations
- Stanford University