Heuristics for Length Bounded Cuts
| Název práce v češtině: | Heuristiky pro délkově omezené řezy |
|---|---|
| Název v anglickém jazyce: | Heuristics for Length Bounded Cuts |
| Klíčová slova: | teorie grafů|aproximační algoritmy|řezy|lineární programování|heuristiky |
| Klíčová slova anglicky: | graph theory|approximation algorithms|cuts|linear programming|heuristics |
| Akademický rok vypsání: | 2022/2023 |
| Typ práce: | diplomová práce |
| Jazyk práce: | angličtina |
| Ústav: | Katedra aplikované matematiky (32-KAM) |
| Vedoucí / školitel: | doc. Mgr. Petr Kolman, Ph.D. |
| Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 30.03.2023 |
| Datum zadání: | 30.03.2023 |
| Datum potvrzení stud. oddělením: | 29.05.2023 |
| Datum a čas obhajoby: | 11.09.2023 09:00 |
| Datum odevzdání elektronické podoby: | 21.07.2023 |
| Datum odevzdání tištěné podoby: | 24.07.2023 |
| Datum proběhlé obhajoby: | 11.09.2023 |
| Oponenti: | Mgr. Martin Koutecký, Ph.D. |
| Zásady pro vypracování |
| Problém minimálního řezu v grafu mezi danou dvojicí vrcholů je klasickým problémem kombinatorické optimalizace, který umíme efektivně řešit již od 50. let minulého století. Problém tzv. délkově omezeného řezu mezi danou dvojici vrcholů s a t, pro daný celočíselný parametr L, studovaný prvně počátkem 70. let minulého století, je nevinně vypadající modfikací problému obyčejného s-t řezu: úkolem je přerušit nikoli všechny cesty mezi s a t, ale pouze cesty mezi s a t délky nejvýšše L. Jedná se o NP-těžký problém. Nejlepší známé aproximační algoritmy mají aproximační poměr polynomiální v počtu vrcholů, nejlepší známé dolní odhady jsou pouze konstatní.
Úkolem diplomanta bude * pokusit se navrhout nové heuristiky pro tento problém, * implementovat známé aproximační algoritmy i nově navržené heuristiky, * porovnat výsledky implementovaných metod na konkrétních instancích problému. The minimum s-t cut in a graph is a classic problem in combinatorial optimization; since the 1950s, it has been known to be effectively solvable. The minimum length-bounded s-t cut problem, for a given integer parameter L, is much more challenging: the task is to cut only the paths between s and t of length at most L, not all paths between s and t. This is an NP-hard problem, with the best known approximation algorithms having a polynomial approximation ratio in the number of vertices. In contrast, the best known hardness lower bounds are only constant. The task of the student will be to * design new heuristics for the problem, * implement the known approximations and the new heuristics for the problem, * compare the results of the implemented algorithms on specific instances of the problem. |
| Seznam odborné literatury |
| Knihy:
R. K. Ahuja, T. L. Magnati, J. B. Orlin. Network Flows: Theory, Algorithms, and Applications, Pearson, 1993. A. Schrijver: Combinatorial Optimization - Polyhedra and Efficiency, Springer, 2003. Odborné články: Georg Baier, Thomas Erlebach, Alexander Hall, Ekkehard Köhler, Petr Kolman, Ondřej Pangrác, Heiko Schilling and Martin Skutella: Length-Bounded Cuts and Flows ACM Transactions on Algorithms, Volume 7, Issue 1, Article No. 4, 2010. Petr Kolman, Eden Chlamtáč: How to Cut a Ball without Separating: Improved Approximations for Length Bounded Cut. Proc. of 23rd Int. Conf. on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2020), pp. 41:1-41:17, 2020 |