Název: Heuristiky pro délkově omezené řezy
Překlad názvu: Heuristics for Length Bounded Cuts
Autoři: Madaj, Pavel ; Kolman, Petr (vedoucí práce) ; Koutecký, Martin (oponent)
Typ dokumentu: Diplomové práce
Rok: 2023
Jazyk: eng
Abstrakt: [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. 1 Tá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
Klíčová slova: teorie grafů|aproximační algoritmy|řezy|lineární programování|heuristiky; graph theory|approximation algorithms|cuts|linear programming|heuristics

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/185013

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-534931


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Diplomové práce