A PhD 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.Semester Hours: 3When Offered: Every three yearsPrerequisite: MATH 5593. Check for updates at courses.cudenver.edu.
This course information is from the 2009-2010 Downtown Campus Catalog. View this catalog.