MATH 7594 - Integer Programming

Summer 2010 Registration MATH 7594
Every three years. A Ph.D. level course that uses linear programming (5593), especially polyhedral theory, to introduce concepts of valid inequalities and superadditivity. Early group-theoretic methods by Gomory and Chvatal’s rounding function are put into modern context, including their role in algorithm design and analysis. Duality theory and relaxation methods are presented for general foundation and analyzed for particular problem classes. Among the special problems considered are knapsack, covering, partitioning, packing, fix-charge, traveling salesman, generalized assignment matchings. Matroids are introduced and some greedy algorithms are analyzed. Additional topics, which vary, include representability theory, heuristic search and complexity analysis. Prereq: MATH 5593.Semester Hours: 3to 3
Registration is changing. Visit our website for details ucdenver.edu/registration.