Original title:
Heuristiky pro délkově omezené řezy
Translated title:
Heuristics for Length Bounded Cuts
Authors:
Madaj, Pavel ; Kolman, Petr (advisor) ; Koutecký, Martin (referee) Document type: Master’s theses
Year:
2023
Language:
eng Abstract:
[eng][cze] This thesis deals with the problem of finding a minimum length-bounded cut in a graph. We first provide a brief overview of the problem and its applications. We then discuss the known theoretical results and approximation algorithms. We look at the existing linear programming formulations and propose a new one. A concise discussion on potential hard instances, utilized for testing our formulations, is also incorporated. The focus of our analysis is on the performance and behavior of our proposed linear programming family, contrasting it with the established natural formulation. We also compare the performance of various heuristics and approximation algorithms in practice by examining their behaviour on a large set of small instances. 1Táto práca sa zaoberá problémom nájdenia minimálneho dľžkovo obmedzeného rezu v grafe. Najprv poskytneme stručný prehľad problému a jeho aplikácií. Potom zhrnieme známe teoretické výsledky a aproximačné algoritmy. Skúmame existujúce formulácie li- neárnych programov pre tento problém a navrhujeme novú. Stručná diskusia o potenciál- nych ťažkých príkladoch, ktoré sú využité na testovanie našich formulácií, je tiež zahrnutá. Zameriavame sa na správanie našej navrhovanej rodiny lineárnych programov a porovná- vame ju s existujúcou prirodzenou formuláciou. Taktiež porovnávame výkonnosť rôznych heuristík a aproximačných algoritmov v praxi skúmaním ich správania sa na veľkej sade malých instancií. 1
Keywords:
graph theory|approximation algorithms|cuts|linear programming|heuristics; teorie grafů|aproximační algoritmy|řezy|lineární programování|heuristiky
Institution: Charles University Faculties (theses)
(web)
Document availability information: Available in the Charles University Digital Repository. Original record: http://hdl.handle.net/20.500.11956/185013