Combinatorial Algorithms for Flow Problems
| Název práce v češtině: | Kombinatorické algoritmy pro tokové problémy |
|---|---|
| Název v anglickém jazyce: | Combinatorial Algorithms for Flow Problems |
| Klíčová slova: | algoritmus|tok|kombinatorický|frank-wolfe|most helpful cycles |
| Klíčová slova anglicky: | algorithm|flow|combinatorial|frank-wolfe|most helpful cycles |
| Akademický rok vypsání: | 2019/2020 |
| Typ práce: | bakalářská práce |
| Jazyk práce: | angličtina |
| Ústav: | Informatický ústav Univerzity Karlovy (32-IUUK) |
| Vedoucí / školitel: | Mgr. Martin Koutecký, Ph.D. |
| Řešitel: | Bc. Richard Hladík - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 11.04.2020 |
| Datum zadání: | 11.04.2020 |
| Datum potvrzení stud. oddělením: | 11.06.2020 |
| Datum a čas obhajoby: | 02.07.2021 09:00 |
| Datum odevzdání elektronické podoby: | 27.05.2021 |
| Datum odevzdání tištěné podoby: | 27.05.2021 |
| Datum proběhlé obhajoby: | 02.07.2021 |
| Oponenti: | Laszlo Vegh |
| Zásady pro vypracování |
| Certain problems in combinatorial optimization have so far only been shown to be polynomial time solvable by use of linear programming. A prime example is the fractional Multi-commodity Flow problem (MCF), which has been called "the easiest problem solvable only by LP". In MCF, we are given a network with $k$ source-sink pairs $s_i$-$t_i$ together with a demand $d_i$ for each commodity, and the task is to find a flow for each commodity which satisfies the demand and the flows taken together do not violate edge capacities. Another problem only known to be solvable by LP is the $L$-bounded flow problem, in which we are given a network, a source-sink pair $s,t$, and an integer $L$, and the task is to find a largest possible flow which can be decomposed into $s$-$t$ paths of length at most $L$.
Obtaining an algorithm which does not rely on LP is desireable not only because it is likely to be more efficient, but also because it may provide new insights into the problem structure and provide new algorithm design approaches. For this reason our primary goal is to simply avoid LP, even if the resulting algorithm is (at least at first) asymptotically inferior. The goal of the project is to explore the usability of primal methods to construct such an algorithm. Primal methods work by iteratively improving some feasible solution, in contrast with dual methods which maintain a dual feasible solution. Two specific methods of interest are Frank-Wolfe-type algorithms, which have recently regained much interest and have been shown to converge quickly under relatively mild conditions, and circuit-augmentation methods which mirror Graver basis techniques from integer programming. Both aforementioned approaches can be seen as (wide) generalizations of cycle canceling-type algorithms for min-cost flow and similar problems, which inspires our hope that they would be applicable to other flow-type problems. |
| Seznam odborné literatury |
| * Lacoste-Julien, Simon, and Martin Jaggi. "On the global linear convergence of Frank-Wolfe optimization variants." Proceedings of the 28th International Conference on Neural Information Processing Systems-Volume 1. 2015.
* Onn, Shmuel. "Nonlinear discrete optimization." Zurich Lectures in Advanced Mathematics, European Mathematical Society (2010). * Eisenbrand, Friedrich, and Hunkenschröder, Christoph, and Klein, Kim-Manuel, and Koutecký, Martin, and Levin, Asaf, and Onn, Shmuel. "An algorithmic theory of integer programming." arXiv preprint arXiv:1904.01361 (2019). |