2021 Faculty Courses School of Computing Undergraduate major in Mathematical and Computing Science
Combinatorial Algorithms
- Academic unit or major
- Undergraduate major in Mathematical and Computing Science
- Instructor(s)
- Hanna Sumita / Makoto Yamashita
- Class Format
- Lecture
- Media-enhanced courses
- -
- Day of week/Period
(Classrooms) - 5-6 Mon (W321) / 5-6 Thu (W321)
- Class
- -
- Course Code
- MCS.T322
- Number of credits
- 200
- Course offered
- 2021
- Offered quarter
- 4Q
- Syllabus updated
- Jul 10, 2025
- Language
- Japanese
Syllabus
Course overview and goals
This course will cover representative combinatorial optimization problems and their methods to solve the problems. Real world problems are modeled as optimization problems by extracting the vital constraints and objectives. It is practically important to solve the optimization problems efficiently. For this end, we need to investigate and utilize a specific property and structure of each problem. This course describes fundamental "combinatorial" optimization problems and their algorithms using their own properties. In addition, this course explains the theory on combinatorial structures and algorithms.
The aim of this course is to give knowledge on fundamental combinatorial optimization problems and their algorithms, and give mathematical tools to argue the performance of the algorithms.
Course description and aims
By the end of this course, students will be able to:
1) Recognize fundamental combinatorial optimization problems appearing in real world situations.
2) Have a vague idea of methods to solve those combinatorial optimization problems.
3) Explain roughly the performance of methods from a theoretical perspective.
Keywords
combinatorial optimization, algorithm, online optimization, dynamic programming, modeling
Competencies
- Specialist skills
- Intercultural skills
- Communication skills
- Critical thinking skills
- Practical and/or problem-solving skills
Class flow
In each class we focus on one combinatorial optimization problem. Students learn its applications and basic methods to solve the problem.
Course schedule/Objectives
| Course schedule | Objectives | |
|---|---|---|
| Class 1 | Introduction to combinatorial optimization | Evaluation of the grade will be explained |
| Class 2 | Shortest path problem | |
| Class 3 | Maximum flow problem | |
| Class 4 | Minimum cost flow problem | |
| Class 5 | Maximum matching problem | |
| Class 6 | Stable marriage problem | |
| Class 7 | Matroid | |
| Class 8 | Review of Classes 1-7 and advanced topics | |
| Class 9 | Knapsack problem and approximation algorithms | |
| Class 10 | Knapsack problem and dynamic programming | |
| Class 11 | Traveling salesman problem | |
| Class 12 | Submodular function maximization problem | |
| Class 13 | Online problems | |
| Class 14 | Secretary problem | Final report |
Study advice (preparation and review)
To enhance effective learning, students are encouraged to spend approximately 100 minutes preparing for class and another 100 minutes reviewing class content afterwards (including assignments) for each class.
They should do so by referring to textbooks and other course material.
Textbook(s)
We do not assign textbooks. We will use course materials that are based on the following books.
Reference books, course materials, etc.
B. Korte and J. Vygen, "Combinatorial Optimization: Theory and Algorithms", Springer, 2018.
A. Schrijver, "Combinatorial Optimization: Polyhedra and Efficiency", Springer, 2003.
M. Shigeno, "Network Optimization and Algorithms （ネットワーク最適化とアルゴリズム)", Asakura-Shoten, 2010. (Japanese)
Y. Kawahara and K. Nagano, "Submodular Optimization and Machine Learning (劣モジュラ最適化と機械学習)", Kodansya, 2015. (Japanese)
All course materials will be uploaded on OCW-i.
Evaluation methods and criteria
Students will be assessed on the final report and quizzes.
Related courses
- MCS.T302 ： Mathematical Optimization
Prerequisites
No prerequisites are necessary, but enrollment in the related course (Mathematical Optimization) is desirable.