West Virginia Univrsity

A Combination
Algorithm for Horn Programs

Abstract:

In this talk we discuss a simple, greedy algorithm for a class of linear programs called Horn programs. This algorithm, which we term as the

Inasmuch as Horn constraints subsume difference constraints, and all known
algorithms for the problem of checking feasibility in Difference Constraint
Systems run in time *Ω(m·n)*, the running time of our algorithm is
only a factor *n* worse than the best known running time for checking
feasibility in Difference Constraint Systems. Horn programs arise in a
number of application areas including econometrics and program verification;
consequently, their study is well-motivated. An important feature of our
algorithm is that it uses only one operator, viz., addition.

We also show that our algorithm can identify the linear and lattice point
feasibility of Extended Horn Systems in *O(m·n²)* time.

Host: Frank Pfenning

Appointments: ameliaw@cs.cmu.edu

Friday, August 7, 2009

3:30 p.m.

Wean Hall 8220

Principles
of Programming Seminars