##
K. Subramani

West Virginia University

###
An Analysis of Quantified Linear Programs

Abstract:
Quantified Linear Programming is the problem of checking whether a
polyhedron specified by a linear system of inequalities is non-empty,
with respect to a specified quantifier string. Quantified Linear
Programming subsumes traditional Linear Programming, since in
traditional Linear Programming, all the program variables are
existentially quantified (implicitly), whereas, in Quantified Linear
Programming, a program variable may be existentially quantified or
universally quantified over a continuous range. On account of the
alternation of quantifiers in the specification of a Quantified Linear
Program (QLP), this problem is non-trivial. QLPs represent a class of
Declarative Constraint Logic Programs (CLPs) that are extremely rich
in their expressive power. The complexity of Quantified Linear
Programming for arbitrary constraint matrices is unknown. In this
paper, we show that polynomial time decision procedures exist for the
case in which the constraint matrix is Totally Unimodular (TUM). We
also provide a taxonomy of Quantified Linear Programs, based on the
structure of the quantifier string and discuss the computational
complexities of the constituent classes.

Host: Frank Pfenning

Appointments: Jennifer Landefeld

Principles
of Programming Seminars

Friday, February 7, 2003

3:30 p.m.

Wean Hall 8220