| tags:[ research conference ]
ICALP 2018 - výpisky
Máme měnící se data, která chceme seřadit. Po každém compare-and-exchange operaci se vymění náhodná dvě sousední data. Počítáme vzdálenost ke správnému seřazení pomocí inverzí. Lower bound je Omega(N) inverzí po konci algoritmu.
Autorům se povedlo dokázat, že insertion sort je optimální – tj. po doběhnutí algoritmu máme s vysokou pravděpodobností O(N) inverzí. Experimenty ukazují, že většina O(N^2) algoritmů má dobré výsledky.
Lower bound pro počítání Lehvensteinovy vzdálenosti je v polynomu řádu N^2. Algoritmy, které jsou rychlejší, musí být aproximační, a některé poseldní algoritmy ani nevracejí operace, které je pro změnu prvního řetězce na druhý, ale pouze jejich počet.
Mějme zakořeněné stromy, kde každý list má číslo 1..n, kde vnitřní vrcholy mají stupeň 2+. Tyto stromy reprezentují historii genetiky různých druhů stromů/zvířat apod. Máme několik způsobů jak kombinovat dva takové stromy, např: majority, loose, frequency, greedy consensus tree.
Autoři dokázali udělat frequency ct v O(kn) a greedy v O(k n^1.5).
Potřebujeme mít deterministický isomorfismus podstromů. Provedeme HLD + uděláme si úplný binární strom kde listy jsou bity příslušnosti do setu. Nějak to prostě umlátili :) Počítali LCA mnoha prvků pomocí micro-macro dekompozice stromů.
B. Dudek and P. Gawrychowski: Edit Distance between Unrooted Trees in Cubic Time ↗
Mějme nezakořeněné, uspořádané stromy. Autoři dovedli v O(N^3) najít edit distance na takových stromech. (Pokud platí nějaká conjecture), tak tento problém nelze vyřešit v O(N^(3-e)) pro e>0.
Pro zakořeněné stromy to lze v O(N^2). Pokud bychom zkoušeli všechny zakořenění, tak máme O(M N^2). Autoři použili nějaké trýčky, aby se dostali z M na N.
Mají 2.36-aproximaci pro harmonický k-medián pro Proportional Approval Voting použitím LP a dependent rounding.
L. Elisa Celis, D. Straszak and N. K. Vishnoi: Ranking with Fairness Constraints ↗
Když máme napovídání personalizované, vzniká problém, že člověk co má jeden názor ho také najde, a nemá tak přehled o všech možných oblastí, které pole zájmu obsahuje. Fair ranking problem – máme m itemů a n pozic, a utilitní matici jakou má váhu když item bude na vybrané pozici, chceme přiřadit všechny problémy. Můžeme mít nějaká omezení, která musí být splněna výsledným přiřazením. Autoři udělali řešení pro d=1, aproximaci pro d>1 a ukázali těžkost problému.
J. Chen, B. Li, Y. Li and P. Lu: Brief Announcement: Bayesian Auctions with Efficient Queries ↗
Autoři se zabývali Bayesovskými aukcemi. Povedlo se jim odvodit lower bound a skoro optimální upper bound.
Máme hráče a zdorje, platí se za zapnutí zdroje a za propojení hráče ke zdroji. Když je hra separable, tak změna volby hráče neovlivní cenu ostatních, kteří nejsou u zdroje od/ke kterému se změnil.
Matroid Games, Connection Games – Autoři udělali redukci, která změní profil na vynutitelný profil pro tyto třídy her.
Jeden hráč se snaží projít sítí od s do d, tak aby byla šance přerušení nepřítelem, který zná jeho strategii, co nejnižší. Když bude mít hráč nerandomizovanou strategii, tak jeho cestu vždy nepřítel přeruší. Když použije náhodnou cestu tak, aby pravděpodobnost nejpravděpodobnější hrany byla co nejnižší, tak minimalizuje šanci, že jeho cestu nepřítel přeruší. Když budeme mít hráčů více, každý s vlastním nepřítelem, dostáváme se do (Network) Congestion Games.
Pro Congestion Games (viz předchozí talk) přišli autoři s lower a upper boundy na Price of Stability.
R. Colini-Baldeschi, M. Klimm and M. Scarsini: Demand-Independent Optimal Tolls ↗
Non-atomic congestion games – dvě skupiny řidičů, kteří mají jiný start/cíl. Každý chce minimalizovat svoji dobu řízení. Wardrop equilibrium, řešení toku (aut) zkrz síť; pokud jsou funkce hran striktně rostoucí je i prostor řešení konvexní a má řešení (LP). Pokud se řidiči chovají sobecky, tak se do tohoto equilibria asi nedostaneme … lze na hrany přidat clo tak, abychom se dostali do tohoto equilibria.
Autoři dokázali, že demand-independent optimal cla existují právě tehdy, když funkce ceny hran jsou všechny typu c(x)=a x^t + b; když existují, tak jsou unikátní; pro generický výsledek mohou vyžadovat záporné clo.
T. Kesselheim and B. Kodric: Price of Anarchy for Mechanisms with Risk-Averse Agents ↗
Výsledky na smoothness; také ukázali, že v all-pay aukci s risk-averse hráči není Price of Anarchy omezené.
Worst case tohoto problému je vyřešený. Autoři se zabývají případem, kde máme sice worst-case graf, ale příchozí vrcholy jsou náhodné. Podařilo se jim tak udělat řešení pro random-arrival, které je lepší než dolní mez worst-casu.
Plně dynamické Bin Packing – mějme itemy, které chceme dát do tašek. Na offline případ je známý FPTAS algo.
Pro online setting: itemy postupně přicházejí a odcházejí a chceme je zabalit do co nejméně tašek tak, abychom při jednom přidání/odebrání, přebalili maximálně R itemů. Zároveň chceme aby se algoritmus dostal na nějakou rozumnou c-aproximaci.
Běží nám simulace, ve které chcme mít možnost se vrátit do libovolného bodu minulosti. Můžeme si uchovávat checkpointy, které načteme a simulujeme od nich. Co ale když máme místo pouze na K takových checkpointů; potřebujeme způsob jak se rozhodnout kdy udělat checkpoint a který z minulých uložených checkpointů smazat. Autoři mají nějaké lower a upper boundy.
B. Gärtner, T. D. Hansen, P. Hubáček, K. Král, H. Mosaad and V. Slívová: ARRIVAL: Next Stop in CLS ↗
Mějme vlak na vrcholu grafu G, kde každý vrchol má dvě vycházející hrany. Každý vrchol má výhybku na jedné ze dvou hran. Vlak vyjede z vrcholu po hraně, na kterou je výhybka, a za sebou ji přehodí na druhou kolej. Zajímá nás
Switching flow – přiřazení počtu projití hranami. NP certifikát je switching flow co splňuje Korhofovy zákony a parity výjezdů z každého vrcholu. Cp-NP certifikát (někdo dokázal), že lze přidat garbage vrchol, do kterého vedou neexistující hrany; pak flow jde buď do cíle, nebo do garbage vrcholu.
Graf posledně použitých hran (smažeme hrany, které nebyly použity poslední) – theorem, buď tam není cykl, nebo je zde jen jeden cykl, který obsahuje výsledný vrchol. Arrival je v UP (NP s pouze jedním certifikátem) i co-UP. Také dokázali, že Arrival je v CLS redukcí z Ar. na End of Metered Line, který je znám být v CLS.
Fine grained complextiy se z otázky P=?NP dostáváme k tomu, že máme mnoho tříd, a nevíme jestli nám dávají větší výpočetní sílu. V poli těchto komplexit máme čtyři hlaví typy kSUM, APSP, k-OV a k-CLIQ.
Pokud je problém těžký dovedeme simulovat derandomizaci; pokud je derandomizace ‘rozbitá’, tak je problém jednoduchý. Weak k-clique conjecture a.e. => pro všechna alpha, pro všechna efektivní distribuce mu lze simulovat BPP pomocí heurBPP s n^{alpha} náhodných bitů.
Sam Staton: Probability theory from a programming perspective ↗
Programování výpočtů pro pravděpodobnostní je sice horší než model na míru, ale rychlost vytvoření programu prototypu má výhody při prototypování. Byla řeč o mírách, a rozšíření modelu tak, aby zahrnoval i funkce vyššího řádu – funkce co maj jako parametr funkce.
Máme vážený graf a chceme vybrat k-souvislý podgraf, který je co nejlevnější. Hladový, lokální algoritmus má proticase, který ukazuje, že není c-aproximací. Autoři ukázali, že pokud budeme řešit vrcholy lokálně, ale v pořadí dle uniformního rozdělení, tak dostaneme 4-aproximaci. Také mají podobný výsledek s prophet setting, kde se rozdělení může měnit, ale víme jaké bude v každém kroce.
B. Aronov, G. Bar-On and M. Katz: Resolving SINR Queries in a Dynamic Setting ↗
Mějme vysílače v rovině s nějakou silou. Každý vysílač má také nějaké rušení, kterým zhoršuje příjem z ostatních vysílačů. Signal to Interference plus Noise Ratio (SINR) popisuje jaký bude příjem vzhledem k síle signálu a rušení. SINR query – může bod v rovině přijímat signál, a od koho? Bez rušení jde o Voroného diagram, s rušením bude prostor omezený a oblasti na hranicích nemohou kvůli rušení přijímat signál.
Autoři mají řešení pro SINR query, ale v dynamickém případě. Rozdělí prostor na 2 části, blízké a vzdálené vysílače, a aproximují rušení z nich, pomocí více pásů, které aproximují polygony.
Máme graf – síť propojených komunikačních uzlů, a hledáme graf, který bude mít dobré vlastnosti. Proper obarvení hran nám dává throughput, tedy počet zpráv, které z dhlouhodobého hlediska zvládneme zpracovávat.
Při komunikaci hranou vznikne interferenční disk a počítáme velikost rušení (podobně jako u předchozí přednášky). Pokud je celková interference >1, tak je to problém a nelze takové hrany používat zároveň.
Autoři se zabývali případem, kdy nemůžeme používat všechny možné hrany roviny, ale co když některé hrany nelze použít kvůli rušení – zeď, geometrie prostoru? Modelujeme grafem, popisující linky, a konfliktním grafem, které linky nelze použít zároveň; tento model je hodně obecný. Mají log n aproximaci pro obecný případ.
Temporal graf – graf, kde hrany mají dány i časy své existence. Temporal vertex cover – časový výskyt vrcholy pokryje hrany, které jsou v daném čase incidentní pokrytému vrcholu; toto se podstatně liší od disjunktních řešení jednotlivích grafů. Sliding Window Termporal Vertex Cover – pokud vezmeme okno velikosti K, chceme aby v tomto okně bylo pokrytí Temporal Vertex Cover.
Pro max stupeň 1 je v P, pro 3 neexistuje PTAS, pro 2 nevíme.
Máme grafy s triliony vrcholy; jeden způsob jak si s nimi poradit je pomocí MapReduce a zpracovat data paralelně na mnoha strojích. Stroje mezi sebou komunikují v kolech a snažíme se minimalizovat počet kol.
Dostáváme stream celých čísel, chceme odpovídat query: jaký je součét posledních X čísel? Existující model umožňuje e-multiplikativní chybu. Autoři uvádí nový model … odpoví korektně na query X+e a ukazují algoritmus s použitím O(e^-1 log R) bitů (R range čísel). Hlavní nápad je rozřezání na bloky.
A. Conway, M. Farach-Colton and P. Shilane: Optimal Hashing in External Memory ↗
Hash table BOA je optimální pro lambda=Omega(log N/log log N + logM/B N), vzhledem k počtu čtení/zápisů. Size-Tiered LSM – v levelech má runy hodnot; nad mina pak BS po levelech. Když se na hodnoty použije fingerprint (hash) a ten se pak rozbaketuje, tak dostaneme O(1) IO operací ne zjištění fingerprintu.
A. Aamand, M. B. T. Knudsen and M. Thorup: Power of d Choices with Simple Tabulation ↗
D-choice paradigma pro hashování – při zahešování máme D možností, kam uložit hashovanou hodnotu; tohle pomáhá při hashování – max load pak je log log n / log d (oproti běžnému log n / log log n). Autoři se zabývali tím, co se děje s tímto paradigmatem pří nenáhodném hashování.
D. Kane, S. Lovett and S. Moran: Generalized comparison trees for point-location problems ↗
Linear Decision Trees (LDT) – máme rozhodovací strom (ternární =,<,>), který se rozhoduje podle hodnoty lineární funkce vstupu (x1+x3-2*x8).
S. Walzer: Load Thresholds for Cuckoo Hashing with Overlapping Blocks ↗
Cukoo hashing with windows – abychom neměli moc vyvolání cache, tak můžeme do jednoho bloku dát více hash hodnot; zároveň může být hodnota na D různých adresách. V tomto hashování nechceme mít malé cykly.
S. Bouchard, Y. Dieudonne and A. Lamani: Byzantine Gathering in Polynomial Time ↗
Máme graf na kterém jsou agenti, kteří se chtějí sejít. Cílem je navrhnout protokol, díky kterému se jim to povede; v grafu jsou ovšem i nepřátelé, kteří jim to chtějí překazit.
S. Das, D. Dereniowski and P. Uznański: Brief Announcement: Energy Constrained Depth First Search ↗
Máme robota co prohledává graf, v grafu je jeden vrchol s nabíjecí stanicí a robot má omezenou baterii. Autoři dokázali, že intuitivní algoritmus je také c-aproximací optima.