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.

In 2015-’16 this course was taught by Karteek Alahari and Anton Osokin (Inria de Paris), and by M. Pawan Kumar before that.