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, interested in developing algorithms for large-scale computation with provable performance guarantees.
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. Packing & covering LPs. LP duality, primal-dual schema in designing exact and approximation algorithms. Dynamic programming; negative cycles, Karp's minimum mean-cycle algorithm, minimum cost-to-time ratio cycles. Applications
Flows&Cuts: Decomposition, max-flow min-cut and integrality theorems. combinatorial implications. Review of augmenting-paths. Preflow-push algorithms, scaling, data structures, amortized analysis; optimal closures, parametric minimum s,t-cuts, fractional programming, combinatorial applications. Lower bounds, circulations, min-flow max-cut theorem. Posets & Dilworth's theorem. Scheduling. Network connectivity. Routing. Deterministic & randomized global minimum cut algorithms. All-pairs minimum cuts, Gomory-Hu trees. Greedy matroids. Multiterminal network synthesis. Min-cost flows: Polynomial algorithms, scaling & dynamic trees. FPTAS for fractional concurrent multicommodity flows, packet routing, network design.
Matching: Alternating paths and trees; Matchings & node covers; SDRs & Hall's theorem; Konig, König-Egerváry, Mendelsohn-Dulmage theorems. Max-min, Gilmore-Gomory and Gale-Shapley matchings. Nonbipartite matching: Tutte-Berge formula, Edmonds' blossom algorithm; weighted perfect matching; T-joins, postman tours, general shortest paths, b-matching, Euclidean matching, metric-TSP.
Approximation algorithms for a number of NP-hard problems based on greedy, primal-dual and LP rounding.
(The exact list of topics covered in a semester may differ somewhat from the above.)
Expected Work: Four problem sets, a midterm and a final.
Schedule: M 1:40-4:40 pm, Hill 254 (Click on Class URL, top left box).
