Binární paint shop problém
Název práce v češtině: | Binární paint shop problém |
---|---|
Název v anglickém jazyce: | Binary paint shop problem |
Klíčová slova: | binární paintshop problém|aproximační algoritmus |
Klíčová slova anglicky: | binary paintshop problem|approximation algorithm |
Akademický rok vypsání: | 2023/2024 |
Typ práce: | bakalářská práce |
Jazyk práce: | čeština |
Ústav: | Informatický ústav Univerzity Karlovy (32-IUUK) |
Vedoucí / školitel: | doc. Mgr. Robert Šámal, Ph.D. |
Řešitel: | Jiří Kalvoda - zadáno a potvrzeno stud. odd. |
Datum přihlášení: | 23.10.2023 |
Datum zadání: | 24.10.2023 |
Datum potvrzení stud. oddělením: | 24.10.2023 |
Datum odevzdání elektronické podoby: | 09.05.2024 |
Oponenti: | Mgr. Michal Opler, Ph.D. |
Zásady pro vypracování |
V tomto problému hledáme optimální rozvrh pro továrnu, která barví frontu aut dvěma barvami. V idealizovaném případě je ve frontě každé auto ve dvou exemplářích, které musí dostat rozdílnou barvu. Při zachování této podmínky se snažíme, z praktických důvodů, minimalizovat počet změn barvy mezi sousedními auty.
V článcích [1,3,4] je navrženo několik aproximačních algoritmů a ukázáno, že v obecnosti je problém výpočetně složitý. Úkolem studenta bude jednak přehledně shrnout dosažené výsledky, jednak vyzkoušet nové přístupy, například s využitím semidefinitního programování. |
Seznam odborné literatury |
[1] S.D. Andres, W. Hochstättler: Some heuristics for the binary paint shop problem and their expected number of colour changes, Journal of Discrete Algorithms 9 (2): 203–11.
[2] B. Gärtner, J. Matoušek: Approximation algorithms and semidefinite programming. Springer 2012 [3] F. Meunier, B. Neveu: Computing solutions of the paintshop–necklace problem, Computers & Operations Research 39 (11): 2666–78, 2012. [4] R. Šámal, J. Hančl, A. Kabela, M. Opler, J. Sosnovec, P Valtr: The binary paint shop problem, Midsummer Combinatorial Workshop XXIV in Prague (July 30, 2019) |