Description
Systematic study of classes of discrete optimization problems that arise as theoretical or computer science 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: A course on the design and analysis of algorithms. (Check with the Instructor if you need a special permission to register.)
Semesters Offered:Spring
Topics: Introduction & brief review: Classes of network and combinatorial optimization problems; computational complexity, NP-completeness & problem reductions, LP duality and graph optimization problems. Detecting negative cycles; minimum cost-to-time cycles, Karp's minimum mean-cycle algorithm. Applications. Flow decomposition, max-flow min-cut and flow integrality theorems; combinatorial applications; lower bounds and circulations; min-flow max-cut and Dilworth's theorem. Scheduling applications. Fast augmenting path and preflow push algorithms. Scaling & data structres. Network connectivity. Routing. All-pairs and parametric min-cut problems; fractional programming: strength of a network, optimal res, maximum density subgraphs. Polynomial min-cost flow algorithms. Approximate concurrent and multicommodity flow algorithms. Maximum and weighted matching: alternating paths and trees; Matchings and node covers; 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 metric-TSP tours. Greeedy matroids. Multiterminal network synthesis. Approximation algorithms for several NP-hard problems based on greedy, primal-dual and LP rounding.
Expected Work: Four problem sets, a midterm and a final.
Schedule: W 1:40-4:40 pm, Hill 254
