### Wymagania (prerequisites)
* algorytmy i struktury danych
* teoria programowania liniowego i calkowitoliczbowego (zalecany)
### Opis (description)
Bedziemy rozwazac problemy instalowania przepustowosci na krawedziach grafu
celem umozliwienia przesylu danych zgodnie ze spodziewanym zapotrzebowaniem na
transfer. Do tej kategorii mozna zaliczyc na przyklad problem minimalnego
drzewa Steinera, w ktorym nalezy polaczyc w jedna spojna skladowa dany zbior
wierzcholkow zwany terminalami. Zazwycazaj dazymy do minimalizacji lacznego
kosztu zainstalowanych polaczen.
Problemy tago typu sa najczesciej NP-trudne, dlatego skupiamy sie na
konstrukcji algorytmow aproksymacyjnych, czyli algorytmow, ktore w czasie
wielomianowym dostarczaja rozwiazan nie wiele drozszych od optimum. Jako
ograniczenia dolnego na koszt rozwiazania optymalnego najczesciej uzywamy
rozwiazania ulamkowego odpowiedniego programu liniowego.
### Program (program)
Problems:
* Steiner tree
* Steiner forest
* Generalized Steiner network
* Network design with degree bounds
* Single Sink Rent-or-Buy
* Connected Facility Location
LP-relaxations:
* standard undirected
* bidirected
* directed component based (for Steiner tree)
* Held&Karp LP for TSP
Related graph constructions:
* vertex sparsifiers
* edge sparsifiers
* expanders
### Literatura (references)
* David P. Williamson and David P. Shmoys. "The design of Approximation Algorithms" ISBN 978-0-521-19527-0
* oryginalne prace
