Heuristics for Length Bounded Cuts
| Thesis title in Czech: | Heuristiky pro délkově omezené řezy |
|---|---|
| Thesis title in English: | Heuristics for Length Bounded Cuts |
| Key words: | teorie grafů|aproximační algoritmy|řezy|lineární programování|heuristiky |
| English key words: | graph theory|approximation algorithms|cuts|linear programming|heuristics |
| Academic year of topic announcement: | 2022/2023 |
| Thesis type: | diploma thesis |
| Thesis language: | angličtina |
| Department: | Department of Applied Mathematics (32-KAM) |
| Supervisor: | doc. Mgr. Petr Kolman, Ph.D. |
| Author: | hidden - assigned and confirmed by the Study Dept. |
| Date of registration: | 30.03.2023 |
| Date of assignment: | 30.03.2023 |
| Confirmed by Study dept. on: | 29.05.2023 |
| Date and time of defence: | 11.09.2023 09:00 |
| Date of electronic submission: | 21.07.2023 |
| Date of submission of printed version: | 24.07.2023 |
| Date of proceeded defence: | 11.09.2023 |
| Opponents: | Mgr. Martin Koutecký, Ph.D. |
| Guidelines |
| 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. |
| References |
| 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 |