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) |