Course Description

MATH 8031. Combinatorial Optimization I

Course Code MATE 8031
Course Title Combinatorial Optimization I
Credits 3
Hours 3 per week
Prerequisites MATH 6881, MATH 8001
Description Elements of linear and integer programming: branch and bound methos and its application to combinatorial optimization problems. Network flow theory and its generalizations: statistical maximal flow, feasibility theorems and combinatorial applications, minimal cost flow problems, multi-terminal maximal flows, multi-commodity flows. Matching theory and its generalizations: matchings in bipartite graphs, size and structure of maximum matchings, bipartite graphs with perfect matchings, general graphs with perfect matchings, some graph-theoretical problems related to matchings, matchings and linear programming, matching algorithms, the f-factor problem, vertex packing and covering, some generalizations of matching problems.
Additional Information