INFT 983�� ADVANCED TOPICS: NETWORK OPTIMIZATION�� SPRING 2002

Place & Time:�� S&T II, Room 128; Monday, 7:20 � 10:00

Instructor:�� Don Wagner

�� Telephone: 703-993-3806 / 703-696-4313

�� Office:� S&T II, Room 112 (generally available on Fridays)

Office Hours:�� By appointment

Text:�� Combinatorial Optimization by W. J. Cook, W. H. Cunningham, W. R. Pulleyblank, and A. Schrijver, John Wiley & Sons, 1998

Description:�� A rigorous treatment of classic problems in combinatorial optimization,

focusing on algorithms and associated polyhedral theory

Prerequisites:�� Linear programming, integer programming, and network flows

Course Outline:�� Introduction�� Chapter 1

�� Minimum Spanning Tree Problem�� Chapter 2

�� Kruskal�s Algorithm

�� Spanning Tree Polytope

�� Review of Shortest Paths and Maximum Flows�� Chapters 2-3

�� Minimum-Cost Flows�� Chapter 4

�� Primal Algorithms

�� Dual Algorithms

�� Matchings�� Chapter 5

�� Cardinality Matching Algorithm

�� Weighted Matching Algorithm

�� Matching Polytope

�� Postman problems

��

�� Possible additional topics:

Integrality of Polyhedra�� Chapter 6

�� Primal-Dual Approximation Algorithms

Grading:�� Grades will be determined by 5-6 homework sets distributed throughout the semester.�

All work is to be done independently.�

INFT 983���������� ADVANCED TOPICS: NETWORK OPTIMIZATION���������� SPRING 2002