Combinatorial Algorithms

Academic unit or major

Undergraduate major in Mathematical and Computing Science

Instructor(s)

Hanna Sumita / Yu Yokoi / Makoto Yamashita

Class Format

Lecture (Face-to-face)

Media-enhanced courses

-

Day of week/Period
(Classrooms)

5-6 Mon / 5-6 Thu

Class

-

Course Code

MCS.T322

Number of credits

200

Course offered

2024

Offered quarter

4Q

Syllabus updated

Mar 14, 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.
2) Solve these fundamental combinatorial optimization problems by using algorithms.
3) Analyze the performance of algorithms from a theoretical perspective.

Keywords

combinatorial optimization, algorithm, modeling, online optimization, dynamic programming

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

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 T2SCHOLA.

Evaluation methods and criteria

Students will be assessed based mainly on the final report.

Related courses

• MCS.T302 ： Mathematical Optimization
• MCS.M421 ： Discrete Optimization

Prerequisites

No prerequisites are necessary, but enrollment in the related course (Mathematical Optimization) is desirable.