ὅδε οἶκος, ὦ ἑταῖρε, μνημεῖον ἐστιν ζῴων τῶν σοφῶν ἀνδρῶν, καὶ τῶν ἔργων αὐτῶν

Existential Polytime and Polyhedral Combinatorics

A minicourse by Jack Edmonds in Belgrade, June 4 - 7, 2015.
Mathematical Institute of the Serbian Academy of Sciences and Arts



For thousands of years, and even now in group theoretic geometry, the beautiful symmetries of a handful of polyhedra with a handful of facets have been at the center of refined mathematics. Since the advent of Turing's computers and operations research, beauty has been found in polyhedra regardless of symmetry, with facets as numerous as the stars.

Linear-algebra theory is being nudged by great systems of linear inequalities as inputs.`Polyhedra' means their solution sets. `Existential polytime', i.e. NP, means certifiable in polynomial time when true. The course will explore some of the polyhedra which have edged aside the dodecahedron.

Topics of the various days are related but presentations will be independent with some reference to each other. Presentation each day will be in the morning, 10am - 12am, with elaboration and tutorial during the refreshment after the lecture.

Thursday. Combinatorial structure of paths, network flows, optimum assignment, stable marriage.
Friday. Routes for Chinese postmen, traveling salesmen, and itinerant preachers, optimum systems of trees and branchings.
Saturday. Submodular set functions and polymatroids. The greedy algorithm. Combinatorics of (linear) dependence. Duality and contractions. Exact matrix implementations. Matroid partitioning and Lehman's game. Polymatroid intersections. Submodular flows. The ellipsoid method for exponentially large linear programs.
Sunday. Some Pure Math of Classical Game Theory. Bimatrix games and beautiful-mind Nash equilibria; Room partitioning and PPA. N-person cooperative games; set functions and cores. Algorithms and algorithmic difficulties.

Some of the Resources. Optima interview;
(Discrete) Optimization Stories, http://www.zib.de/groetschel/publications/OptimizationStories.pdf,
Books on Combinatorial Optimization including
Schrijver, Combinatorial Optimization: Polyhedra and Efficiency (available digitally)

Jack Edmonds, 3^4, the teacher, is the Dumbledore, Gandalf, Merlin, Obi-Wan Kenobi, of the subject.
Muggles are welcome.

Please register at no cost: graphopt@mi.sanu.ac.rs

GALERY