Simplex
Twophase
Dijkstra
Prim
Kruskal
FordFulkerson
FAQ
Japanese/English

Instructor:
 Kenji Ikeda
 Room : C403
 Office Hours : Mon. 14:0017:00
Lectures:
 Time : Mon. & Fri. 17:5519:25
 Room : C20
Course Materials
 Textbook: No required text
 Reference book:
 C. H. Papadimitriou and K. Steiglitz : Combinatorial Optimization
 Algorithms and Complexity, PrenticeHall (1982)
 Vasek Chvatal : Linear Programming, W.H.Freeman, New York (1983)
 Notes: course notes(Sorry! Only in Japanese)
 Java applets: click on the left margin.
Announcement
Syllabus
1st 
Linear Programming (LP) Problem 
an LP problem

2nd 
from Geometric solution to Algebraic solution 
demo1 

A brief review of linear algebra. 

Basic Solutions. 
demo2 
3rd 
Fundamental Theorem 

Simplex Method 
demo3 1 ,
2 
4th 
Two Phase Method 
demo4 1 ,
2

5th 
Revised Simplex Algorithm 
6th 
Duality 

 Duality Theorem
 Complementary Slackness
 Farkas' Lemma

7th 
A brief review of Graphs and Networks 
8th 
Shortest Path Problem (Dijkstra's Algorithm ) 
demo8 1 ,
2,
3,
4

9th 
MST Problem (Krukal's Algorithm) 
demo9 1 ,
2,
3,
4


MST Problem (Prim's Algorithm) 
demo10 1 ,
2,
3,
4

10th 
Maximum FlowMinimum Cut Problem 
demo11 1 ,
2,
3,
4

11th 
Maximum Matching  Minimum Cover Problem 
demo12 1 ,
2,
3,
4

12th 



13th 



14th 
Trial exam 

15th 
Final Exam 

Grading and Exams:
Exams in the past
 Exams(Sorry! Only in Japanese)
