We will study a collection of advanced LP-based techniques including:
* various sampling techniques
* proving properties of vertex solutions via
uncrossing
* roud-or-cut method to derive approximation algorithm
The techniques will be presented mostly in the context of network design optimization problems, where a subset of edges (or vertices) of the input graph needs to be selected.
Part of the material will be from this book:
http://www.contrib.andrew.cmu.edu/~ravi/book.pdf
Part will be directly from research papers.
Me as an organizer would present a subset of the topics, but the success of the series depends on the availability of volunteers to join the effort.
Depending on the set of people who sign in, the presentations may be either in polish or in english.
However, there are essentially no source materials in polish available.
This seminar can be considered in relation with another one called "Spectral Graph Theory". Only the one that turns out to be more popular in the vote will be organized.
