Skip to content
Snippets Groups Projects
Select Git revision
  • d7c46f4d147ca520623ac4fa6a9ac4598bfadab2
  • master default protected
2 results

index.md

Blame
  • index.md 71.12 KiB
    title: "Bakalářka: Binární paint shop problém"
    lang: "cs"
    highlight-style: "dracula"
    ft:
        title: Binární paint shop problém
        author: Jiří Kalvoda
        department: Informatický ústav Univerzity Karlovy
        department_type: Ústav
        supervisor: doc. Mgr. Robert Šámal, Ph.D.
        abstract: |
            Binární paint shop je následující optimalizační úloha:
            Na barvicí linku vjíždí řada aut.
            Od každého typu auta jsou někde v řadě právě dvě auta a
            jedno z nich bychom rádi nabarvili červeně a druhé modře.
            Měnit barvu, kterou aktuálně barvíme, je drahá operace,
            proto bychom rádi pro danou posloupnost aut provedli co nejméně změn.
            Vstupem úlohy jsou typy aut v posloupnosti a výstupem je jejich obarvení.
            Je známé, že úloha je NP-těžká a za určitých předpokladů dokonce neaproximovatelná,
            proto je na místě zkoumat řešení, co se chovají dobře na náhodném vstupu.
            V této práci je představen algoritmus založený na semidefinitním programování,
            který dle provedených měření pro náhodné vstupy dosahuje výsledků okolo 0.34-násobku počtu typů aut.
            O algoritmu jsme dokázali, že pro každý vstup vrátí ve střední hodnotě řešení nejhůře o 0.212-násobek počtu typů aut horší než optimum.
        keywords: [binární paint shop problém, aproximační algoritmus]
        year: 2024
        study_programme: Informatika
        en:
            title: Binary paint shop problem
            keywords: [binary paint shop problem, approximation algorithm]
            department: Computer Science Institute of Charles University
            department_type: Institute
            abstract: |
                The Binary Paint Shop represents an optimization problem:
                A line of cars enters a paint shop.
                There are exactly two cars of each type somewhere in the line.
                The aim is to color one of these two cars red and the other blue.
                It is expensive to switch the current color in the paint shop
                so for a given sequence of cars we would like to minimize the number of color changes.
                Input of the task are types of cars in the line and output is the coloring of theses cars.
                This task is known to be NP-hard, and under specific conditions, it defies polynomial time approximations.
                Therefore, it is a good idea to find some algorithms which behave well on a randomly generated input.
                This thesis introduces an algorithm based on semidefinite programming. Experiments on random inputs show it reaches solutions near to 0.34 times the number of car types.
                We proved that for each input this algorithm returns a solution with expected deviation from optimum of at most 0.212 times the number of car types.
    Klikaci věci + generování obsahu formátítkem
    Algoritmy velké písmena
    
    Vizualizace: více pohledů a správné pořadí hran.
    TODO SAZBA blockquote

    ::: {only=html} \def\progline#1#2#3{\hbox{#1}\hskip 1cm\relax #2 \hskip 1cm\relax #3} \protected\def\P{{\rm P}} \protected\def\NP{{\rm NP}} \protected\def\APX{{\rm APX}} \protected\def\opt{{\rm opt}} \protected\def\algo#1{{\bf #1}} \protected\def\alg{\algo{alg}} :::

    \def\progline#1#2#3{\hbox to 3cm{#1\hfil}\hbox to 5cm{\hfil$\displaystyle #2$\hfil}\hbox to 4cm{$\displaystyle #3$\hfil}}
    \protected\def\P{{\rm P}}
    \protected\def\NP{{\rm NP}}
    \protected\def\APX{{\rm APX}}
    \protected\def\vec#1{\vecoverrightarrow{#1}}
    \let\rightarrowfillreal\rightarrowfill
    \protected\def\opt{{\rm opt}}
    \protected\def\algo#1{{\bf #1}}
    \protected\def\alg{\algo{alg}}

    ::: {c=head} :::

    Obsah {-}

    ::: {c=table_of_contents} :::

    Úvod

    V této práci představíme binární paint shop problem. Jedná se o úlohu, kterou neumíme efektivně řešit (protože je \NP úplná) a ani aproximovat (za předpokladu Unique games conjecture je konstantní aproximace také \NP těžká), takže mimo jiné probíhá aktivní výzkum snažící se najít algoritmus, který je dobrý v průměrném případě (pro náhodný vstup).

    Zadání

    Zadání binárního paint shop problému (dále těž BPS) je následující:

    ::: {c=box t=task name="Binární paint shop"} V řadě je 2n​ aut n různých typů -- od každého typu dvě. Chtěli bychom od každého typu nabarvit jedno auto červeně a druhé modře. Auta však na barvicí linku vjíždí v pořadí, v jakém jsou v řadě. Barvicí linka je optimalizovaná na barvení velkého počtu aut jednou barvou. Tedy měnit barvu, kterou se barví, je složitá a drahá záležitost. Chceme tedy najít obarvení aut tak, aby od každého typu bylo jedno červené a jedno modré, přitom počet změn barev v řadě byl co nejmenší. :::

    Počet změn barev řešení považujeme za skóre algoritmu. Relativní skóre pak je poměr skóre a počtu typů aut.

    Problém můžeme chápat buď jako optimalizační problém, kde účelová funkce je počet změn v řešení a snažíme se ji minimalizovat, nebo jako rozhodovací problém, kde se ptáme, jestli existuje řešení s nejvýše nějakým zadaným počtem změn.

    Cíle práce

    Naším cílem bude najít co nejlepší algoritmus řešící BPS a odhadnout u něj střední hodnotu skóre pro náhodný vstup. Dále se pokusíme porovnat již známé algoritmy.

    Struktura práce

    Nejprve zavedeme notaci potřebnou pro pohodlnou práci s BPS a definujeme aproximační algoritmy. Kapitola 2 obsahuje shrnutí doposud známých algoritmů a jiných výsledků ohledně BPS. V kapitole 3 je představen princip semidefinitního programování, které má uplatnění v algoritmu představeném o kapitole 4. Kapitola 5 se věnuje praktické implementacím algoritmů a naměřeným datům o nich.

    Notace

    Auta budeme indexovat od 0 do 2n-1 a typy od 0 do n-1.

    Pomocí a_{i,0} budeme značit pozici prvního auta typu i a pomocí a_{i,1} pozici druhého.

    Opačně t_i bude značit typ auta na pozici i a p_i bude značit, jestli se jedná o první nebo druhé auto daného typu (tedy bude nabývat hodnoty 0 nebo 1).

    Protože někdy bude výhodnější zacházet se znaménky, zavedeme P_i = -1+2 p_i, které bude nabývat hodnot -1 a 1. Také rozšíříme notaci o a_{i, -1} = a_{i,0}.

    Nakonec ještě zavedeme zkratku indexu druhého auta stejného typu jako je auto na pozici i: o_i = a_{t_i,-P_i}.

    Barvy pro nás budou 0 a 1. Pokud budeme uvažovat nějaké konkrétní obarvení c, tak c(i) bude značit barvu auta na pozici i.

    Pro algoritmus \alg označíme skóre na vstupu \alpha pomocí \gamma_{\alg}(\alpha). Dále označme všechny vstupy délky n jako W_n. Průměrné skóre algoritmu na všech vstupech délky n tedy bude \gamma_{\alg}(n) = {\sum_{\alpha \in W_n} \gamma_{\alg} (\alpha) \over |W_n|}. Tuto hodnotu mimo jiné můžeme chápat jako střední hodnotu skóre pro uniformně náhodný vstup délky n. K tomu ještě zavedeme notaci pro relativní skóre \delta_{\alg}(\alpha) = \gamma_{\alg}(\alpha)/n_{\alpha} a analogicky průměrné relativní skóre \delta_{\alg}(n) = \gamma_{\alg}(n)/n. Nakonec označme \delta_{\alg} = \lim_{n\to\infty} \delta_{\alg}(n) = \lim_{n\to\infty} \gamma_{\alg}(n)/n. Protože limita nemusí vždy existovat, zavedeme ještě limes superior a limes inferior: \delta^+_{\alg} = \limsup_{n\to\infty} \delta_{\alg}(n) a \delta^-_{\alg} = \liminf_{n\to\infty} \delta_{\alg}(n). Význam těchto definic bude vysvětlen v následující kapitole.

    Dále označme \gamma(\alpha) optimální skóre na vstupu \alpha. A následně analogicky definujeme \gamma(n), \delta(\alpha), \delta(n), \delta, \delta^+ a \delta^- stejně jako u variant s algoritmem, jen skóre daného algoritmu nahradíme za optimální skóre.

    Definice aproximačních algoritmů

    Protože ne pro všechny problémy známe polynomiální algoritmus, který je schopný je vyřešit, zajímavý výsledek může být, i když se k řešení zvládneme jen v nějakém smyslu alespoň přiblížit. Na to nejprve musíme říct, co pro nás znamená, že nějaké řešení je několikrát horší než jiné. To nám poskytne obecná definice optimalizačního problému.

    ::: {c=box t=def name="Optimalizační problém"} Problém je optimalizační, pokud pro každý vstup I, existuje množina přípustných řešení F(I). Dále existuje účelová funkce f, která pro každý vstup a jeho přípustné řešení určuje reálné nezáporné číslo -- jeho hodnotu.

    Pokud se jedná o minimalizační problém, tak pod pojmem optimum daného vstupu (značíme \opt(I)) myslíme infimum hodnot účelové funkce přes všechna přípustná řešení, tedy \inf f[F(i)]. Pro maximalizační problém analogicky použijeme supremum. :::

    A nyní již přejdeme k samotným definicím algoritmů blížících se optimu.

    ::: {c=box t=def name="Aproximační algoritmus"} Algoritmus \alg je g(n)-aproximační na minimalizačním problému, pokud pro každý vstup I algoritmus vrátí přípustné řešení \alg(I), pro které platí, že f(\alg(I)) \le g(|I|) \cdot \opt(I). :::

    Předešlá definice záleží na tom, co považujeme za velikost vstupu, což se pro různé problémy a jejich interpretace liší. Naštěstí nás většinou budou zajímat c-aproximace, tedy aproximace, kde g(n) je konstantní funkce rovna c.

    U maximalizačních problémů je drobný problém v terminologii, protože není shoda na tom, jestli má platit f(\alg(I)) \ge g(|I|) \cdot \opt(I) nebo f(\alg(I)) \ge {1\over g(|I|)} \cdot \opt(I). Naštěstí podle kontextu jde snadno rozhodnout, která definice se používá, protože je potřeba násobit optimum číslem menším rovno jedné (jinak by pro kladné hodnoty účelové funkce nemohl existovat žádný vyhovující algoritmus).

    Bohužel někdy asi ani s aproximačními algoritmy nevystačíme a proto zavedeme pravděpodobnostní relaxaci.

    ::: {c=box t=def name="Pravděpodobnostní aproximační algoritmus"} Náhodný algoritmus \alg je pravděpodobnostně g(n)-aproximační na minimalizačním problému, pokud pro každý vstup I algoritmus vždy vrátí přípustné řešení \alg(I), pro které platí, že \E[f(\alg(I))] \le g(|I|) \cdot \opt(I). :::

    Snadným důsledkem definice (a Markovovy nerovnosti) je, že pro každé \lambda > 1 pravděpodobnostně g(n)-aproximační algoritmus vrátí s pravděpodobností zdola omezenou konstantou 1- {1\over \lambda} \in (0,1) řešení s hodnotou nejvýše \lambda \cdot g(n)\cdot \opt(I).

    Všimněme si, že na hodnotě 1-{1\over\lambda} příliš nezáleží. Opakovaným spouštěním algoritmu a pak vybráním nejlepšího z dodaných řešení zvládneme pravděpodobnost libovolně těsně přiblížit k jedné.

    Pokud řešíme složitost algoritmů a úloh, většinou vyžadujeme, aby účelová funkce i rozhodování přípustnosti řešení byly vyčíslitelné v polynomiálním čase. Navíc chceme, aby všechna přípustná řešení měla délku omezenou nějakým polynomem v délce vstupu. Snadno nahlédneme, že za takovýchto podmínek je rozhodovací verze, jestli je optimum alespoň zadané číslo, v \NP. Pro takovou úlohu většinou hledáme polynomiální aproximační algoritmus. Binární paint shop vyhovuje všem těmto podmínkám.

    Pokud existuje (1+\varepsilon)-aproximační algoritmus pro každé \varepsilon > 0, říkáme, že máme aproximační schéma.

    Doposud známé výsledky

    Bonsmaa, Epping a Hochstättler [@apx] dokázali, že optimalizační verze BPS je \APX-těžký problém, což je silnější tvrzení, než že rozhodovací verze je \NP-těžká. Za předpokladu \P \neq \NP víme, že kromě polynomiálního algoritmu na rozhodovací verzi nemůže existovat ani polynomiální aproximační schéma na optimalizační verzi.

    Snadno nahlédneme, že rozhodovací problém patří do \NP. Když nám někdo dá přiřazení barev autům, v lineárním čase jsme schopni ověřit, že počet změn je dostatečně malý a od každého typu a barvy auta je právě jeden výskyt. Tedy rozhodovací problém je \NP-úplný.

    Dále pak Gupta a spol. [@neaprox] ukázali, že za předpokladu Unique games conjecture je NP-těžké i problém libovolně konstantně aproximovat. K tomu využili převod na problém minimálního ne-řezu. To je problém podobný maximálnímu řezu, který bude představen později. Ovšem místo maximalizace počtu hran v řezu minimalizujeme počet hran mimo něj (tedy v rámci partit). Tyto dva problémy mají stejné optimum, ovšem aproximovatelnost se na nich chová drasticky jinak. V momentě, kdy jsou skoro všechny hrany v řezu, tak přidání další hrany do řezu skoro nezmění počet hran v něm. Ovšem odebrání hrany z ne-řezu bude mít velký vliv (procentuálně) na počet hran v ne-řezu.

    Vzhledem k předešlým výsledkům je na místě zkoumat různé heuristiky a obecně algoritmy, co jsou nás schopny k optimálnímu řešení alespoň částečně přiblížit.

    Jedním z takových algoritmů je hladový algoritmus popsaný Andresem and Hoch-stättlerem [@gr]:

    ::: {c=box t=algo name="Hladový algoritmus" notation=g} Autům budeme přiřazovat barvy v pořadí, v jakém jsou na vstupu. První auto v řadě obarvíme řekněme červeně. Dále budeme vždy první auto daného typu barvit stejně jako předcházející auto a druhé auto daného typu obarvíme vždy zbývající barvou. :::

    V daném článku autoři o tomto algoritmu dokázali, když vezmeme uniformně náhodný vstup délky n, tak střední hodnota počtu změn ve vygenerovaném řešení je \sum_{0\le k < n} {2k^2-1 \over 4k^2-1}.

    Hladový algoritmus budeme značit \algo g, tedy předešlou hodnotu značíme \gamma_{\algo g}(n). Připomeňme, že pomocí \delta_{\algo g}(n) značíme tuto hodnotu vydělenou velikostí vstupu, tedy \gamma_{\algo g}(n) / n.

    Pro dostatečně velká n se \gamma_{\algo g}(n) pohybuje zhruba okolo (1 / 2) n (formálně řečeno: platí, že \delta_{\algo g} = \lim_{n\to\infty} {\gamma_{\algo g}(n) / n} = {1 / 2}) (viz obrázek ).

    ::: {#e-g c=figure}

    max_n = 21
    fig = go.Figure(data=[go.Scatter(
        x=list(range(1, max_n)),
        y=[sum((2*k**2-1)/(4*k**2-1) for k in range(n))/n for n in range(1, max_n)],
        mode = 'markers',
        )])
    fig.update_layout(
        xaxis_title="Počet typů aut.",
        yaxis_title="Relativní skóre.",
        xaxis=dict(range=[0,None]),
        yaxis=dict(range=[0, 2]),
        showlegend=False,
    )

    Graf střední hodnoty rel. skóre hladového řešení \delta_{\algo g}(n) v závislosti na n. :::

    U hladového řešení je tedy střední hodnota skóre přes uniformně náhodný vstup přesně vyčíslená. Pro nás je zejména důležité, že jsme ji schopni shora odhadnout. Střední hodnotu totiž můžeme považovat za ukazatel kvality algoritmu (čím menší je, tím se jedná o lepší algoritmus) a tedy horní odhad nám dává záruku kvality algoritmu.

    Zajímavé je pro nás zkoumat chování algoritmů na velkých vstupech, tedy dává smysl uvažovat limitu střední hodnoty do nekonečna. Ovšem s narůstajícím počtem aut narůstá i počet potřebných změn, takže samotná limita střední hodnoty moc nedává smysl, protože by byla nekonečná. Místo ní budeme uvažovat \lim_{n\to\infty} {\gamma_{\alg}(n) / n} = \lim_{n\to\infty}\delta_{\alg}(n). O ní víme, že pro libovolný algoritmus (pokud existuje) bude v intervalu [0, 2], protože maximální počet změn musí být mezi 0 a 2n-1.

    I když nejsme schopní hledat optimum efektivně, pro každý vstup je určitě optimum dobře definovaná hodnota. Můžeme se tedy ptát na otázku, kolik vyjde limita, kde místo skóre algoritmu vložíme optimum pro daný vstup, tedy \lim_{n\to\infty} \delta(n) = \lim_{n\to\infty} \gamma(n)/n. Označme hodnotu této limity \delta.

    Bohužel není zřejmé, že limita skutečně existuje, proto místo limity budeme často uvažovat limes supervisor a inferior. Ty budeme značit přidáním \pm jako horního indexu. Stejnou notaci budeme používat i u limit algoritmů.

    Jelikož optimum musí být alespoň tak dobré jako výstup hladového řešení, dostáváme konstruktivní horní odhad \delta^+ \le 0.5. Hledáním lepších algoritmů můžeme horní odhad zlepšovat.

    Překvapivě však je, že Hančl a kol. [@docw] ukázali dolní odhad \delta^- \ge 0.214 pomocí počítání pravděpodobností pro náhodné obarvení. Samotný fakt, že \delta^- > 0 je již poměrně zajímavé tvrzení. To nám říká, že každý algoritmus na průměrném vstupu musí použít aspoň \Omega(n) změn barev. Nemůže tedy například existovat algoritmus, kterému by stačilo jen \O(n / \log n) změn. To také říká, že odhadovat algoritmy pomocí \lim_{n\to\infty} \gamma_{\alg}/n, je alespoň co se týče asymptotiky dostačující, protože vystihuje konstantu nejvýznačnějšího členu polynomiální aproximace.

    Dále si představíme několik algoritmů, které se snaží konstruktivně zlepšit horní odhad na \delta^+.

    ::: {c=box t=algo name="Rekurzivní hladové řešení" notation="rg"} Z řady aut odstraníme první auto v řadě a druhé auto příslušného typu. Zbytek aut rekurzivně obarvíme a pak do řady přidáme odebranou dvojici tak, aby byl počet změn co možná nejmenší možný. :::

    Autoři algoritmu, Andres and Hochstättler [@gr], o něm dokázali, že {2\over 5}\,n - {8\over 15} \le \gamma_{\algo{rg}}(n) \le {2\over 5}\,n + {7\over 10}, tedy \delta_{\algo{rg}} = 2/5 = 0.4.

    Dále se o zlepšení tohoto algoritmu pokusili Hančl a kol. [@docw]. Ti si všimli, že ve výstupu rekurzivního řešení se občas stane, že přebarvením dvojic typů aut se zlepší skóre. Ukázali, že takových dvojic je vždy ve výstupu lineárně mnoho a z toho pak ukázali horní odhad \delta^+ \le 0.4 - \varepsilon < 0.4 (pro \varepsilon zhruba 2\cdot 10^{-6}).

    Hančl a kol. [@docw] přišli ještě s dalším způsobem, jak vylepšit rekurzivní hladové řešení. Při běhu hladového řešení se občas stane, že některá dvojice aut stejného typu si může prohodit barvy bez změny skóre řešení. Když přidáváme auto do okolí takovéto dvojice, v některých případech můžeme provést toto prohození a tím snížit počet nově vytvořených změn barev. Budeme si tedy udržovat některé z takovýchto dvojic a pokud budeme přidávat auto do okolí evidované dvojice tak, že prohození barev dané dvojice by pomohlo, prohodíme její barvy.

    Budeme pracovat nad rozšířenou abecedou barev o znak "*" reprezentující neurčenou barvu. Při rekurzi budeme udržovat invariant, že pro každý typ obě auta buď budou označena * a nebo ani jedno z nich nebude označeno * a pak nutně budou mít různé barvy. Navíc bude platit, že * nikdy není na okrajích a nejsou dvě vedle sebe. Specificky tedy na * budeme přebarvovat dvojici aut v momentě, kdy získá všechny sousedy.

    Pro popis algoritmu zavedeme notaci N(i), což bude reprezentovat multimnožinu barev aut sousedících s autem na pozici 0<i<2n-1, tedy \{c(i-1), c(i+1)\}.

    ::: {c=box t=algo name="Hvězdičkové rekurzivní řešení" notation="rsg"} Budeme pracovat nad rozšířenou škálou barev \{0,1,*\}. Ze vstupu odebereme auta typu t_0 a zarekurzíme se na zbytek. Tím získáme nějaké obarvení, které může použít na původní vstup s tím, že auta typu t_0 zatím nebudou obarvená, ty dobarvíme dle následujících pravidel:

    A) Když o_0 = 1 a n>1 nastavíme c(1)=c(2). B) Když o_0=2n-1 nastavíme c(0) = 1. C) Když N(o_0) = \{t,t\} pro nějaké t\in\{0,1\}, nastavíme i c(o_0) = t. D) Když N(o_0) = \{0,1\}, nastavíme c(0) = c(1). E) Když N(o_0) = \{1-c(1), *\}, nastavíme c(0) = c(1). F) Když N(o_0) = \{c(1), *\}, nastavíme c(0) = c(1) a přenastavíme * v okolí o_0 na 1-c(1) a druhé auto daného typu na opačnou barvu.

    A druhé auto typu t_0 obarvíme zbývající barvou.

    Pokud auta typu t_{1} spolu nesousedí, * \not\in N(1) \cup N(o_1) a prohození barev aut typu t_1 by zachovalo počet změn, přenastavíme jejich barvy na *.

    Po návratu ze všech rekurzí zbylé dvojice aut * přebarvíme na dvě různé barvy. :::

    ::: {#rsg c=figure}

    import math
    hypoth = 1/13 * math.sqrt(61) - 3/13
    import bakalarka.g as g, bakalarka.data_lib as data_lib
    fig = g.intro_graph("rsg")
    fig.add_vline(x=200*hypoth,
                  annotation_text="hypotéza", annotation_position="top left",
                  fillcolor="green")

    Graf skóre 1\,000 běhů hvězdičkového rekurzivního řešení pro n=200. :::

    Autoři algoritmu o něm vyslovili domněnku, že \delta_{\algo{rsg}} = {1\over 13} \cdot \sqrt{61} - {3\over 13} \doteq 0.370. Na obrázku je zobrazen histogram skóre tohoto algoritmu spuštěného na náhodných vstupech a hodnota z předešlé hypotézy.

    Zobecněné verze a související problémy

    Zobecněním binárního paint shopu je obecný paint shop problém, zavedený Eppingem a spol. [@ps]. Z něj pochází motivace k binární verzi.

    ::: {c=box t=task name="Obecný paint shop problém"} V řadě je m​ aut n různých typů -- nyní však již od každého typu libovolný počet. Dále máme definováno pro každou kombinaci typu a barvy (kterých také může být více než dvě), kolik aut daného typu má být nabarveno na danou barvu. Chceme tedy najít obarvení aut tak, aby počet změn barev v řadě byl co nejmenší. :::

    Binární verze problému je tedy speciální případ obecného paint shop problému, kde od každého typu máme dvě auta, máme jen dvě požadované barvy a navíc platí, že pro každou kombinaci typu a barvy chceme právě jedno auto.

    Souvisejícím problémem je dělení náhrdelníku zavedený v Alonově článku [@necklace]:

    ::: {c=box t=task name="Dělení náhrdelníku"} Skupina k loupežníků uloupí náhrdelník skládající se z kn drahokamů t různých typů. Pro každý typ i platí, že náhrdelník obsahuje právě ka_i drahokamů daného typu (pro nějaké celé a_i). Loupežníci si jej chtějí férově rozdělit. Náhrdelník tedy rozdělí na několik navzájem nepřekrývajících se intervalů, jejichž sjednocení je celý náhrdelník. Každý z intervalů pak přiřadí nějakému loupežníkovi tak, aby každý loupežník získat od každého typu i právě a_i drahokamů (což znamená, že všichni budou mít od každého typu stejný počet drahokamů). Chceme minimalizovat počet intervalů, na které je nutné náhrdelník rozdělit. :::

    Nejprve si všimněme, že dělení náhrdelníku je speciálním případem obecného paint shop problému. Auta pro nás budou drahokamy. Barva auta bude označovat, který loupežník získá daný drahokam. Minimalizovat počet intervalů je to stejné jako minimalizovat počet hranic mezi nimi (kterých je o jedna méně něž intervalů). Ve vstupu problému dělení náhrdelníku navíc musí platit, pro každý typ má být stejný počet aut obarvený jednotlivými barvami (a tedy počet aut daného typu musí být násobkem k). Naopak binární paint shop problém je speciálním případem dělení náhrdelníku pro dva lupiče, kde navíc platí, že všechna a_i jsou 1 (tedy od každého typu jsou na náhrdelníku právě dva drahokamy).

    Semidefinitní programování

    V této kapitole si představíme princip semidefinitního programování (dále též SDP), jak jej popisují Gärtner a Matoušek [@semidef], a jeho použití na problém maximálního řezu, z něhož vychází algoritmus na binární paint shop.

    Nejprve zavedeme a připomeneme notaci důležitou v této kapitole. Nechť \R^{n\times m} značí množinu n-řádkových m-sloupcových matic složených z reálných čísel. Řádky i sloupce indexujeme od 0, tedy matice A\in \R^{n\times m} obsahuje prvky A_{i,j} pro všechna 0\le i < n a 0 \le j < m. Nechť \SYM_n = \{X \in \R^{n\times n} \mid x_{i,j} = x_{j,i} \hbox{\ pro všechna\ } 0 \le i,j < n\} je třída všech symetrických matic a nechť X \circ Y = \sum_{0\le i<n} \sum_{0\le j<m} x_{i,j} y_{i,j} značí součet součinu matic po složkách. Nakonec X \succeq 0 bude značit skutečnost, že matice X je pozitivně semidefinitní (bude vysvětleno později).

    Úloha semidefinitního programování je optimalizační úloha (podobně jako lineární programování) následujícího formátu: \progline{maximalizuj}{C \circ X}{} \progline{za podmínek}{A_i \circ X = b_i}{0 \le i < m-1} \progline{}{X \succeq 0.}{}

    Vstupem programu tedy je velikost matice n, počet podmínek m \in \N a pak pro každou podmínku matice A_i \in \SYM_n a číslo b_i \in \R. Výstupem je pak X\in \SYM_n splňující výše uvedené podmínky.

    Pro nás bude důležitý následující fakt z lineární algebry:

    ::: {c=box t=fact} Nechť X \in \SYM_n. Následující tvrzení jsou ekvivalentní definice pozitivně semidefinitní matice:

    • Všechna vlastní čísla matice X jsou nezáporná.
    • Pro každý vektor \vec{x} \in \R^n platí \vec{x}^{\rm T} X\vec{x}\ge 0.
    • Existuje matice Y \in \R^{n\times n} taková, že X = Y^{\rm T} Y. :::

    Pro nás bude důležitá zejména třetí podmínka, protože navíc platí, že ze semidefinitní matice X zvládneme zkonstruovat Y v čase \O(n^3) pomocí tzv. Choleského dekompozice.

    Navíc pro libovolnou reálnou matici Y je Y^{\rm T} Y symetrická. Tedy semidefinitní programování můžeme chápat jako optimalizační úlohu na Y\in \R^{n\times n}. Pojďme se zamyslet nad tím, co v takovémto pohledu znamenají podmínky a účelová funkce. Matici Y můžeme považovat za n sloupcových vektorů \vec{y_0}, \dots, \vec{y_{n-1}} vedle sebe. Matice Y^{\rm T} pak odpovídá těmto vektorům zapsaných v řádcích pod sebou. Matice X = Y^{\rm T} Y tedy na pozici i,j obsahuje skalární součin vektorů \vec{y_i} a \vec{y_j}. Účelová funkce tedy je lineární kombinací skalárních součinů a podmínky odpovídají vynucení rovnosti lineární kombinace skalárních součinů vektorů a konstanty. Speciálně tedy můžeme mít podmínku na délku vektoru: |\vec{y_i}|^2 = \vec{y_i}^{\rm T}\vec{y_i} = C. Semidefinitní programování v tomto tvaru budeme nazývat semidefinitní programování v dekomponovaném tvaru.

    Maximální řez

    Představíme si pravděpodobnostní aproximační algoritmus založený na semidefinitním programování na následující problém:

    ::: {c=box t=task} Nechť G=(V, E) je graf s hranami ohodnocenými nezápornými čísly dle h: E \rightarrow \R^+_0. Řezem grafu rozumíme rozdělení vrcholů na dvě disjunktní množiny A \cup B = V. Hodnotou daného řezu je pak součet cen hran vedoucích mezi A a B. Tedy: H(A,B) = \sum_{\{u,v\}\in E\atop u\in A, v\in B} h({u,v}) Cílem je maximalizovat hodnotu řezu. :::

    Problém maximálního řezu (resp. rozhodovací verze, kde se ptáme na existenci řezu alespoň dané velikosti) je NP-úplný [@maxcut-np], proto se u něj zkoumají aproximační algoritmy a pravděpodobnostní aproximační algoritmy.

    Nejprve si ukážeme triviální pravděpodobnostní 0.5-aproximační algoritmus:

    ::: {c=box t=algo} Každý vrchol uniformně náhodně přiřaď do množiny A nebo B. :::

    ::: {c=box t=theorem} Triviální algoritmus je pravděpodobnostní 0.5-aproximační algoritmus. :::

    ::: {c=proof} Každá hrana bude v řezu s pravděpodobností 1/2 -- při umisťování druhého vrcholu dané hrany máme pravděpodobnost 1/2, že ho umístíme do stejné množiny a tedy hrana nebude součásti řezu a pravděpodobnost 1/2 že do opačné a tedy bude součástí řezu. Součet hran v řezu je součtem indikátorů jevů přítomnosti jednotlivých hran v řezu vynásobený jejich hodnotou. Z linearity střední hodnoty tedy střední hodnota součtu vah hran v řezu je 1/2 celkového součtu vah hran, což je alespoň 1/2 optima. :::

    Povšimněme si, že triviální algoritmus dosáhl poměrně zajímavého aproximačního poměru a to se ani nedíval na vstup.

    Předešlý algoritmus lze derandomizovat, jak popisuje Dimitrakakis [@maxcut-derandom]. Výsledný algoritmus pak vždy najde řešení obsahující alespoň 1/2 hran, tedy alespoň 1/2 optima.

    Lepšího aproximačního poměru dosáhneme Goemansovým-Williamsonovým algoritmem, založeným na semidefinitním programování a proto popsaným mimo jiné v již dříve zmíněném úvodu do semidefinitního programování [@semidef].

    Naivní implementace je, že si pro každý vrchol u vyrobíme proměnnou x_u, která může nabývat hodnot \pm 1, která bude říkat, do jaké množiny máme vrchol umístit. Do účelové funkce pak zakódujeme graf. Účelová funkce bude \sum_{uv \in E} h(u,v)\cdot\left(- \frac{x_u x_v}{2} + \frac{1}{2}\right) = \frac{F}{2} + \frac{1}{2} \sum_{uv \in E} -h(u,v)x_u x_v , kde F=\sum_{uv\in E} h(u,v) značí součet hodnot všech hran. Pro každou hranu tedy přičte h(u,v), pokud x_u a x_v mají různá znaménka, a 0, pokud stejná.

    Takovýto optimalizační problém bohužel ani pomocí semidefinitního programování neumíme řešit. Na to, abychom uměli vyjádřit nějaký součin, musíme použít semidefinitního programování v dekomponovaném tvaru. Pak ale místo toho, abychom měli pro každý vektor jen jednu proměnnou, budeme mít pro každý vrchol celý vektor proměnných a místo součinu proměnných budeme mít skalární součin těchto vektorů. Již ale současně neumíme zařídit, aby tyto vektory byly buď (1,0,\dots,0) nebo (-1,0,\dots,0). Můžeme ale přidat podmínku na to, aby délka každého vektoru byla 1. Tím jsme vyrobili relaxaci výše uvedeného programu, protože za těchto podmínek může vektor nabývat i jiných poloh než (\pm 1,0,\dots,0). Celý algoritmus pak vypadá následovně:

    ::: {c=box t=algo name="Goemansův-Williamsonův"} Vyřešíme následující semidefinitní program v dekomponovaném tvaru: \progline{maximalizuj}{\sum_{uv \in E} -h(u,v)\vec{y_u}^{\rm T} \vec{y_v}}{} \progline{za podmínek}{|y_i| = 1}{0 \le i < |V|} Dále uniformně náhodně zvolíme jednotkový vektor vektor z\in \R^n a do jedné množiny vybereme právě ty vrcholy v, pro které y_v^{\rm T} z \ge 0. :::

    Semidefinitní program v algoritmu si lze představit jako umísťování n bodů na n-1 dimenzionální sféru v \R^n. Účelová funkce se snaží umístit body vrcholů spojených hranou co nejdále od sebe.

    V případě, kdy jsme povolovali pouze hodnoty \pm 1, bylo jasné, které vrcholy patří do které množiny. Nyní však výstupem optimalizace jsou vektory a tedy přiřazení množinám není tak jednoznačné. Rádi bychom umístili od sebe vzdálené body do různých množin. Na to můžeme rovnoměrně náhodně zvolit nadrovinu procházející počátkem a rozdělit body do množin podle toho, do které z polorovin určených danou nadrovinou patří.1

    To nám zaručí, že dvojice bodů daleko od sebe budou mít velkou pravděpodobnost toho, že budou v různých poloprostorech. Semidefinitní programování se tedy snaží dostat dvojice bodů odpovídající vrcholům spojených hranou daleko od sebe a podle toho se zvyšuje pravděpodobnost toho, že vrcholy budou v jiných množinách a tedy hrana bude v řezu.