### Prerequisites
* Required: algorithms and data structures
* Would help: linear programming
### Course description
We will discuss combinatorial optimization problems in the context of providing connectivity. In a typical setting, given an input graph G=(V,E) and connectivity requirements between selected pairs of vertices, the goal is to find a set of edges of minimal cost that provides the required connectivity.
Perhaps the simplest problem of this type is the min cost spanning tree. A slight extension that already makes the problem highly nontrivial is the Steiner tree setting in which only a selected set of vertices called terminals is required to be connected.
Most of the settings of our interest are NP-hard to solve optimally and we will study approximation algorithms that find close to optimal solutions in polynomial time. Notably, many of the algorithms that will be discuss crucially exploits properties of linear relaxations of the studied problem.
### Program
Providing connectivity:
* Steiner tree
* Steiner forest
* Prize collecting Steiner forest
* Generalized Steiner network
* Network design with degree bounds
Augmenting connectivity:
* Tree augmentation
* Cactus augmentation
LP-relaxations:
* standard undirected
* bidirected cut relaxation (BCR)
* directed component based (for Steiner tree)
* Held&Karp LP for TSP
Algorithms:
* LP rounding
* primal-dual
* local search
* relative greedy
### Literature
* David P. Williamson and David P. Shmoys. "The design of Approximation Algorithms" ISBN 978-0-521-19527-0
* research papers
