Binární paint shop problém
| Thesis title in Czech: | Binární paint shop problém |
|---|---|
| Thesis title in English: | Binary paint shop problem |
| Key words: | binární paintshop problém|aproximační algoritmus |
| English key words: | binary paintshop problem|approximation algorithm |
| Academic year of topic announcement: | 2023/2024 |
| Thesis type: | Bachelor's thesis |
| Thesis language: | čeština |
| Department: | Computer Science Institute of Charles University (32-IUUK) |
| Supervisor: | doc. Mgr. Robert Šámal, Ph.D. |
| Author: | Jiří Kalvoda - assigned and confirmed by the Study Dept. |
| Date of registration: | 23.10.2023 |
| Date of assignment: | 24.10.2023 |
| Confirmed by Study dept. on: | 24.10.2023 |
| Date of electronic submission: | 09.05.2024 |
| Opponents: | Mgr. Michal Opler, Ph.D. |
| Guidelines |
| 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í. |
| References |
| [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) |