Return to Colloquia & Seminar listing
Optimal Solutions to Integer Programs
Student-Run Research Seminar| Speaker: | Prof. Rekha Thomas, Texas A&M University / UC San Diego. |
| Location: | 593 Kerr |
| Start time: | Thu, Mar 9 2000, 3:10PM |
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.