Return to Colloquia & Seminar listing
Optimal Solutions to Integer Programs
Student-Run Research| Speaker: | Prof. Rekha Thomas, Texas A&M University / UC San Diego. |
| Location: | 593 Kerr |
| Start time: | Thu, Mar 9 2000, 3:10PM |
Description
It is well known that a basic optimal solution to a linear
program does not have more non-zero entries than the rank of
its coefficient matrix. However, an optimal solution to
the corresponding integer program has no such bound on the
size of its support. In this talk I will discuss some old
and new theoretical methods for preprocessing a family of integer programs
so that the optimal solution to any given program in the family
can be obtained by solving a simpler set of problems. These
methods can also be viewed as ways to correct the linear optima
to the corresponding integer optima.