3. 강의목표
This course treats an important class of problems in the areas of Combinatorial Optimization.
Various combinatorial optimization algorithms for problems such as Shortest Path, Max Flow,
Matching, Assignment are investigated from a Primal-Dual perspective.
The concept of Matroid and NP-completeness are also discussed to better understand
the fundamental differences between easy and hard combinatorial problems.
4. 강의선수/수강필수사항
IMEN 261 Introduction to Operations Research (or separate approval)
5. 성적평가
3 Exams 25% each, 75% total
3 Assignments 7% each, 21% total
Class Participaption 4%
6. 강의교재
| 도서명 |
저자명 |
출판사 |
출판년도 |
ISBN |
|
Combinatorial Optimization - Algorithms and Complexity. Dover Edition, 1998 (Originally published by Prentice Hall, 1982)
|
C.H. Papadimitriou and K. Steiglitz.
|
Prentice Hall
|
1982
|
0-13-152462-3
|
7. 참고문헌 및 자료
any elementary Operations Research textbooks
8. 강의진도계획
9월 6일 Mon Chapter 1 Introduction
9월 8일 Wed Chapter 2 Simplex algorithm
9월 13일 Mon Chapter 3 Duality
9월 15일 Wed Chapter 4 Revised Simplex
9월 20일 Mon Chuseok
9월 22일 Wed Chuseok
9월 27일 Mon Chapter 5 Primal-Dual Algorithm
9월 29일 Wed Ch6 P-D Algorithm for MaxFlow and Shortest Path
10월 4일 Mon Alt Holiday
10월 6일 Wed Ch7 PD Scheme for Min-cost Flow
10월 11일 Mon Ch7 PD Scheme for Min-cost Flow
10월 13일 Wed Review & HW1 Due
10월 18일 Mon Exam 1
10월 20일 Wed Ch8 Algorithm and complexity
10월 25일 Mon Ch9 Efficient algorithm for MaxFlow
10월 27일 Wed Ch10 Matching
11월 1일 Mon Ch10 Bi-partite Matching
11월 3일 Wed Ch10 Non-Bi-partite Matching
11월 8일 Mon Ch11 Weighted Bi-partite Matching
11월 10일 Wed Ch11 Weighted Non-Bi-partite Matching
11월 15일 Mon Review & HW2 Due
11월 17일 Wed Exam 2
11월 22일 Mon Ch12 Matroid
11월 24일 Wed Ch12 Matroid
11월 29일 Mon Ch12 Matroid
12월 1일 Wed Ch13 Integer Programming
12월 6일 Mon Ch13 Integer Programming
12월 8일 Wed Ch13 Integer Programming
12월 13일 Mon Review & HW3 Due
12월 15일 Wed Exam 3
9. 수업운영
Whenever the COVID 19 situation permits, the class will be offered off-line but on-line, otherwise.
Following all COVID 19 guide lines, all efforts are to be made to have exams off-line.
All the on-line classes are to be recorded for later study.
10. 학습법 소개 및 기타사항
The attendance is essential, especially for off-line sessions.
You must catch up with missed on-line clases by watching the video recording
that are to be made available after every on-line class.
11. 장애학생에 대한 학습지원 사항
- 수강 관련: 문자 통역(청각), 교과목 보조(발달), 노트필기(전 유형) 등
- 시험 관련: 시험시간 연장(필요시 전 유형), 시험지 확대 복사(시각) 등
- 기타 추가 요청사항 발생 시 장애학생지원센터(279-2434)로 요청