FIT 2019

Probabilistyczna weryfikacja modelowa jest metodą formalnej weryfikacji poprawności systemów stochastycznych, których własności wyrażane są w probabilistycznej logice temporalnej. Pokrewnym problemem jest synteza strategii, która automatycznie generuje strategię zapewniającą, że dana formuła logiki temporalnej jest spełniona w modelu. Dzięki wsparciu zaawansowanych narzędzi, takich jak na przykład PRISM (www.prismmodelchecker.org), metody te zostały z powodzeniem zastosowane w wielu dziedzinach, w tym w pojazdach autonomicznych, bezpieczeństwie komputerowym i protokołach komunikacyjnych. Wykład ten jest przeglądem najnowszych osiągnięć w zakresie probabilistycznej weryfikacji modelowej współbieżnych gier stochastycznych z uwzględnieniem prawdopodobieństwa, niedeterminizmu oraz wielu graczy konkurujących lub współpracujących, aby osiągnąć swoje cele. W przeciwieństwie do gier turowych, gracze we współbieżnych grach stochastycznych podejmują decyzje jednocześnie. Następnie zostaną przedstawione techniki algorytmiczne, nazywane PRISM-games, opracowane jako rozszerzenie narzędzia PRISM, które przyjmują jako specyfikację formuły podane w probabilistycznej logice temporalnej czasu alternującego i wspierają rozumowanie na temat optymalnych równowag społecznych Nasha dla koalicji graczy. Zastosowanie tych metod zostanie zilustrowane przykładami, takimi jak nawigacja robotów, protokoły komunikacyjne i sterowanie zużyciem energii. Wykład zakończy się podsumowaniem wyzwań istniejących w omawianej dziedzinie.

Bibliografia

• (kontekst gier turowych) http://qav.comlab.ox.ac.uk/bibitem.php?key=CFK+13b
• (weryfikacja współbieżnych gier stochastycznych) http://qav.comlab.ox.ac.uk/bibitem.php?key=KNP+18
• (optymalna równowaga społeczna Nasha, zaakceptowana na FM 2019) https://arxiv.org/abs/1811.07145

Mój wykład będzie wstępem do projektowania mechanizmów prawdomównych dla problemów aukcji kombinatorycznych, gwarantujących aproksymacje rozwiązań społecznie optymalnych. Rozważę dwie wersje takich aukcji: pierwszą, która zakłada stałą liczbę sprzedawanych przedmiotów, oraz drugą, która nie ma tego założenia i nie ma dodatkowych założeń o wartościowaniach kupujących.

Dla pierwszej wersji pokazujemy istnienie deterministycznych prawdomównych mechanizmów aproksymacyjnych, w których sprzedający wystawia stałą liczbę różnych przedmiotów, każdy dostępny w ograniczonej liczbie kopii. Kupujący wyrażają swoje preferencje dla multizbiorów przedmiotów, tj. mogą zażądać jednej lub większej liczby kopii każdego przedmiotu. Celem mechanizmu aukcyjnego jest wyznaczenie alokacji multizbiorów, która jest aproksymacją alokacji społecznie optymalnej. Pomimo istnienia bogatej literatury o prawdomównych mechanizmach dla problemów aukcji kombinatorycznych (zakładających wiele różnych przedmiotów) oraz dla problemów aukcji "multi-unitarnych" (zakładających wielu kopii jednego typu przedmiotu), niewiele wiadomo na temat mechanizmów, które łączą te dwie wersje aukcji. Nasze wyniki dla tego typu aukcji uzyskane są przy założeniu submodularnych i "multi-minded" wartościowań uczestników aukcji.

Dla drugiej, ogólnej wersji pokazujemy istnienie prawdomównych mechanizmów aproksymacyjnych dla aukcji kombinatorycznych w modelu online, w którym kupujący pojawiają się sekwencyjnie. Rozważamy dwa warianty takich sekwencji: wariant losowy oraz wariant adwersarialny. Wartościowania uczestników aukcji zadane są przez wyrocznię popytu. Dotychczasowe wyniki dla tego typu aukcji zakładały, że każdy przedmiot dostępny jest w $b>1$ kopiach, gdzie najczęstsze założenie to $b=\Omega(\log m)$, gdzie $m$ oznacza liczbę typów towarów. Zaproponowane przez nas mechanizmy online dają gwarancje aproksymacyjne bez tego typu założeń. Wprowadzamy nową technikę nieświadomego zaokrąglania randomizowanego, która umożliwia nam dowodzenie gwarancji aproksymacji w modelu online, które są silniejsze niż najlepsze znane aproksymacje, nawet w modelu offline. Nasze mechanizmy randomizowane są uniwersalnie prawdomówne i znacząco lepsze od dotychczas znanych mechanizmów tego typu.

Wykład prezentuje wyniki otrzymane wspólnie z Orestisem Telelisem, Carmine Ventre oraz Bertholdem Voeckingiem.

Gra jest interesującą metaforą dla opisania struktury obliczenia. Centralnym problemem jest znalezienie metody na rozwiązanie gier ustalonego typu, to znaczy określenie, kto ma strategię wygrywającą w danej grze. W skrócie nazywamy to problemem rozwiązania gry. W tym wystąpieniu skoncentrujemy się na pewnym typie gier, zwanym grami z warunkami parzystości, i na jego związku z problem obliczania punktów stałych. W 2017 roku Calude, Jain, Khoussainov, Li i Stephan znaleźli pierwszy quasi-wielomianowy algorytm na rozwiązywanie gier z warunkami parzystości. Algorytm ten można przedstawić jako metodę na obliczenie wartości termów z punktami stałymi. Gry parzystości, jak też problem obliczania wartości termów z punktami stałymi, mają bezpośrednie związki z otwartymi problemami w weryfikacji systemów informatycznych, programowaniu liniowym i planowaniu stochastycznym. Wyniki z ostatnich lat pozwalają mieć nadzieję na postęp w rozwiązaniu problemów otwartych od kilku dziesięcioleci.

Obserwacje astronomiczne, duże eksperymenty fizyczne czy wreszcie ruch sieciowy w Internecie to przykładowe scenariusze, w których generowane są duże ilości danych. Rosnące rozmiary zbiorów danych powodują, że klasyczny sposób myślenia o efektywnych algorytmach jako tych, które działają w czasie wielomianowym na pojedynczym komputerze, często nie przystaje do rzeczywistości. W tej prezentacji opowiem o modelach obliczeniowych stworzonych, by sprostać wyzwaniom zrodzonym przez ilości danych, które ciężko umieścić na jednej maszynie albo nawet przesłać do tej samej lokalizacji geograficznej. W szczególności przedstawię algorytmy dla kilku podstawowych problemów statystycznych i grafowych w tych modelach. Jest to bardzo aktywne pole obecnych badań i wiele ciekawych problemów pozostaje otwartych.

Definiujemy naturalną klasę problemów zapytań na przedziałach i dowodzimy, że wszystkie problemy w tej klasie mają taką samą złożoność czasową (z dokładnością do czynników polilogarytmicznych). Dzięki temu możemy uzyskać nowe szybsze algorytmy (również online) dla wszystkich problemów w naszej klasie.

Następnie skupiamy się na specjalnym przypadku tych problemów, w którym zapytania są dane offline a ich liczba jest liniowa. Problemy te stają się wtedy równoważne czasowo problemowi zliczania, dla każdej krawędzi $e$ w grafie o $m$ krawędziach, liczby trójkątów zawierających $e$. Ten naturalny problem daje się rozwiązać najszybszym znanym algorytmem zliczania trójkątów [1], działającym w czasie $O(m^{2\omega/(\omega+1)})\leq O(m^{1.41})$. Co więcej, jeśli $\omega=2$, ograniczenie $O(m^{2\omega/(\omega+1)})$ jest ścisłe (z dokładnością do czynników $m^{o(1)}$) przy założeniu Hipotezy 3SUM. W takim wypadku, nasza równoważność rozwiązuje kwestię złożoności problemów zapytań na przedziałach. Nasze problemy stanowią pierwszą klasę równoważności z tym osobliwym ograniczeniem złożoności czasowej.

Prezentowane wyniki powstały we współpracy z Lechem Durajem, Krzysztofem Kleinerem oraz Virginią Vassilevską Williams.

Literatura

1. Noga Alon, Raphael Yuster, Uri Zwick, Finding and counting given length cycles, Algorithmica 17(3), 209–223, 1997.

Grafy łukowe to grafy przecięć łuków okręgu. W niniejszym referacie przedstawię wielomianowy algorytm testujący izomorfizm grafów łukowych. Algorytm ten opiera się na tzw. drzewach dekompozycyjnych – strukturach reprezentujących wszystkie znormalizowane modele przecięć grafów łukowych. Drzewa te pełnią więc podobną rolę jak PQ-drzewa dla grafów przedziałowych.

Nasza praca odpowiednio rozszerza i modyfikuje podejście do problemu testowania izomorfizmów grafów łukowych zaproponowane przez Hsu [1]. Aby opisać znormalizowane modele grafu łukowego $G$, Hsu wykorzystuje odpowiedniość pomiędzy takimi modelami a stosownie określonymi modelami przecięć cięciw okręgu pewnego grafu stowarzyszonego z $G$. Podejście Hsu okazało się jednak błędne – w szczególności w pracy [2] podano kontrprzykład pokazujący, że drzewa dekompozycyjne Hsu nie mogą być wykorzystane w algorytmach testujących izomorfizm grafów łukowych.

Literatura

1. W.L. Hsu, $O(MN)$ algorithms for the recognition and the isomorphism problems on circular-arc graphs, SIAM J. Comput. 24(3), 411–439, 1995.
2. A. Curtis, M.C. Lin, R. McConnell, Y. Nussbaum, F. Soulignac, J. Spinrad, J. Szwarcfiter, Isomorphism of graph classes related to the circular-ones property, Discrete Math. Theor. Comput. Sci. 15(1), 157–182, 2013.

In the online packet scheduling problem with deadlines (Packet Scheduling, for short), the goal is to schedule transmissions of packets that arrive over time in a network switch and need to be sent across a link. Each packet has a deadline, representing its urgency, and a non-negative weight, that represents its priority. Only one packet can be transmitted in any time slot, so, if the system is overloaded, some packets will inevitably miss their deadlines and be dropped. In this scenario, the natural objective is to compute a transmission schedule that maximizes the total weight of packets which are successfully transmitted. The problem is inherently online, with the scheduling decisions made without the knowledge of future packet arrivals. The central problem concerning Packet Scheduling, that has been a subject of intensive study since 2001, is to determine the optimal competitive ratio of online algorithms, namely the worst-case ratio between the optimum total weight of a schedule (computed by an offline algorithm) and the weight of a schedule computed by a (deterministic) online algorithm. We solve this open problem by presenting a $\phi$-competitive online algorithm for Packet Scheduling (where $\phi\approx 1.618$ is the golden ratio), matching the previously established lower bound.

Joint work with Pavel Veselý, Marek Chrobak, and Jiří Sgall.

Zarówno Bitcoin, jak i inne systemy typu blockchain u swoich podstaw mają protokół konsensusu, czyli algorytm uzgadniania pomiędzy uczestnikami, w jakiej kolejności należy rozpatrywać transakcje przybywające do systemu. W tym kontekście bardzo zaskakującym rezultatem jest Twierdzenie FLP, które orzeka, przy pewnych założeniach o sieci, że żaden deterministyczny protokół nie jest w stanie rozwiązać problemu konsensusu w sytuacji, gdy choć jeden z uczestników protokołu jest nieuczciwy. W trakcie referatu zaprezentuję nowy protokół konsensusu Aleph i pokażę, jak można „oszukać” Twierdzenie FLP wykonując wspólny rozproszony rzut monetą. Powiem też nieco o tym, w jaki sposób zrealizować konsystentny rzut w przypadku, gdy nawet spora część uczestników jest nieuczciwa.

Praca wspólna z Adamem Gągolem, Damianem Straszakiem i Michałem Świętkiem.

Algorytmy tekstowe często stoją przed koniecznością wyboru pewnego podzbioru pozycji w tekście. Taka potrzeba złamania symetrii naturalnie objawia się w algorytmach równoległych, ale może także wynikać z konstrukcji podziału tekstu na bloki (np. w celu budowy hierarchicznego parsowania tekstu) lub z ograniczeń na dostępną pamięć (utrzymywanie pewnych danych dla wszystkich pozycji tekstu może być zbyt kosztowne). Podzbiór pozycji cechuje lokalna zgodność, jeśli decyzja o losie pozycji jest podejmowana nie w oparciu o jej numer, a jedynie na podstawie zawartości pobliskich pozycji.

Parsowania lokalnie zgodne znane są już od połowy lat 90., gdy stworzono je na potrzeby algorytmów równoległych i do utrzymywania dynamicznych tekstów. Jednakże dopiero ostatnie kilka lat przyniosło rozkwit technik opartych o lokalną zgodność, które znalazły wiele nowych, często zaskakujących zastosowań. Jedną z tych technik jest rekompresja autorstwa Artura Jeża, wykorzystana między innymi do równań na słowach oraz przetwarzania skompresowanych tekstów. Z kolei technika zbiorów synchronizujących, stworzona (w mojej pracy doktorskiej i prowadzących do niej publikacjach) na potrzeby struktur danych utrzymujących statyczne teksty, pozwoliła między innymi na wykorzystanie równoległości bitowej modelu RAM do przetwarzania tekstów nad małym alfabetem. Uzyskaliśmy dzięki temu pierwsze optymalne rozwiązanie problemu zapytań o najdłuższy wspólny prefiks, a także pierwszy algorytm obliczający transformatę Burrowsa-Wheelera w czasie asymptotycznie mniejszym niż długość tekstu (wyniki te opublikowaliśmy z Dominikiem Kempą na konferencji STOC 2019).

W czasie referatu opiszę podstawy kilku technik opartych na lokalnej zgodności, pokażę na prostych przykładach ich użyteczność i naszkicuję bardziej zaawansowane zastosowania.

W czasie wystąpienia pokażę, że gramatyka bezkontekstowa wielkości $m$, która generuje pojedyncze słowo $w$, może być przekształcona w liniowym czasie w gramatykę bezkontekstową wielkości $\mathcal{O}(m)$, której drzewo wyprowadzenia ma głębokość $\mathcal{O}(\log |w|)$. Rozwiązuje to otwarty problem w dziedzinie kompresji gramatykowej. Uzyskany wynik uogólnia się do kompresji gramatykowej drzew, jak również do ogólnych obwodów algebraicznych, przy założeniu, że algebra spełnia pewne techniczne warunki; w szczególności wynik ten stosuje się do standardowych obwodów arytmetycznych nad (nieprzemiennymi) półpierścieniami.

Calude, Jain, Khoussainov, Li i Stephan [1] podali w 2017 roku kwaziwielomianowy algorytm znajdujący zwycięzcę w grach parzystości. Po tym przełomowym wyniku zostało wymyślonych parę innych algorytmów kwaziwielomianowych rozwiązujących ten sam problem. Są one wszystkie względnie trudne do zrozumienia. Ponadto, okazuje się, że w praktyce działają one bardzo wolno. Od dawna natomiast istnieje rekurencyjny algorytm Zielonki, o odmiennych własnościach: jest bardzo prosty, w najgorszym przypadku działa w czasie wykładniczym, lecz w praktyce zazwyczaj jest bardzo szybki. W pracy, którą chciałbym zaprezentować, połączyłem oba podejścia: podałem niewielką modyfikację algorytmu Zielonki, która zapewnia, że jego czas działania jest co najwyżej kwaziwielomianowy. Otrzymujemy w ten sposób algorytm, który jest prosty i rozwiązuje gry parzystości w czasie kwaziwielomianowym. Praca została przyjęta na konferencję MFCS [2].

Literatura

1. C.S. Calude, S. Jain, B. Khoussainov, W. Li, F. Stephan, Deciding parity games in quasipolynomial time, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, 252–263, 2017.
2. P. Parys, Parity Games: Zielonka's algorithm in quasi-polynomial time, 2017 (wysłane na MFCS 2019).

We provide a simple new randomized contraction approach to the global minimum cut problem for simple undirected graphs. The contractions exploit 2-out edge sampling from each vertex rather than the standard uniform edge sampling. We demonstrate the power of our new approach by obtaining better algorithms for sequential, distributed, and parallel models of computation. Our end results include the following randomized algorithms for computing edge connectivity, with high probability:

• Two sequential algorithms with complexities $O(m\log n)$ and $O(m+n\log^3 n)$. These improve on a long line of developments including a celebrated $O(m\log^3 n)$ algorithm of Karger [STOC'96] and the state of the art $O(m \log^2 n (\log\log n)^2)$ algorithm of Henzinger et al. [SODA'17]. Moreover, our $O(m+n\log^3 n)$ algorithm is optimal when $m=\Omega(n\log^3 n)$.
• An $\tilde{O}(n^{0.8} D^{0.2} + n^{0.9})$ round distributed algorithm, where $D$ denotes the graph diameter. This improves substantially on a recent breakthrough of Daga et al. [STOC'19], which achieved a round complexity of $\tilde{O}(n^{1-1/353}D^{1/353} + n^{1-1/706})$, hence providing the first sublinear distributed algorithm for exactly computing the edge connectivity.
• The first $O(1)$ round algorithm for the massively parallel computation setting with linear memory per machine.

Joint work with Mohsen Ghaffari and Mikkel Thorup.

We show that the open problem of the existence of a p-optimal proof system for SAT can be characterized in terms of total nondeterministic Turing machines. We prove that there exists a p-optimal proof system for SAT if and only if there exists a proof system $h$ for SAT such that for any total nondeterministic Turing machine working in polynomial time its totality is provable with short proofs in $h$ and these proofs can be efficiently constructed.

Additionally we show that the problem of the existence of an optimal proof system for TAUT can be characterized in terms of pairs of nondeterministic Turing machines which are disjoint (do not accept the same strings). We prove that there exists an optimal proof system for TAUT if and only if there exists a proof system $f$ for TAUT such that for any pair of disjoint nondeterministic Turing machines working in polynomial time their disjointness is provable in $f$ with short proofs.

The talk is based on [1].

Literatura

1. Z. Sadowski, Total nondeterministic Turing machines and a $p$-optimal proof system for SAT}, in: J. Kari, F. Manea, I. Petre (eds.), 13th Conference on Computability in Europe, CiE 2017 Proceedings, LNCS, vol. 10307, pp. 364–374, Springer, Heidelberg, 2017.
2. O. Beyersdorff, Z. Sadowski, Do there exist complete sets for promise classes?, Math. Logic Q. 57(6), 535–550, 2011.

We study the amount of consistency (measured by relational width) needed to solve $\operatorname{CSP}(\Gamma)$ for first-order expansions $\Gamma := (D; E,N,{=},R_1,\ldots,R_k)$ of countably infinite homogeneous graphs $\mathbb{G} := (D; E)$, where $N$ is the binary relation between different vertices not connected by an edge and $R_1,\ldots,R_k$ are relations first-order definable in $\mathbb{G}$. We study our problem for $\Gamma$s that additionally have bounded strict width, i.e., for which establishing local consistency of an instance of $\operatorname{CSP}(\Gamma)$ not only decides if there is a solution but also ensures that every solution may be obtained from a locally consistent instance by greedily assigning values to variables, without backtracking. It is known that with every countably infinite homogeneous graph $\mathbb{G}$ the finite unique minimal set of finite graphs $\mathcal{F}_{\mathbb{G}}$ is associated such that a finite $G$ is an induced substructure of $\mathbb{G}$ if and only if there is no $G'\in\mathcal{F}_{\mathbb{G}}$ such that $G'$ embeds into $G$.

Our main result is that the structures $\Gamma$ under consideration have relational width exactly $(2,\mathbb{L}_{\mathbb{G}})$ where $\mathbb{L}_{\mathbb{G}}$ is the maximal size of a forbidden subgraph in $\mathcal{F}_{\mathbb{G}}$, but not smaller than $3$. It implies, in particular, that $\operatorname{CSP}(\Gamma)$ may be solved in time $O(n^m)$ where $n$ is the number of variables and $m$ is the maximum of $\mathbb{L}_{\mathbb{G}}$ and the arities of relations in the signature, while strict width $\ell$ ensures time $O(n^{\ell+1})$. Furthermore, since $\mathbb{L}_{\mathbb{G}}$ may be arbitrarily large, our result contrasts the collapse of the relational bounded width hierarchy for finite structures $\Gamma$, whose relational width, if finite, is always at most $(2,3)$.

Finally, we show that certain maximally tractable $\Gamma$s with a first-order definition in a countably infinite homogeneous graph whose $\operatorname{CSP}(\Gamma)$ are already known to be solvable in polynomial time by other algorithms may be also solved by establishing consistency. Thus, we provide an alternative algorithm for already studied problems.

We consider hypercubes with pairwise disjoint faulty edges. An $n$-dimensional hypercube (cube), denoted by $Q_n$, is an undirected graph with $2^n$ nodes, each labeled with a distinct binary strings. We shall say that the parity of the vertex $x$ is 0 if the number of ones in its labels is even, and is 1 if the number of ones is odd. Two vertices $a=a_{n-1}\ldots a_0$ and $b=b_{n-1}\ldots b_0$ are connected by the edge iff $a$ and $b$ differ in one position. If $a$ and $b$ differ in position $i$, then we say that the edge $(a,b)$ is a crossing edge going in direction $i$. We define the parity of the edge as the parity of the end with 0 (on the position where they are different). It was already known, see [1], that $Q_n$ is not Hamiltonian if it has a SCDHW (subcube disconnected halfway), i.e. if there is a dimension where all crossing edges of parity 0 (or 1) are faulty.

We show:

Theorem 1. Every cube $Q_n$ with $n\geq 4$ and disjoint faulty edges is Hamiltonian if and only if it has no SCDHW (subcube disconnected halfway). In other words the cube is Hamiltonian if and only of for each direction there are two healthy crossing edges of different parity.

Corollary 2. If $n\geq 4$, faulty edges $F$ are pairwise disjoint, and there are two nonparallel faulty edges, then $Q_n$ is Hamiltonian.

Corollary 3. If $n\geq 4$, faulty edges $F$ are pairwise disjoint, and $|F|<2^{n-2}$, then $Q_n$ is Hamiltonian.

Joint work with Janusz Dybizbański.

References

1. A. Szepietowski, Hamiltonian cycles in hypercubes with $2n-4$ faulty edges, Information Sciences 215, 75–82, 2012.

Gęstość $D(G)$ grafu $G$ to maksymalny stosunek liczby krawędzi do liczby wierzchołków pewnego podgrafu grafu $G$. Dla klasy grafów $\mathcal{F}$ wartość $D(\mathcal{F})$ oznacza supremum gęstości grafów z $\mathcal{F}$. Graf $k$-kolorowy to skończony, prosty graf, którego krawędziom przyporządkowano liczby od $1$ do $k$, nazywane kolorami. Funkcję ze zbioru wierzchołków jednego $k$-kolorowego grafu w drugi nazywamy homomorfizmem, jeżeli każda krawędź pierwszego grafu jest odwzorowana w krawędź drugiego grafu z zachowaniem kolorów krawędzi. Dla klasy grafów $\mathcal{F}$, $k$-kolorowy graf $\mathbb{H}$ (niekoniecznie z $\mathcal{F}$) nazywamy $k$-uniwersalnym dla $\mathcal{F}$, jeżeli każdy $k$-kolorowy graf utworzony z grafu z $\mathcal{F}$ można odwzorować homomorficznie w $\mathbb{H}$.

Wiadomo [1], że dla każdego $k\geq 2$, klasa grafów $\mathcal{F}$ posiada graf $k$-uniwersalny wtedy i tylko wtedy, gdy acykliczna liczba chromatyczna grafów z $\mathcal{F}$ jest ograniczona przez stałą. Rozmiar najmniejszego grafu $k$-uniwersalnego dla takiej klasy jako funkcja zmiennej $k$ mieści się, asymptotycznie, pomiędzy $\Omega(k^{D(\mathcal{F})})$ a $O(k^{\lceil D(\mathcal{F})\rceil})$ [1]. W naszej pracy domykamy górne ograniczenie do $O(k^{D(\mathcal{F})})$ dla klas grafów, dla których $D(\mathcal{F})$ jest liczbą wymierną.

Literatura

1. G. Guśpiel, G. Gutowski, Universal targets for homomorphisms of edge-colored graphs, J. Combin. Theory Ser. B 127, 53–64, 2017.

Podajemy algorytm o stałym współczynniku aproksymacji dla asymetrycznej wersji problemu komiwojażera (ATSP). Analiza tego współczynnika opiera się o standardową relaksację liniową, więc wynik ten potwierdza również hipotezę o jej stałej luce całkowitości (integrality gap).

Nasze techniki rozszerzają te użyte w algorytmie Svenssona dla szczególnego przypadku grafów nieważonych. Mówiąc dokładniej, podajemy ogólną redukcję, dzięki której wystarczy umieć rozwiązywać ATSP na grafach o strukturze podobnej (choć ogólniejszej) do instancji nieważonych. Następnie pokazujemy, jak na takich grafach rozwiązywać problem Local-Connectivity ATSP, o którym wiadomo, że jest równoważny ATSP (w sensie istnienia aproksymacji o stałym współczynniku).

Wspólny wynik z Olą Svenssonem i László A. Végh.

W problemie klastrowania zwanym Ordered $k$-Median jakość rozwiązania jest mierzona poprzez posortowanie kosztów połączeń klientów (clients) do otworzonych centrów obsługi (facilities) oraz przeskalowanie otrzymanego wektora kosztów przez dany na wejściu wektor wag (większe koszty obsługi skalowane są przez większe wagi). Od lat 90. XX-go wieku ten problem był intensywnie badany w optymalizacji dyskretnej oraz w badaniach operacyjnych, gdyż uogólnia wiele fundamentalnych problemów klastrowania i problemów lokalizacji takich jak $k$-Median oraz $k$-Center. Otrzymanie nietrywialnych algorytmów aproksymacyjnych było otwartym problemem nawet dla tak prostych grafów jak drzewa. Ostatnio Aouad i Segev (2019) skonstruowali algorytm $\mathcal{O}(\log n)$-aproksymacyjny dla Ordered $k$-Median, używając odpowiednieo zaprojektowanego przeszukiwania lokalnego. Istnienie wielomianowego algorytmu o stałej aproksymacji pozostawało otwartym pytaniem nawet dla wektora wag z dwoma różnymi wartościami.

Naszym głównym wynikiem jest skonstruowanie algorytmu o stałej aproksymacji dla ogólnego problemu Ordered $k$-Median bazującego na zaokrąglaniu odpowiedniego programu liniowego. W celu analizy procesu zaokrąglania dla nieliniowej funkcji celu zastosowaliśmy kilka nowych pomysłów i technik, które wierzymy, że są wartościowe same w sobie z algorytmicznego punktu widzenia.

Referat bazuje na wspólnej pracy z Jarosławem Byrką oraz Joachimem Spoerhase opublikowanej pt. Constant-factor approximation for Ordered $k$-Median na konferencji STOC 2018.

We propose a resolution for the issue of applicability of kernel-$k$-means for non-embeddable kernel matrices. We investigated several euclidization methods commonly used in the literature, including the Theorem 7 of Gower and Legendre from [1] on transformations from an non-embeddable distance matrix to an embeddable one. We have shown experimentally that this theorem is wrong in both parts referring to works of Lingoes and Cailliez. We demonstrated that the Lingoes transformation yields same results for kernel-$k$-means clustering prior and after this transformation. We showed that Cailliez transformation does not have this property.

Only if we accept the Lingoes euclidization transformation as a legitimate kernel matrix transformation and the kernel-$k$-means clustering in the kernel matrix obtained via such euclidization as the valid clustering for the original kernel matrix, then we can apply the kernel-trick for kernel-$k$-means also in the non-Euclidean space. Other transformations yield inconsistent results.

Joint work with Robert Kłopotek.

References

1. J.C. Gower, P. Legendre, Metric and Euclidean properties of dissimilarity coefficients, Journal of Classification 3, 5–48, 1986.

W naszej pracy rozważamy problem znalezienia poprawnego dwukolorowania dla hipergrafów niejednorodnych spełniających wzmocniony warunek Lokalnego Lematu Lovásza. Bazując na algorytmie opracowanym przez Czumaja i Scheidelera oraz algorytmie Mosera-Tardosa, konstruujemy algorytm lokalny dla tego problemu.

Praca wspólna z Jakubem Kozikiem.

Literatura

1. Noga Alon, A parallel algorithmic version of the local lemma, Random Structures Algorithms, 2(4), 367–378, 1991.
2. Artur Czumaj, Christian Scheideler, Coloring non-uniform hypergraphs: a new algorithmic approach to the general Lovász local lemma, in: Proceedings of the Eleventh Annual ACM–SIAM Symposium on Discrete Algorithms (San Francisco, CA, 2000), pp. 30–39, ACM, New York, 2000.
3. Robin A. Moser, Gábor Tardos, A constructive proof of the general Lovász Local Lemma, J. ACM, 57(2), Art. 11, 15, 2010.
4. Ronitt Rubinfeld, Gil Tamir, Shai Vardi, Ning Xie, Fast local computation algorithms, in: ICS 2011, pp. 223–238, 2011.

Miary centralności są powszechnie używanym narzędziem do oceny istotności elementów w sieci. Podczas gdy większość z występujących w literaturze miar oparta jest na najkrótszych ścieżkach, my proponujemy nową centralność – Centralność Zanikania Błądzenia Losowego (ang. Random Walk Decay Centrality) – która oparta jest na błądzeniu losowym po sieci. Proponujemy również jej aksjomatyczną charakteryzację, co pozwala zobaczyć, że jest ona blisko związana z PageRankiem: udowadniamy, że biorąc jeden aksjomat z charakteryzacji Centralności Zanikania Błądzenia Losowego – Brak Samoodziaływania (ang. Lack of Self-Impact) – i zamieniając go na inny aksjomat – Zamiana Krawędzi (ang. Edge Swap), otrzymujemy aksjomatyzację PageRanka. Dodatkowo pokazujemy, że Brak Samoodziaływania jest pożądaną własnością w wielu kontekstach, a niespełnianie Zamiany Krawędzi może pozytywnie przyczynić się do promocji większego zróżnicowania w sieci.

Miary centralności służą wskazaniu, które węzły są kluczowe dla sieci. Betweenness jest jedną z takich miar, można ją z grubsza interpretować jako ułamek wszystkich najkrótszych ścieżek pomiędzy dwoma węzłami w sieci zawierających dany węzeł. Węzeł jest tym ważniejszy, im więcej najkrótszych ścieżek przez niego przechodzi. Jednakże liczenie tej miary jest kosztowne obliczeniowo.

Geometria hiperboliczna ostatnimi czasy jest stosowana w analizie sieci społecznych. W szczególności Dyskretny Model Hiperbolicznych Grafów Losowych (DHRG) może być użyty do wygenerowania sieci, które cechują się właściwościami zbliżonymi do tych posiadanych przez rzeczywiste sieci. Po zanurzeniu sieci w płaszczyznie hiperbolicznej z wykorzystaniem modelu DHRG, reinterpretujemy definicję miary centralności, otrzymując hiperboliczne pseudo-betweenness. Wiadomo, że grafy o drzewiastej strukturze cechują się dobrymi własnościami algorytmicznymi. W szczególności dzięki nim nasze hiperboliczne pseudo-betweenness można policzyć efektywnie. Porównujemy również naszą miarę z innymi istniejącymi miarami centralności.

Praca wspólna z Erykiem Kopczyńskim.

Odkrycie drzew behawioralnych miało ogromny wpływ na rozwój sztucznej inteligencji (AI) stosowanej w grach komputerowych. Istniejące prace naukowe skupiają się na opracowaniu AI, które będzie osiągało jak najlepsze wyniki w danej grze. Z drugiej strony, istotnym problemem zdiagnozowanym w branży gier komputerowych jest brak użytkowników w początkowym etapie cyklu życia gry, a zastosowanie na tym etapie zaawansowanego AI prowadzi do zniechęcenia potencjalnych graczy. Podczas referatu omówione zostaną prace wykonane w ramach projektu nr POIR.01.02.00-00-0108/16 realizowane wspólnie z Baad Games Studio. Celem prowadzonych badań było opracowanie metodologii konstrukcji algorytmu sztucznej inteligencji imitujących styl gry rzeczywistych graczy. Zagadnienie to zostało sformułowane jako problem optymalizacji dyskretno-ciągłej w przestrzeni drzew behawioralnych, przy funkcji kryterialnej oceniającej podobieństwo między rozgrywką wzorcową rzeczywistego gracza a ocenianym drzewem behawioralnym. Zostaną przedstawione również rezultaty przeprowadzonych eksperymentów numerycznych, które wykazały perspektywiczność zastosowanego podejścia.

Praca wspólna z Andrzejem Kozikiem, Tomaszem Machalewskim i Adrianem Ochmannem.

W tym referacie wprowadzamy problem izomorfizmu wyborów oraz jego przybliżony wariant, problem odległości izomorficznej między wyborami. Pokazujemy, że problem izomorfizmu wyborów jest bardzo łatwy (w szczególności ma prosty algorytm wielomianowy), podczas gdy złożoność obliczeniowa problemu odległości wyborów ściśle zależy od użytej metryki między porządkami preferencji. Pokazujemy zarówno przykład, gdzie problem ten ma algorytm wielomianowy, jak i bardzo naturalną metrykę, przy której jest NP-trudny, trudny do aproksymacji oraz pozbawiony algorytmów FPT. Co gorsza, nasza odległość wydaje się także trudna do obliczenia w praktyce, przy pomocy solwerów ILP.

Argumentujemy, czemu mierzenie odległości między wyborami jest przydatne i jakie problemy można dzięki niemu podejmować. Prezentacja oparta jest na naszym wspólnym artykule zaprezentowanym niedawno na konferencji AAAI 2019 [1].

Praca wspólna z Piotrem Skowronem, Arkadim Sliniko, Stanisławem Szufą i Nimrodem Talmonem.

Literatura

1. P. Faliszewski, P. Skowron, A. Slinko, S. Szufa, N. Talmon, How similar are two elections?, AAAI 2019.