Search This Blog

Computational Complexity

Computational Complexity

Instructor

Dr. Sarah M. Ryan

3014 Black Engineering, 294-4347

smryan@iastate.edu

Office Hours

TR 1:30 - 3:00 p.m.

Time & Place

MWF 12:00 - 12:50 p.m., 1034 Black

Please note: Contrary to ISU convention, we will begin at 12:00 promptly, not 12:10.

Text

Network Flows: Theory, Algorithms and Applications,by Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin, published by Prentice Hall, 1993

This book won the Institute for Operations Research and the Management Sciences (INFORMS) Lanchester Prize for the best contribution to OR/MS published in English in 1993.

Course Web Page

http://www.public.iastate.edu/~smryan/ie510/index.htm

Homework assignments and solutions and other material will be made available here as the semester progresses. Check it often!

Description

Many optimization problems can be modeled in terms of flows through networks. A network formulation can provide a clear visual representation of the problem and enable efficient solution methods. In particular, many discrete and nonlinear problems can be solved very efficiently as network flows.

Homework exercises will be assigned every 1-2 weeks to be handed in and graded. Students will complete semester projects chosen from their own interests or a suggested list. There will be three exams.

Tentative Topic List

The following sections in Ahuja, Magnanti and Orlin:

1.1-4 Introduction

2.1-5 Paths, Trees and Cycles

3.1-6 Algorithm Design and Analysis

4.1-5 Shortest Paths: Label-Setting Algorithms

5.1-6 Shortest Paths: Label-Correcting Algorithms

Chapters 4 and 5 will be supplemented with instructor’s notes on dynamic programming formulation, application and methods.

6.1-6 Maximum Flows: Basic Ideas

7.1-2,6-7 Maximum Flows: Polynomial Algorithms

9.1-7 Minimum Cost Flows: Basic Algorithms

11.1-5, 12 Minimum Cost Flows: Network Simplex Algorithms

12.1-6 Assignments and Matchings

13.1-5 Minimum Spanning Trees

19.7-9 Additional Applications

A "Tutorial on Computational Complexity" by Craig Tovey (2002) is in Interfaces Vol 32, No. 3. (If you follow this link from an ISU computer, you should be logged on to Extenza-INFORMS with full access to articles.)

Class notes:

Introduction

Chapter 1

Chapter 2 Please read section 2.2 before Monday, 8/30/04

Chapter 3

Chapter 4

Chapter 19

Chapter 5

Dynamic Programming Part 1

Dynamic Programming Part 2

Chapters 6 and 7

Chapter 9

Chapter 11

Chapter 12

Chapter 13

Chapter 16

No comments:

Post a Comment