The introduction to discrete optimization (MA2827) course at Ecole Centrale Paris will be taught by Karteek Alahari (Inria Grenoble – Rhone-Alpes) and Yuliya Tarabalka (Inria Sophia Antipolis – Méditerranée) in the 2016-’17 academic year.
Discrete optimization is concerned with the subset of optimization problems where some or all of the variables are confined to take a value from a discrete set. Examples include several important problems in various fields of applied mathematics and computer science, such as
- Finding the best (shortest, cheapest, most scenic) route from one place to another.
- Connecting cities using a road network that minimizes the cost.
- Selecting a subset of projects, each requiring a subset of available resources, to maximize profit.
- Finding the best assignment of students to universities.
In this course, we will study the fundamental concepts of discrete optimization such as greedy algorithms, dynamic programming and min-max relationships. Each concept will be illustrated using well-known problems such as shortest paths, minimum spanning tree, min-cut and max-flow. We will also identify which problems are easy and which problems are hard, and discuss how to obtain an approximate solution to hard problems.