Description
Introduction and systematic study of classes of discrete optimization problems that arise as theoretical or practical applications, of the underlying combinatorial optimization theory, and the analysis and design of efficient algorithms for their exact or approximate solution. The content is intended for students in computer science and in other disciplines such as mathematics, statistics, operations research, engineering, and bioinformatics.
Michael Grigoriadis
Credits: 3
Category: A
Prerequisites: DCS graduate admission requirements; background in design and analysis of algorithms.
Semesters Offered:Spring
Topics: Classes of network and combinatorial optimization problems. Computational complexity, NP-completeness & reductions. LP duality. Shortest paths & negative cycles; minimum cost-to-time cycles and Karp's minimum mean-cycle algorithm. Flow decomposition, max-flow min-cut and flow integrality theorems; combinatorial applications; lower bounds and circulations; min-flow max-cut and Dilworth's theorems. Augmenting path and preflow push algorithms. Scaling. Dynamic trees. Network connectivity. All-pairs and parametric min-cut problems; fractional programming: strength of a network, optimal res, maximum density subgraphs. Polynomial min-cost flow algorithms: Concurrent and multicommodity flows. Maximum and weighted matching: alternating paths and trees; Matchings and node covers. Matching on bipartite graphs: systems of distinct representatives; problem reductions; König-Egervary and Mendelsohn-Dulmage theorems; fast algorithms; max-min, Gilmore-Gomory, and Gale-Shapley matchings. Matchings on nonbipartite graphs: Tutte's and Berge's theorems; blossoms and shrinking; Edmonds' maximum and weighted matching algorithms; T-joins, postman tours, b-matching, Euclidean matching, approximate solution of TSP. Greeedy matroids. Multiterminal network synthesis. Approximation algorithms for several NP-hard problems, based on greedy, primal-dual and LP rounding techniques.
Expected Work: Four problem sets plus a final exam.
Class meets Tuesdays, 3:20-6:20 p.m. at Hill 120.
