| Powrót do listy seminariów |
Seminarium Zakładu Analizy Algorytmów
Prowadzą: Wojciech Rytter i Krzysztof Diks
Seminarium posiada własną stronę internetową.
| 2012-05-31, godz. 12:15, s. 5870 |
| Anna Zych & Attila Bernath (Uniwersytet Warszawski) |
| The Maximum Independent Set problem on intersection graphs & Covering minimum cost arborescences |
| The Maximum Independent Set problem on intersection graphs I will talk about the Maximum Independent Set problem on intersection graphs. An independent set is a set of vertices in the graph that are pairwise disjoint. In general graphs, the problem of finding the maximum independent set of vertices is hard to approximate within a ratio asymptotically better than 1/|V|, where V is the set of vertices of the graph. However the instances we get in reality are often not that pessimistic. Sometimes, for some routing or planning purposes, we care to find a maximum set of geometric objects in the plane that do not intersect. An intersection graph is a graph where the vertices correspond to shapes given in the plane and there is an edge between two vertices iff the corresponding shapes intersect. In particular, every planar graph is an intersection graph of stars. A lot of classes of intersection graphs have been defined depending on the type and the location of the objects in the plane. For most of these classes the hardness status of the Maximum Independent Set problem is known. This is not the case, however, for the class of outerstring graphs, although the Independent Set problem on outerstring graphs models many realistic routing scenarios. I will end up presenting a step forward to determining the hardness of this problem, which is a polynomial time algorithm for the Maximum Independent Set in outersegment graphs (a subclass of outerstring graphs). The main purpose of this talk is to wake the interest to solve the problem in outerstring graphs. ========================= Covering minimum cost arborescences Given a digraph $D=(V,A)$ with a designated root node $r\in V$ and arc-costs $c:A\to \Rset$, we consider the problem of finding a minimum cardinality subset $H$ of the arc set $A$ such that $H$ intersects every minimum $c$-cost $r$-arborescence. (By an $r$-arborescence we mean an inclusionwise minimal subset of arcs of $D$, in which every node is reachable from $r$.) This problem is a special case of covering minimum cost common bases of two matroids, which is NP-complete even if the two matroids coincide, and the costs are all equal to 1. On the other hand we show that this special case is polynomially solvable: we give a polynomial algorithm for finding such an arc set $H$. The algorithm solves a weighted version as well, in which a nonnegative weight function $w:A\to \Rset_+$ is also given, and we want to find a subset $H$ of the arc set such that $H$ intersects every minimum $c$-cost $r$-arborescence, and $w(H)$ is minimum. This is a joint result with Gyula Pap. |
| 2012-05-24, godz. 12:15, s. 5870 |
| Andras Sebo (CNRS, Laboratoire G-SCOP, Grenoble) |
| TSP and related problems via Matroids, Matchings and Extensions |
| I present improved approximation guarantees for the graphic TSP and some related problems. For the graphic TSP itself, the new approximation ratio is $7/5$. For a generalization, the connected-$T$-join problem, we obtain the first nontrivial approximation algorithm, with ratio $3/2$. This contains the graphic $s$-$t$-path-TSP as a special case. Our improved approximation guarantee for finding a smallest $2$-edge-connected spanning subgraph is $4/3$. The key new ingredient of all our algorithms is a special kind of ear-decomposition optimized using forest representations of hypergraphs, a particular matroid intersection problem. Matchings, Joins, Matroids are the key-words of this approach. I would like to communicate the intuition that leads from these classical notions to the new approximation results. These are common results with Jens Vygen. |
| 2012-05-10, godz. 12:15, s. 5870 |
| Gruia Calinescu (Illinois Institute of Technology) |
| Minimum Power Strong Connectivity |
| Given a directed simple graph G=(V,E) and a nonnegative-valued cost function the power of a vertex u in a directed spanning subgraph H is given by the maximum cost of an arcs of H exiting u. The power of H is the sum of the power of its vertices. Power Assignment seeks to minimize the power of H while H satisfies some connectivity constraint. In this paper, we assume E is bidirected (for every directed edge e in E, the opposite edge exists and has the same cost), while H is required to be strongly connected. This is the original power assignment problem introduce in 1989 and since then the best known approximation ratio is 2 and is achieved by a bidirected minimum spanning tree. We improve this to 2 - epsilon for a small positive epsilon, by combining techniques from Robins-Zelikovsky (2000), Christofides (1976), and Caragiannis, Flammini, and Moscardelli (2007), together with a novel property on T-joins in certain hypergraphs. We also present a integer/linear programming formulation, a fast variant of the approximation algorithm, and simulation results comparing new and previously proposed heuristics with the above exact and approximation algorithms, showing tradeoffs between the running time and the quality of the output. This part joint work with Kan Qiao. |
| 2012-03-08, godz. 12:15, s. 5870 |
| Marcin Mucha (Uniwersytet Warszawski) |
| (Graphic) TSP approximation |
| During the recent year, a lot of progress has been made on approximating the Traveling Salesman Problem and the Traveling Salesman Path Problem, and in particular their graphic variants. In this talk I will briefly survey the recent results and show in more detail the papers by Momke and Svensson, and my own. |
| 2012-02-23, godz. 12:15, s. 5870 |
| Wojciech Tyczynski (Uniwersytet Warszawski) |
| Computing factorization forest of a small depth |
| Assume we have a finite set Q and set of all binary relations over Q: R_Q. Let w be the word over alphabet R_Q. An evaluation of word w is the composition of all letters of w. A factorization forest for w is a laminar family of factors of w that contains {x} for every position x. A collation of the set of consecutive factors of w is any concatenation of those factors that is also a factor of w. A set of consecutive factors is called homogeneous if all their collations have the same evaluation. A factorization forest is called homogeneous if any choice of at least three consecutive siblings is homogeneous. During the seminar I will show that for any word w we can construct a homogeneous factorization forest of height at most polynomial in |R_Q| (independently of the length of w!). I will present the algorithm for constructing such forest in time O(Q^3 w). This algorithm is the part of Paweł Parys PhD thesis. |
| 2012-01-12, godz. 12:15, s. 5870 |
| Marcin Pilipczuk (Uniwersytet Warszawski) |
| A glimpse on my PhD thesis |
| In my talk I will present the main results of my PhD thesis. I plan to focus mostly on the background of my research, motivation, and present a very general overview of the techniques - without any technical details. The talk will be divided into two parts. The first part, titled `Beyond 2^n', is devoted to the main line of research in moderately-exponential algorithms: can NP-hard problems be solved faster than the naive brute-force search (or straightforward dynamic programming)? In many cases, the brute-force solution or the DP one runs in 2^n time, where n is the number of vertices, variables or other entities in the considered problem. I will briefly summarize known approaches how to `break the 2^n barrier', and talk about the results of the thesis: algorithms for Capacitated Dominating Set (SWAT'10), Minimum Maximal Irredundant Set (CIAC'10), and, finally, a scheduling problem denoted 1|prec|sum C_i (ESA'11). In the second part I will move to the area of fixed-parameter tractability. The main topic of this part will be the parameterized complexity of graph separation problems. I will present the background and the current state of this area and give a glimpse of the techniques used in the main contribution of the thesis: a fixed-parameter algorithm for the Subset Feedback Vertex Set problem (ICALP'11). I will conclude with a very short note on the last result of the dissertation: kernelization hardness of connectivity problems in graphs of bounded degeneracy (WG'10). |
| 2011-12-08, godz. 12:15, s. 5870 |
| Aleksander Madry (Microsoft Research New England i EPFL) |
| Electrical Flows, Laplacian Systems, and Faster Approximation of Maximum Flow in Undirected Graphs |
In this talk, I'll describe a new technique for approximating the maximum flow in capacitated, undirected graphs. I'll then use this technique to develop the asymptotically fastest-known algorithm for solving this problem.  |
| 2011-12-01, godz. 12:15, s. 5870 |
| Krzysztof Rządca (Uniwersytet Warszawski) |
| Teoriogrowe mechanizmy zwiększania dostępności danych w rozproszonych systemach replikacyjnych |
W systemach przechowywania danych w architekturze peer-to-peer, użytkownicy zwiększają dostępność danych przez wzajemne ich replikowanie. Centralny system pośredniczący w zawieraniu umów replikacyjnych może zoptymalizować dostępność danych tak, by wszyscy użytkownicy mieli podobny poziom dostępności. Jeśli jednak umowy zawierane są w sposób zdecentralizowany przez samych użytkowników, ich egoizm prowadzi do nierówności, skutkujących ograniczeniem niezawodności danych nowych użytkowników, a więc i zmniejszeniu popularności całego systemu. |
| 2011-11-24, godz. 12:15, s. 5870 |
| Riste Skrekovski (Uniwersytet Warszawski) |
| Some results on fullerene graphs |
Fullerene graphs are 3-connected planar cubic graphs with all faces of size 5 or 6. Motivation to study this class of graphs came from chemistry. In my talk I will present some bounds on the invariants as diameter, the independence number, the smallest eigenvalue, bipartite edge frustration, and saturation number. |
| 2011-11-17, godz. 12:15, s. 5870 |
| Christian Wulff-Nilsen (University of Southern Denmark) |
| Approximate Distance Oracles with Faster Preprocessing and Query Time |
Given an undirected graph G with m edges, n vertices, and non-negative edge weights, and given an integer k>=2, we show that for some constant c, a (2k-1)-approximate distance oracle for G of size O(kn^{1 + 1/k}) can be constructed in O(\min\{kmn^{1/k},\sqrt km + kn^{1 + c/\sqrt k}\}) time and can answer queries in O(\log k) time. This improves the O(k) query time of Thorup and Zwick and breaks the quadratic preprocessing time bound of Baswana and Kavitha for m = o(n^2) and all $k\geq 6$. When m = \Omega(n^{1 + c/\sqrt k}) and k = O(1), our oracle is optimal w.r.t.\ both stretch, size, preprocessing time, and query time, assuming a widely believed girth conjecture by Erd\H{o}s. We also give, for any \epsilon > 0, an oracle of size O(kn^{1 + 1/k}) which answers (2 + \epsilon)k-approximate distance queries in O(1/\epsilon) time. At the cost of a k-factor in size, this improves the 128k approximation achieved by the constant query time oracle of Mendel and Naor. We can match their O(n^{1 + 1/k}) size bound for any constant \epsilon > 0 and k = O(\log n/\log\log n). |
| 2011-11-03, godz. 12:15, s. 5870 |
| Wojciech Tyczyński (Uniwersytet Warszawski) |
| Wykorzystanie teorii automatów do przetwarzania dokumentów XML cz. II |
Tematem seminarium będzie algorytm, który dla zadanego zapytania XPath \phi oraz dokumentu XMLowego t zwraca zbiór wierzchołków t, które spełniają zadaną formułę. Silniki, które zawierają algorytmy ewaluacji zapytań XPath są wbudowane we wszystkie przeglądarki internetowe. Jednakże są one tam bardzo nieefektywne - zdarza się, że ich złożoność jest wielomianem stosunkowo wysokiego stopnia względem rozmiaru dokumentu XML. W ramach seminarium zaprezentuję algorytm, który bez względu na zapytanie jest liniowy względem wielkości dokumentu, aczkolwiek nie jest już liniowy względem długości zapisu formuły XPath. Cała prezentacja jest w całości oparta na pracy doktorskiej Pawła Parysa. |
| 2011-10-27, godz. 12:15, s. 5870 |
| Wojciech Tyczyński (Uniwersytet Warszawski) |
| Wykorzystanie teorii automatów do przetwarzania dokumentów XML |
Tematem seminarium będzie algorytm, który dla zadanego zapytania XPath \phi oraz dokumentu XMLowego t zwraca zbiór wierzchołków t, które spełniają zadaną formułę. Silniki, które zawierają algorytmy ewaluacji zapytań XPath są wbudowane we wszystkie przeglądarki internetowe. Jednakże są one tam bardzo nieefektywne - zdarza się, że ich złożoność jest wielomianem stosunkowo wysokiego stopnia względem rozmiaru dokumentu XML. W ramach seminarium zaprezentuję algorytm, który bez względu na zapytanie jest liniowy względem wielkości dokumentu, aczkolwiek nie jest już liniowy względem długości zapisu formuły XPath. Cała prezentacja jest w całości oparta na pracy doktorskiej Pawła Parysa. |
| 2011-10-20, godz. 12:15, s. 5870 |
| Attila Bernáth (Uniwersytet Warszawski) |
| Degree-bounded spanning trees and matroids |
| Materiały dotyczące referatu |
Consider the problem of finding a minimum cost spanning tree in a graph with the additional requirement that the degree of each node in the tree should not exceed an upper bound given in advance. This problem is hard: already the problem of deciding whether such a tree exists is NP-complete, so it does not really make sense to speak about an approximation algorithm. |
| 2011-06-02, godz. 12:15, s. 5870 |
| Saket Saurabh ( Institute of Mathematical Sciences, Chennai, India) |
| Chromatic Coding |
| Alon, Yuster and Zwick developed the method of color-coding to give a 2^O(k)n^O(t) time algorithm for subgraph isomorphism problem when the subgraph we are looking for has treewidth t and size k. We develop a variation of this method, called Chromatic Coding, where one is interested in just properly coloring the subgraph one is seeking for, as opposed to color coding, where every vertex gets a distinct color. Using this method we develop the first subexponential time algorithms for feedback arc set in tournaments, dense instances of betweenness and minimum quartet inconsistency. In this talk we will introduce the method of Chromatic Coding through the example of feedback arc set in tournaments. (This is a joint work with Noga Alon and Daniel Lokshtanov.) |
| 2011-05-12, godz. 12:15, s. 5870 |
| Jakub Łącki (Uniwersytet Warszawski) |
| Min-cuts and Shortest Cycles in Planar Graphs in O(n log log n) Time |
We present a deterministic O(n log log n) time algorithm for finding shortest cycles and minimum cuts in planar graphs. The algorithm improves the previously known fastest algorithm by Italiano et al. in STOC'11 by a factor of log n. This speedup is obtained through the use of dense distance graphs combined with a divide-and-conquer approach. Joint work with Piotr Sankowski. |
| 2011-05-05, godz. 12:15, s. 5870 |
| Piotr Sankowski (Uniwersytet Warszawski) |
| Dynamiczne algorytmy tekstowe |
| Tematem tego seminarium będzie technika stworzona przez K. Mehlhorn, R. Sundar i C. Uhrigw pracy "Maintaining dynamic sequences under equality tests in polylogarithmic time", która umożliwia dynamiczne utrzymywanie informacji o sekwencjach i pozwala na wykonywanie na nich testów równości. Opowiem także o uogólnieniu i poprawieniu tego wyniku przez S. Alstrup, G. S. Brodal, i T. Rauhe w "Pattern Matching in Dynamic Text", które oprócz przyspieszania czasu działania pozwala na dynamiczne wyszukiwanie podsłów. |
| 2011-04-21, godz. 12:15, s. 5870 |
| Marek Cygan (Uniwersytet Warszawski) |
| Cut&count technique for connectivity problems parameterized by treewidth |
| The notion of treewidth, introduced in 1984 by Robertson and Seymour, has in many cases proved to be a good measure of the intrinsic difficulty of various NP-hard problems on graphs, and a useful tool for attacking those problems. Many of them can be efficiently solved through dynamic programming if we assume the input graph to have bounded treewidth. For several problems with global connectivity requirement the best known algorithms were of t^O(t) n^O(1) time complexity, where t is the width of the given tree decomposition. We present a technique named Cut&Count that allows us to produce c^t n^O(1) Monte Carlo algorithms for most connectivity type problems, including Hamiltonian Path, Feedback Vertex Set and Connected Dominating Set. The constant c we obtain is in all cases small (at most 4 for undirected problems and at most 6 for directed ones), and in several cases we are able to show that improving those constants would cause the Strong Exponential Time Hypothesis to fail. Our results have numerous consequences in various fields, like FPT algorithms, exact and approximate algorithms on planar and H-minor-free graphs and algorithms on graphs of bounded degree. In all these fields we are able to improve the best-known results for some problems. This is a joint work with Jesper Nederlof, Marcin Pilipczuk, Michał Pilipczuk, Johan van Rooij, Jakub Onufry Wojtaszczyk. |
| 2011-04-14, godz. 12:15, s. 5870 |
| Artur Czumaj (University of Warwick) |
| Almost Tight Bounds for Reordering Buffer Management |
| In this talk we will study the nowadays classical online problem of buffer reordering. In the reordering buffer management problem a stream of colored items arrives at a service station and has to be processed. The cost for servicing the items heavily depends on the processing order: servicing an item with color c, when the most recently serviced item had color c' <> c, incurs a context switching cost w_c. In order to reduce the total processing cost, the servicing station is equipped with a reordering bu ffer able to store k items. This buff er can be used to reorder the input sequence in a restricted fashion to construct an output sequence with lower processing cost. At each point in time, the buffer contains the first k items of the input sequence that have not yet been processed. A scheduling strategy has to decide which item to service next. Upon its decision, the corresponding item is removed from the buff er and serviced, while the next item from the input sequence takes its place in the buffer. In this talk I'll present almost tight bounds for the online reordering buffer management problem on the uniform metric. This is a joint work with Anna Adamaszek, Matthias Englert, and Harald Raecke. |
| 2011-04-07, godz. 12:15, s. 5870 |
| Brak seminarium z powodu FIT, OI |
| 2011-03-31, godz. 12:15, s. 5870 |
| Dominik Scheder (ETH Zurich) |
| A Full Derandomization of Schoenings k-SAT Algorithm |
Schoening in 1999 presented a simple randomized algorithm for k-SAT with running time O(a^n * poly(n)) for a = 2(k-1)/k. We give a deterministic version of this algorithm running in time O(a^(n+o(n))).
|
| 2011-03-31, godz. 12:15, s. 5870 |
| Dominik Scheder (ETH Zurich) |
| A Full Derandomization of Schoening's k-SAT Algorithm |
| Schoening in 1999 presented a simple randomized algorithm for k-SAT with running time O(a^n * poly(n)) for a = 2(k-1)/k. We give a deterministic version of this algorithm running in time O(a^(n+o(n))). Joint work with Robin A. Moser. |
| 2011-03-31, godz. 12:15, s. 5870 |
| Dominik Scheder (ETH Zurich) |
| A Full Derandomization of Schoening's k-SAT Algorithm |
| Schoening in 1999 presented a simple randomized algorithm for k-SAT with running time O(a^n * poly(n)) for a = 2(k-1)/k. We give a deterministic version of this algorithm running in time O(a^(n+o(n))). Joint work with Robin A. Moser. |
| 2011-03-17, godz. 12:15, s. 5870 |
| Dariusz Leniowski (Uniwersytet Warszawski) |
| Prawdomownosc a budzet w aukcjach -- wynik negatywny i pozytywny. |
| Na seminarium zostanie przedstawiony wynik Christiana Borgsa i innych dotyczacy wieloprzedmiotowych aukcji z budzetami. Dla systemow prawdomownych kluczowy okaze sie warunek sprzedzy wszystkich przedmiotow, a jego opuszczenie pozwoli na opracowanie aukcji (asymptotycznie) maksymalizujacej zysk. |
| 2011-03-10, godz. 12:15, s. 5870 |
| Paweł Brach (Uniwersytet Warszawski) |
| Rozpowszechnianie plotki w sieciach społecznościowych |
Na seminarium zostanie omówiona grupa algorytmów rozpowszechniania plotki w sieciach społecznościowych. Takie algorytmy używają losowej komunikacji podczas której dochodzi do wymiany informacji pomiędzy węzłami. W omawianym modelu będziemy myśleli o n graczach, którzy w każdej rundzie komunikują się z losowo wybranym partnerem. Podczas komunikacji dochodzi do przekazania plotki. Zostaną zdefiniowane znane algorytmy rozpowszechniania plotki: Push, Pull oraz Push & Pull. Przedstawione zostaną dotychczasowe wyniki, w których próbuje się opisywać dynamikę procesu rozpowszechniania plotki za pomocą równań pola średniego. |
| 2011-03-03, godz. 12:15, s. 5870 |
| Piotr Sankowski (Uniwersytet Warszawski) |
| Combinatorial Auctions with Budgets |
| We consider budget constrained combinatorial auctions where bidder i has a private value v_i, a budget b_i, and is interested in all the items in S_i. The value to agent i of a set of items R is v_i times the size of the intersection between R and S_i. Such auctions capture adword auctions, where advertisers offer a bid for ads in response to an advertiser-dependent set of adwords, and advertisers have budgets. It is known that even of all items are identical and all budgets are public it is not possible to be truthful and efficient. Our main result is a novel auction that runs in polynomial time, is incentive compatible, and ensures Pareto-optimality for such auctions when the valuations are private and the budgets are public knowledge. This extends the result of Dobzinski et al. (FOCS 2008) for auctions of multiple identical items and public budgets to single-valued combinatorial auctions with public budgets. Joint work with Amos Fiat, Jared Saia, Stefano Leonardi |
| 2011-02-24, godz. 12:15, s. 5870 |
| Konstanty Junosza-Szaniawski (Politechnika Warszawska) |
| Exact algorithms for L(2,1)-labeling of graphs |
| $L(2,1)$-labeling is a graph coloring model inspired by a channel assignment problem in telecommunication. It asks for such a labeling of vertices with nonnegative integers that adjacent vertices get labels that differ by at least $2$ and vertices in distance $2$ get different labels. It is known that for any fixed $k \geq 4$ it is NP-complete to determine if a graph has a $L(2,1)$-labeling with no label greater than $k$. In this paper we present an improved bound on complexity of an algorithm for finding an optimal $L(2,1)$-labeling (i.e. an $L(2,1)$-labeling in which the largest label is the least possible). We improve the upper complexity bound of the algorithm from $O^* (3.56^n)$ to $O^*(3.23^n)$. Moreover, we establish a lower complexity bound, which is $\Omega^{*} (3.07^n)$. |
| 2011-02-17, godz. 12:15, s. 5870 |
| dr hab Jerzy Tyszkiewicz (Uniwersytet Warszawski) |
| Parallel Random Access Machines and Spreadsheets are (Almost) the Same |
| In the talk I will describe a mild syntactic restriction concerning spreadsheets (created in e.g. MS Excel or OpenOffice), which turns them into a computing device almost equivalent to Parallel Random Access Machines. Under this restriction, columns and rows of spreadsheets correspond to to time and memory/processors of PRAM, respectively. I will also demonstrate that other variants of restrictions imposed on spreadsheet do not behave so well. Finally, I will sketch some practical consequences of these results. |
| 2011-01-20, godz. 12:15, s. 5870 |
| Jarosław Grytczuk (Uniwersytet Jagielloński) |
| Nonrepetitive coloring games |
Nonrepetitive coloring games can be played on various combinatorial structures (graphs, words, etc.). Basic idea goes back to Thue, who proved in 1906 that the ntegers can be 3-colored so that any two adjacent segments are not indentical. his striking result has been generalized in many directions, leading to a variety f peculiar coloring problems. Is it true, for instance, that planar graphs can be olored with a bounded number of colors so that any simple path is nonrepetitive?
|
| 2011-01-13, godz. 12:15, s. 5870 |
| Seminarium odwołane |
| 2010-12-16, godz. 12:15, s. 5870 |
| Krzysztof Onak (CMU) |
| Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity |
| We present a near-linear time algorithm for approximating the edit distance between two strings to within a significantly better factor than previously known. This result emerges in our investigation of edit distance from a new perspective, namely a model of asymmetric queries, for which we present near-tight query complexity bounds. Another consequence of this new model is the first rigorous separation between edit distance and Ulam distance, which we obtain by tracing the hardness of edit distance back to a phenomenon that was not used before. Joint work with Alexandr Andoni and Robert Krauthgamer. |
| 2010-12-09, godz. 12:15, s. 5870 |
| Łukasz Kowalik (Uniwersytet Warszawski) |
| Cykl Hamiltona w grafach nieskierowanych szybciej niz 2^n. |
| Problemy cyklu Hamiltona i TSP to jedne z najintensywniej badanych problemow optymalizacyjnych. W latach 60-tych Held i Karp podali prosty algorytm oparty na programowaniu dynamicznym, wymagajacy czasu O*(2^n) i pamieci O(2^n). Powstalo naturalne pytanie, czy te granice da sie przekroczyc. Szybko okazalo sie ze w przypadku cyklu Hamiltona, ktory jest problemem odrobine prostszym mozna uzyskac mala poprawe: za pomoca zasady wlaczen i wylaczen uzyskuje sie pamiec wielomianowa bez pogorszenia czasu dzialania. I ten stan rzeczy utrzymywal sie przez niemal... 50 lat. Dopiero w tym roku Andreas Bjorklund wykazal, ze problem cyklu Hamiltona w grafach nieskierowanych mozna rozwiazac w czasie O*(2^{3/4n}). Podczas referatu opowiem ze szczegolami algorytm dla przypadku grafow dwudzielnych, ktory jest dosc prosty i dziala w czasie O*(2^{n/2}) = O(1.42^n). Nastepnie naszkicuje jak ten algorytm rozszerza sie do przypadku ogolnego. |
| 2010-12-02, godz. 12:15, s. 5870 |
| Maxime Crochemore (King's College London) |
| Reactive Automata |
| 2010-11-25, godz. 12:15, s. 5870 |
| Bartlomiej Bosek i Tomasz Krawczyk (Uniwersytet Jagielloński) |
| The sub-exponential upper bound for the on-line chain partitioning problem |
| One of the important models for scheduling is based on partially ordered sets. In this model the points represent the incoming tasks and the order reflects cause-effect relation between tasks. The algorithmic problem which arises in this model is to divide on-line the set of points of the poset into chains: the tasks from a common chain will be executed by a single device. Keeping this constraint, which asserts the optimality of the execution time, the scheduler tries to minimize the number of devices needed. It naturally leads to the on-line chain partitioning problem. So far the best known on-line algorithm partitioning a poset of width $w$ is the one of Kierstead and uses at most $(5^w-1)/4$ chains; on the other hand Szemer\'{e}di proved that any such algorithm requires at least $\binom{w+1}{2}$ chains. These results were obtained in the early 1980's and since then no progress has been done. Following Trotter's chapter \emph{Partially ordered sets} of the \emph{Handbook of Combinatorics}, the main problem here is to narrow these bounds and in particular to decide whether there exists an on-line algorithm that partitions posets of width at most $w$ into polynomial number of chains. In this paper we provide an on-line algorithm that partitions posets of width $w$ into at most $w^{14\log{w}}$ chains. This yields the first sub-exponential upper bound for the on-line chain partitioning problem. |
| 2010-11-04, godz. 12:15, s. 5870 |
| Marcin Pilipczuk (Uniwersytet Warszawski) |
| Unique Games Conjecture i trudność aproksymacji |
Począwszy od sławnego twierdzenia PCP, do dnia dzisiejszego znamy bardzo dużo wyników dowodzących trudność aproksymacji różnych problemów. O ile dowodzenie braku istnienia PTASa jest zazwyczaj mniej lub bardziej skomplikowaną redukcją kombinatoryczną, o tyle otrzymani ścisłych oszacowań, pokrywających się z najlepszymi znanymi algorytmami aproksymacyjnymi, wymaga często zaawansowanych technik z rachunku prawdopodobieństwa i analizy fourierowskiej. W czasie referatu zaszkicuję historię tej dziedziny, pokażę podstawowe techniki oraz postaram się uzasadnić znaczenie hipotezy Unique Games. Referat powstał w oparciu o warsztaty dotyczące trudności aproksymacji, które organizowaliśmy z Markiem Cyganem, Michałem Pilipczukiem i Jakubem Wojtaszczykiem.
|
| 2010-10-21, godz. 12:15, s. 5870 |
| Jakub Łącki (Uniwersytet Warszawski) |
| Dynamiczne algorytmy dla silnie spójnych składowych i domknięcia przechodniego |
| Zaprezentuję strukturę danych, która utrzymuje strukturę silnie spójnych składowych grafu skierowanego i obsługuje operacje usunięć krawędzi. Przy jej użyciu pokażę algorytm utrzymywania domknięcia przechodniego podczas usuwania krawędzi z grafu. Działa on deterministycznie i jest równie wydajny, jak najszybszy dotychczas znany algorytm randomizowany oraz o rząd wielkości szybszy od najszybszych algorytmów deterministycznych. Wszystkie prezentowane algorytmy są proste i opierają się jedynie na elementarnej wiedzy z teorii grafów. |
| 2010-10-14, godz. 12:15, s. 5870 |
| Jakub Pawlewicz (Uniwersytet Warszawski) |
| Zliczanie liczb bezkwadratowych |
| Liczba bezkwadratowa, to taka, która nie ma dzielników kwadratowych Liczenie liczby liczb bezkwadratowych nie większych od n dotychczas potrafiliśmy robić w czasie O(n^1/2). Przedstawię algorytm działający w czasie O(n^2/5) w pamięci O(n^1/5), który dodatkowo dobrze się zrównolegla. Dotychczas największa policzona wartość jest dla n=10^17 (Sloane A071172). Z użyciem mojej implementacji byłem w stanie policzyć wartość dla n=10^32 w 2 dni na 6 procesorach. |
| 2010-10-07, godz. 12:15, s. 5870 |
| Jaroslaw Byrka (Uniwersytet Wrocławski) |
| An Improved LP-based Approximation for Steiner Tree |
| The Steiner tree problem is: given a weighted undirected graph and a subset of terminal nodes, find a minimum-cost tree spanning the terminals. In a sequence of papers, the approximation ratio for this problem was improved from $2$ to the current best $1.55$ [Robins,Zelikovsky-SIDMA'05]. All these algorithms are purely combinatorial. A long-standing open problem is whether there is an LP-relaxation for Steiner tree with integrality gap smaller than $2$ [Vazirani,Rajagopalan-SODA'99]. In this paper we improve the approximation factor for Steiner tree, developing an LP-based approximation algorithm. Our algorithm is based on a, seemingly novel, \emph{iterative randomized rounding} technique. We consider a directed-component cut relaxation for the $k$-restricted Steiner tree problem. We sample one of these components with probability proportional to the value of the associated variable in the optimal fractional solution and contract it. We iterate this process for a proper number of times and finally output the ampled omponents together with a minimum-cost terminal spanning tree in the remaining graph. Our algorithm delivers a solution of cost at most $\ln(4)$ times the cost of an optimal $k$-restricted Steiner tree. This directly implies a $\ln(4)+\varepsilon<1.39$ approximation for Steiner tree. As a byproduct of our analysis, we also show that the integrality gap of our LP is at most $1.55$, hence answering to the mentioned open question. In the talk I will describe a slightly weaker, but less technical argument that provides 1.5-approximation for Steiner tree. |
| 2008-10-09, godz. 12:15 - 14, s. 5870 |
| Piotr Sankowski (Uniwersytet Warszawski) |
| Lokalne koalicje w grach na sieciach |
| Jakosc equilibrium Nasha w grach na sieciach zostala juz dobrze zrozumiana i seminarium zaczne od wprowadzenia problmu i przypomnienia najwazniejszych wynikow. Natomiast glownym tematem saminarium bedzie cena anarchii w grzach na sieci z kosztem Shaplya, w przypadku gdy dozwolone sa lokalne koalicje miedzy graczami. W przypadku rozproszonym nie zawsze mozliwe jest komunikacja i zawiazywanie sie koalicji miedzy dowolnymi zbiorami graczy, a gracze tworzacy koalicje musza nawzajem byc swiadomi swojgo istnienia. Tutaj bede zakladal, ze gracze ktorzy dziela jakis zasob moga utworzyc koalicje, w przypadku gier na sieciach oznacza, ze gracze wspoluzytkujacy jakas krawedz moga utworzyc koalicje. Pokarze, ze taki zalozenie prowadzi zo zmniejszenia sie ceny anarchii z k do log(k), w przypadku nieskierowanych gier o jednym terminalu, w ktorych w kazdym wierzcholku umieszczony jest gracz, a k to liczba graczy. W przypadku gier skierowanych, badz o wielu terminalach lokalne koalicje nie maja duzego wplywu na cene anarchii. A wrecz moga prowadzic do negatywnych skutow, gdyz w przypadku ceny stabilnosci zwieksza sie ona z log(k) do k. |
| 2007-11-29, godz. 12:15 - 14, s. 5870 |
| David Peleg (Weizmann Institute) |
| On time-efficient broadcast in wireless networks |
| As broadcasting is one of the primary functions in radio networks, fast algorithms for performing it are of considerable interest. A radio network consists of stations that can act at any a given time step either as transmitters or as receivers. Given a deployment of the stations, the reception conditions can be modeled by a graph, where the existence of an edge between two nodes indicates that transmissions of one of them can reach the other, i.e., these nodes can communicate directly. The message transmitted by a node in given time step is delivered in the same time step to all of its neighbors in the graph. A node acting as a receiver in a given step will successfully receive a message if and only if exactly one of its neighbors transmits in that step. If two or more neighbors of a node transmit simultaneously, then a collision occurs and none of the messages is heard by the node in that step. |
| 2007-10-04, godz. 16:15-17:45, s. 4420 |
| Madhu Sudan (Massachusetts Institute of Technology) |
| Sub-linear time algebraic algorithms |
| A modern thrust in computing is to design algorithms that take vast amounts of data and try to estimate properties of the data in a "quick and dirty" way. Sub-linear time algorithms is the area of theoretical computer science which presents design and rigorous analysis of such algorithms. The study of sublinear time algorithms started with the seminal work of Blum, Luby, and Rubinfeld (1990) who presented a "constant-time" algorithm to test if a function mapping a finite group to a finite group is essentially a homomorphism between the groups. This algorithm has since become quite famous as the "linearity test". The linearity test, and follow-up works, including "low-degree tests" (tests that check if a given multivariate function is essentially a low-degree polynomial) have become central elements in modern computational complexity (and form the heart of constructions of probabilistically checkable proofs (PCPs)). In this series of lectures we will describe the model of sublinear-time algorithms and present the (extremely simple) algorithms for linearity testing and low-degree testing. We will then describe some of analysis which draw upon algebra, geometry, analysis. |
| 2007-03-08, godz. 12:15 - 14, s. 5870 |
| Uri Zwick (Tel Aviv University) |
| Overhang (prowadzi: Uri Zwick) |
| How far off the edge of the table can we reach by stacking n identical blocks of length 1? A classical solution achieves an overhang of (1/2)H_n, where H_n=1/1+1/2+...+1/n is the n-th harmonic number. This solution is widely believed to be optimal. We show, however, that it is exponentially far from optimal by giving explicit constructions with an overhang of Omega(n^{1/3}). Together with Yuval Peres, Mikkel Thorup and Peter Winkler, we have recently shown that no larger overhangs are achievable. |
| 2007-01-11, godz. 12:15 - 14, s. 5870 |
| Darek Kowalski ( University of Liverpool) |
| Zlozonosc komunikacyjna algorytmow rozproszonych odpornych na wady |
| Przedstawie dwa podstawowe problemy rozproszone: consensus (decyzyjny) oraz gossip (komunikacyjny). Zaprezentuje szereg rozwiazan dla tych problemow ktore sa: odporne na wady (typu crash), szybkie oraz generujace niewielka ilosc komunikatow. Wiekszosc dotychczasowych algorytmow byla z reguly szybka i odporna na wady, natomiast ilosc komunikatow byla wielomianowa w przeliczeniu na kazdy wadliwy procesor, najnowsze prace pokazuja jak zmniejszyc te liczbe do polylogarytmicznej jednoczesnie zachowujac wlasnosci odpornosci na wady oraz szybkosci. |
| 2006-12-14, godz. 12:15 - 14, s. 5870 |
| Arkadiusz Paterek (Uniwersytet Warszawski) |
| Collaborative Filtering: Netflix Prize |
| In this talk, I will present different algorithms for the collaborative filtering task. The task of collaborative filtering is to predict the preferences of a user, given preferences of other users. An example of a commercial collaborative filtering system is the movie recommendation algorithm Netflix's Cinematch, which predicts the customer's rating for a given movie. Recently, Netflix, the world's largest online DVD rental service, released to the public a large database of 17770 movies, rated by 480189 customers, and announced a $1M prize for 10% improvement in prediction accuracy over Cinematch on the dataset. I will give an overview of my solution - better than Cinematch by over 3%. |
| 2006-10-26, godz. 12:15 - 14, s. 5870 |
| Marcin Mucha (Uniwersytet Warszawski) |
| Aproksymacja asymetrycznych wariantow problemu komiwojazera |
| Na najblizszym seminarium opowiem prace Haim Kaplan, Moshe Lewenstein, Nira Shafrir, Maxim Sviridenko "Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs". J. ACM 52(4): 602-626 (2005) (wczesniej extended abstract na FOCS 2003). Autorzy opracowali bardzo ladna i dosc ogolna technike aproksymacji asymetrycznych (tzn. funcja odleglosci nie jest symetryczna) wariantow problemow minTSP i maxTSP. Technika ta co prawda bazuje na programowaniu liniowym, ale zawiera takze bardzo eleganckie rozumowanie grafowe. Postaram sie aby moja prezentacja byla dostepna dla osob, ktore nie mialy okazji zajmowac sie aproksymacja. W szczegolnosci oznacza to, ze pokaze sporo rzeczy "standardowych" i nie bede wchodzil w bardziej zawile fragmenty omawianej pracy. Serdecznie zapraszam wszystkich zainteresowanych analiza algorytmow i kariera w biznesie taksowkowym. |
| 2006-10-12, godz. 12:15 - 14, s. 5870 |
| Łukasz Kowalik (Uniwersytet Warszawski) |
| Konferencja SODA; "Mierz i zwyciężaj": metoda analizy algorytmów wykładniczych. |
| Seminarium będzie się składało z dwóch części. Podczas części pierwszej krótko przedstawię najciekawsze wyniki z tegorocznej konferencji SODA. Nieco bardziej szczegółowo opowiem o pracy Fedor V. Fomin, Fabrizio Grandoni, Dieter Kratsch, "Measure and Conquer: A Simple O(2^0.288n) Independent Set Algorithm", która zawiera interesującą koncepcję (nazywną szumnie "mierz i zwyciężaj") analizowania złożoności czasowej algorytmów wykładniczych typu "branch-and-reduce". Podczas drugiej części przestawię własną pracę wykorzystującą m.in. metodę "mierz i zwyciężaj". Mój algorytm dotyczy 3-kolorowania krawędziowego grafów (dowolnych) i poprawia wcześniejszy algorytm autorstwa Beigela i Eppsteina, który działa w czasie O(2^(n/2)) Uwaga! Po seminarium planujemy wznowić stary zwyczaj swobodniejszej dyskusji przy kawie i ciastkach. |
| 2006-05-25, godz. 12:15 - 14, s. 5870 |
| Bartosz Przydatek (ETH w Zurychu) |
| Solving Medium-Density Subset Sum Problems in Expected Polynomial Time |
| Solving Medium-Density Subset Sum Problems in Expected Polynomial Time.
The subset sum problem (SSP) (given n numbers and a target bound B, find a subset of the numbers summing to B), is a classic NP-hard problem. The hardness of SSP varies greatly with the density of the problem. In particular, when $m$, the logarithm of the largest input number, is at least $c*n$ for some constant $c$, the problem can be solved by a reduction to finding a short vector in a lattice. On the other hand, when $m=O(log n)$ the problem can be solved in polynomial time using dynamic programming or some other algorithms especially designed for dense instances. However, as far as we are aware, all known algorithms for dense SSP take at least $\Omega(2^m)$ time, and no polynomial time algorithm is known which solves SSP when $m=\omega(log n)$ (and $m=o(n)$). We present an expected polynomial time algorithm for solving uniformly random instances of the subset sum problem over the domain $Z_M$, with $m=O((log n)2)$. To the best of our knowledge, this is the first algorithm working efficiently beyond the magnitude bound of $O(log n)$, thus narrowing the interval of hard-to-solve SSP instances. (this is joint work with Abie Flaxman) Więcej informacji: http://zaa.mimuw.edu.pl |
| 2006-05-11, godz. 12:15 - 14, s. 5580 |
| Piotr Sankowski (Uniwersytet Warszawski) |
| Szybsze dynamiczne skojarzenia i spójność wierzchołkowa |
| W ramach seminarium opowiem o pierwszych dynamicznych podkwadratowych algorytmach na obliczanie: liczby wierzchołkowo rozłącznych s,t-ścieżek, rozmiaru maksymalnego skojarzenia w grafie i skierowanej k-spójności wierzchołkowej. Prezentowane algorytmy są randomizowane z jednostronnym błędem. Algorytmy dynamiczne dla problemu rozmiaru maksymalnego skojarzenia i liczby wierzchołkowo rozłącznych ścieżek obsługuje operację zmiany w grafie w czasie O(n^1.495). Natomiast algorytm dla dynamicznej k-spójności wierzchołkowej obsługuje zmiany w czasie O(n^1.575 + nk^2). Jako rezultat uboczny otrzymujemy także dynamiczny algorytm na obliczanie rzędu macierzy obsługujący zmiany w czasie O(n^1.495). |
| 2006-03-09, godz. 12:15 - 14, s. 5870 |
| Marcin Kubica i Tomasz Waleń (Uniwersytet Warszawski) |
| O pewnych algorytmicznych problemach tekstowych |
| Tomek Waleń opowie o wspólnej pracy z P. Kolmanem. Podczas seminarium zostanie przybliżony problem porównywania sekwencji genomów. W szczególności problem obliczania odległości pomiędzy napisami liczonej w liczbie odwróceń (całych bloków), potrzebnych do przekształcenia jednego napisu w drugi (reversal distance). Przedstawiony zostanie algorytm O(k) aproksymacyjny dla problemu obliczenia odległości pomiędzy dwoma k-napisami (tzn. napisami, w których każdy znak alfabetu występuje co najwyżej k razy). Poprzedni znany algorytm ma współczynnik aproksymacji O(k^2). Marcin Kubica opowie o problemie uliniowienia wielu sekwencji (niekodującego) RNA. Problem ten jest modelowany za pomocą grafów liniowych -- sekwencjom RNA odpowiadają grafy liniowe, a problemowi uliniowienia odpowiada maksymalny zagnieżdżony podgraf liniowy (MAX-NLS). Dla ogólnych grafów liniowych problem ten jest NP-zupełny. Dotychczas znana aproksymacja tego problemu charakteryzuje się współczynnikiem O(\log^2 n) i działa w czasie O(kn^5). Przedstawimy ulepszoną wersję tej aproksymacji -- działającą w czasie O(kn^2) oraz pokażemy, że współczynnik aproksymacji jest rzędu O(\log n). Dla grafów liniowych generowanych przez sekwencje RNA pokażemy 1/4-aproksymację działającą w czasie O(kn). |
| 2006-03-02, godz. 12:15 - 14, s. 5870 |
| Wojciech Plandowski (Uniwersytet Warszawski) |
| O rozwiązywaniu równań w półgrupie wolnej |
| Na seminarium przedstawię pierwszy algorytm rozwiązujący równania w półgrupie wolnej, który działa w DEXPTIME. Prezentowane podejście pozwala na rozwiązanie w PSPACE następujących problemów: - sprawdzenia, czy zbiór rozwiązań równania jest skończony, - sprawdzenia, czy zbiór współczynników okresowości rozwiązań jest ograniczony. |
| 2006-01-26, godz. 12:15 - 14, s. 5870 |
| Anna Wojak (Uniwersytet Warszawski) |
| Wyznaczanie Euklidesowej najkrótszej drogi na płaszczyźnie pomiędzy dwoma punktami z pominięciem wielokątnych przeszkód. |
| Wyznaczanie Euklidesowej najkrótszej ścieżki jest jednym z najstarszych i dobrze znanych problemów w geometrii obliczeniowej. Obecnie istnieje wiele typów problemów związanych z wyznaczaniem najkrótszych dróg. Rozważmy płaszczyznę zawierająca zbiór rozłącznych przeszkód, których liczba wierzchołków wynosi n oraz dany punkt źródła s. Problemem jest wyznaczenie najkrótszej drogi z punktu s do wszystkich punktów wolnej przestrzeni. Znane są dwie główne metody wyznaczania najkrótszych ścieżek: visibility graph (VG) oraz shortest path map (SPM) połączone z algorytmami Dijkstra oraz A*. Shortest path map polega na specjalnym podziale płaszczyzny na obszary ukorzenione w wierzchołkach przeszkód. Obszary te są wyznaczane za pomocą rozchodzenia się czoła fali frontowej z punktu źródła s na całą płaszczyznę pośród wielokątnych przeszkód. Na początku lat dziewięćdziesiątych J.S.B. Mitchell pokazał, że wyznaczenie SPM wymaga O(n^{3/2} + \epsilon) dla \epsilon > 0. Następnie Jonh Hersberger oraz Subhash Suri zaproponowali optymalny algorytm dla SPM działający w najgorszym przypadku w czasie O(nlogn) i wymagający O(nlogn) pamięci. Kluczowym pomysłem ich algorytmu jest specjalny podział płaszczyzny zwany conforming subdividion, który może być wyznaczony w czasie O(n+nlogn). |
| 2006-01-12, godz. 12:15 - 14, s. 5870 |
| Dorota Cendrowska (Uniwersytet Warszawski) |
| Konstrukcja klasyfikatora obiektów z wykorzystaniem algorytmu badania rozdzielności liniowej dwóch zbiorów |
| W ramach seminarium zostaną poruszone kwestie dotyczące odpowiedzi na następujące pytania: Jak ludzie radzą sobie z problemem automatycznego rozdzielania liniowego dwóch zbiorów? Trop 1: Może "liniowo" to synonim "zbyt łatwo" i sprawdza się reguła garbage rule garbage out jako parafraza reguły garbage in garbage out? Trop 2: Co to w ogóle znaczy "rozdzielać zbiory liniowo"? Trop 3: Czego potrzebowalibyśmy do szczęścia, aby jednak algorytm rozdzielania liniowo dwóch zbiorów móc nazwać "użytecznym"? Czy matematyka może być lekarstwem na całe to zło? Algorytm badania liniowej rozdzielności a konstrukcja klasyfikatora — dwa podejścia Czy z tego wszystkiego jest jakiś morał? |
| 2006-01-05, godz. 12:15 - 14, s. 5870 |
| Krzysztof Onak (Uniwersytet Warszawski) |
| Testowanie własności |
| W sytuacji, gdy dysponujemy ograniczoną ilością czasu, może nie być możliwe sprawdzenie, czy dany obiekt (kombinatoryczny) posiada, pewną ustaloną własność. Tym niemniej nie jesteśmy całkowicie bezradni. Okazuje się, że w wielu przypadkach, odczytując jedynie niewielki fragment danych opisujących obiekt, możemy z dużym prawdopodobieństwem rozróżnić obiekty posiadające zadaną własność od tych, które należałoby znacznie zmodyfikować, aby tę własność posiadły. Takie podejście nazywa się zwyczajowo "testowaniem własności" (ang. property testing). Skupię się na przykładach związanych z testowaniem wymiarowości danych, ale nie zapomnę o hołubionych na Uniwersytecie Warszawskim grafach i zaprezentuję przykładowe, bardzo ogólne twierdzenia dotyczące testowania własności grafowych. Testowanie własności znajduje zastosowania w obszarach takich jak algorytmy aproksymacyjne, teoria kodów, uczenie maszynowe. Przy okazji opowiem również, jak wygląda, z krótkiej półrocznej perspektywy czasu, studiowanie na MIT, czym tam się ludzie zajmują, a także z przyjemnością odpowiem na wszelkie inne pytania. |
| 2005-12-15, godz. 12:15 - 14, s. 5870 |
| Arkadiusz Paterek (Uniwersytet Warszawski) |
| O ulepszaniu algorytmów dla gier dwuosobowych z pełną informacją |
| Na seminarium omówię własne eksperymenty związane z zastosowaniem technik uczenia z nadzorem do wyboru parametrów funkcji oceniającej w programie grającym w szachy. Opowiem również o algorytmie BPIP, obiecującej alternatywie dla algorytmu alfa-beta cięć. Jest to algorytm typu best-first search, oparty na teorii decyzji. Funkcja oceniająca w algorytmie BPIP zwraca dla liści drzewa rozkład prawdopodobieństwa. Rozkłady są propagowane do korzenia drzewa przeszukiwania, zgodnie z regułą minimaksową. Przeszukiwanie polega na rozwijaniu liści, które mają największy wpływ na oczekiwaną wypłatę. Dodatkową zaletą algorytmu BPIP jest jasne kryterium zakończenia przeszukiwania. |
| 2005-12-08, godz. 12:15 - 14, s. 5870 |
| Marcin Stefaniak (Uniwersytet Warszawski) |
| Algorytmiczne aspekty infrastruktury SilkRoute |
| SilkRoute (2002) służy do wyciągania danych z relacyjnej bazy (SQL) w postaci drzewiastej (XML) przy użyciu języka zapytań XQuery. Odbywa się to poprzez stworzenie drzewiastego planu zapytań SQL, co można zrobić na wiele sposobów. SilkRoute w celu optymalizacji planu zapytań używa heurystycznych szacunków oraz zachłannego algorytmu, co przynosi zadowalające praktycznie rezultaty. Interesujące, czy można dla tej z życia wziętej sytuacji stworzyć pewien (uproszczony) model matematyczny, tak aby ów problem algorytmiczny dał się ładnie zanalizować. |
| 2005-11-17, godz. 12:15 - 14, s. 5870 |
| Anna Urbańska (Uniwersytet Warszawski) |
| Kombinatoryczny algorytm obliczania wyznacznika |
| Tematem referatu jest kombinatoryczna charakteryzacja wyznacznika, dająca prosty i całkowicie kombinatoryczny algorytm na jego obliczanie, działający w czasie O(n^4). Algorytm ten nie wymaga dzielenia i pracuje nad dowolnym pierścieniem przemiennym. Postaram się również pokazać, jak wykorzystując algorytm szybkiego mnożenia macierzy poprawić złożoność czasową tego algorytmu. Na koniec opowiem jak w analogiczny sposób można scharakteryzować wszystkie pozostałe współczynniki wielomianu charakterystycznego oraz Pfaffian dowolnej macierzy skośno-symetrycznej oraz podam kombinatoryczne dowody poprawności znanych algorytmów obliczania wyznacznika (Chistova, Csanky'ego oraz Samuelsona). |
| 2005-11-10, godz. 12:15 - 14, s. 5870 |
| Krzysztof Ciebiera (Uniwersytet Warszawski) |
| Poświadczone struktury danych |
| Zagadnienia: 1. Co to są poświadczone struktury danych? 2. Tradycyjne metody tworzenia poświadczonych słowników. 3. ''Skip-lists'' - metoda implementacji poświadczonych słowników. 4. Inne znane zastosowania poświadczonych struktur danych (w geometrii i algorytmach grafowych). |
| 2005-10-27, godz. 12:15 - 14, s. 5870 |
| Piotr Sankowski (Uniwersytet Warszawski) |
| Obliczanie odległości w grafie przy użyciu mnożenia macierzy |
| Tematem seminarium jest obliczanie odległości w grafie z wykorzystaniem mnożenia macierzy. Rozpocznę od przedstawienia tegorocznych wyników pokazujących w jaki sposób bliczyć odległości z zadanego wierzchołka w grafie dla całkowitoliczbowych wag krawędzi w takim samym czasie jak mnożenie macierzy rozmiaru n na n. Wynik ten został jednoczesnie przedstawony w pracach ,,Answering distance queries in directed graphs using fast matrix multiplication'' Raphael Yuster i Uri Zwick (FOCS'05) oraz ,,Shortest Paths in Matrix Multiplication Time'' Piotr Sankowski (ESA'05). Druga część seminarium będzie poświęcona obliczaniu odległości między wszystkimi parami wierzchołków w grafie. Skoncentruję się na przestawieniu wyników zawartych w pracy ,,All Pairs Shortest Paths in weighted directed graphs'' Uri Zwick (FOCS'98). |
| 2005-10-20, godz. 12:15 - 14, s. 5870 |
| Marcin Peczarski (Uniwersytet Warszawski) |
| Komputerowo wspomagane badanie własności porządków częściowych |
| Własności, o których będę mówił, związane są z sortowaniem za pomocą porównań. Sortowanie porządku częściowego polega na znalezieniu jednego z jego rozszerzeń liniowych. Sortowanie możemy sobie wyobrazić jako grę. W każdym ruchu my wybieramy parę elementów do porównania, a przeciwnik wskazuje nam kolejność tych elementów. Wskazane porównanie dzieli możliwy zbiór rozszerzeń liniowych na dwa rozłączne podzbiory. Czyli gra polega na tym, że w każdym kroku my wybieramy podział zbioru rozszerzeń liniowych, a przeciwnik wskazuje ten podzbiór, który zawiera poszukiwane rozszerzenie liniowe. Gra kończy się, gdy pozostanie zbiór jednoelementowy. Omówię trzy problemy badawcze, którymi się zajmuję. 1. Hipoteza o złotym podziale Sformułuję hipotezę o złotym podziale porządku częściowego. Prawdziwość tej hipotezy implikuje prawdziwość bardzo znanej hipotezy 1/3--2/3 oraz ciasną górną granicę dla sortowania porządków częściowych. Przedstawię wybrane wyniki badań, w tym moje, nad dowodami powyższych hipotez. 2. Najgorzej zbalansowane porządki - drabiny z powyłamywanymi szczeblami Dość naturalną, choć nie zawsze optymalną, strategią sortowania porządku częściowego jest wskazywanie podziału zbioru jego rozszerzeń liniowych na możliwie równoliczne podzbiory. Złośliwy przeciwnik, starając się utrudnić nam zadanie, będzie wybierał podzbiór o większej mocy. Współczynnik zbalansowania porządku częściowego określa, jak bliski idealnemu (na równoliczne podzbiory) podział możemy wskazać. Zatem istotne jest pytanie, jak źle może być zbalansowany porządek częściowy. Brightwell [1999] wskazał znane mu najgorzej zbalansowane porządki częściowe. Przedstawię, znalezioną za pomocą komputera, nieskończoną klasę gorzej zbalansowanych porządków częściowych. 3. Sortowanie z minimalną liczbą porównań Interesuje nas minimalna liczba porównań, zawsze wystarczająca do posortowania n elementów. Wiadomo, że dla n < 12 i n = 20, 21 minimum to realizuje algorytm Forda-Johnsona. Algorytm ten jest również optymalny dla n = 12 [Wells 1969] oraz n = 13, 14, 15, 22 [Peczarski 2002,2004]. Najmniejszą liczbą elementów, dla której znamy algorytm lepszy od algorytmu Forda-Jonhnsona, jest n = 47 [Moenting 1981]. Przedstawię aktualny stan moich poszukiwań najmniejszego n, dla którego algorytm Forda-Johnsona nie jest optymalny. |
| 2005-10-13, godz. 12:15 - 14, s. 5870 |
| Mirosław Kowaluk (Uniwersytet Warszawski) |
| Problem najbliższego wspólnego przodka w grafach acyklicznych |
| Najbliższym wspólnym przodkiem dwóch wierzchołków u,v grafu acyklicznego jest wierzchołek będący wspólnym przodkiem wierzchołków u, v i nie będęcy przodkiem żadnego innego wspólnego przodka tych wierzchołków. Wybór najbliższego wspólnego przodka nie musi być jednoznaczny. W problemie najbliższego przodka w grafie acyklicznym pragniemy możliwie szybko odpowiadać na pytanie, który z wierzchołków grafu jest najbliższym wspólnym przodkiem dwóch dowolnie wybranych wierzchołków tego grafu. W tym celu stosujemy preprocessing umożliwiający odpowiedź na to pytanie w czasie stałym. Dotychczas najlepszy algorytm wykonywał preprocessing w czasie O(n^{(\omega+3)/2}, gdzie \omega=2,376. Z Andrzejem Lingasem poprawiliśmy nieco ten wynik do O(n^{2+(1/(4-\omega))}. |
| 2005-10-06, godz. 12:15 - 14, s. 5870 |
| Łukasz Kowalik (Uniwersytet Warszawski) |
| Listowe kolorowanie krawędziowe grafów i aproksymacja lesistości grafu |
| Postaram się krótko przedstawić problem listowego kolorowania krawędziowego grafów oraz opowiedzieć o znanych wynikach w tej dziedzinie. Szczególnie uważnie będę się przyglądał grafom planarnym. Z listowym kolorowaniem krawędziowym grafów ogólnych i planarnych wiąże się kilka bardzo ciekawych problemów otwartych -- przede wszystkim teoriografowych, ale również algorytmicznych. Lesistość (ang. arboricity) grafu to najczęściej stosowana miara rzadkości/gęstości grafu. Problem mierzenia lesistości jest wielomianowy, ale najlepsze znane algorytmy opieraja sie metodach przeplywowych i mają złożoność rzedu O~(m^3/2). Jeśli starczy czasu drugą część seminarium poświęcę na zreferowanie efektywnych algorytmow aproksymacyjnych dla problemu mierzenia lesistosci oraz pokrewnego problemu znajdowania optymalnej orientacji grafu. Tu takze opisze kilka otwartych problemów (myślę że dużo prostszych niż te związane z kolorowaniem listowym). |
| 2004-11-25, godz. 12:15 - 14, s. 5870 |
| Krzysztof Diks (Uniwersytet Warszawski) |
| O dwóch ciekawych problemach grafowych |
| Opowiemy o dwóch znanych problemach grafowych postawionych ogólniej niż się to robi klasycznie. Przedstawimy ugólnione twierdzenie Vizinga o kolorowaniu krawędzi multigrafu i pokażemy, w jaki sposób znajdować cykle Eulera w grafach mieszanych, tzn. takich, w których mogą się pojawiać zarówno krawędzie skierowane, jak i nieskierowane. W naszych rozważaniach skoncentrujemy się na algorytmicznych aspektach omawianych zagadnień. |
| 2004-11-18, godz. 12:15 - 14, s. 5870 |
| Arkadiusz Paterek (Uniwersytet Warszawski) |
| Modelowanie funkcji oceniającej w grach |
| W programach grających w gry dwuosobowe, opartych na algorytmach typu minimax, stosuje się często funkcję oceniającą w postaci kombinacji liniowej wybranych numerycznych własności pozycji. Dysponując wystarczająco dużym zbiorem pozycji z oceną ustaloną przez wyrocznię, można ustalić współczynniki funkcji, minimalizując jej błąd dla ocenionych pozycji. Na seminarium opowiem o eksperymencie z mojej pracy magisterskiej, polegającym na ustaleniu parametrów funkcji oceniającej w programie szachowym, przy użyciu metody najszybszego spadku. |
| 2004-11-04, godz. 12:15 - 14, s. 5870 |
| Łukasz Kowalik (Uniwersytet Warszawski) |
| Kolorowanie krawędziowe grafów planarnych |
| W problemie kolorowania krawędziowego grafu należy krawędziom grafu przypisać kolory tak, aby incydentne krawędzie otrzymały różne kolory. Rozważa się bardzo naturalne uogólnienie tego problemu: listowe kolorowanie krawędziowe. W tej wersji każda krawędź ma przypisaną listę dozwolonych kolorów. Na seminarium opowiem o algorytmach kolorowania krawędziowego i listowego kolorowania krawędziowego grafów planarnych. Będą nas interesowały wyłącznie liniowe algorytmy i optymalne kolorowanie -- używające możliwie małej liczby kolorów lub działające dla możliwie krótkich list. Opowiem o nowych wynikach w tej dziedzinie, uzyskanych we współpracy z Richardem Cole. |
| 2004-10-28, godz. 12:15 - 14, s. 5870 |
| Piotr Sankowski (Uniwersytet Warszawski) |
| Od macierzy odwrotnoścci do dynamicznych najkrótszych ścieżek |
| W trakcie seminarium przedstawię najważniejsze elementy konstrukcji algorytmów dla dynamicznego liczenia macierzy odwrotnej oraz ich zastosowanie do liczenia dynamicznego domknięcia przechodniego. Konstrukcja ta daje asymptotyczne najszybsze znane algorytmy dla tego problemu. W drugiej części seminarium opowiem o rozszerzeniach przedstawionych metod dla obliczeń nad pierścieniami. Rozszerzenie to umożliwi konstrukcję efektywnych dynamicznych algorytmów na obliczanie długości najkrótszych ścieżek w grafie. |
| 2004-10-21, godz. 12:15 - 14, s. 5870 |
| Katarzyna Paluch (Instytut Informatyki, Uniwersytet Wrocławski) |
| Aproksymacyjne algorytmy pokrywania tablic liczbowych prostokątami |
| Przedstawione zostaną główne wyniki rozprawy doktorskiej prelegentki: dwa algorytmy aproksymacyjne dla problemu ,,Rectangle Tiling", pierwszy o współczynniku aproksymacji 9/4 i drugi o współczynniku aproksymacji 17/8. |
| 2004-10-14, godz. 12:15 - 14, s. 5870 |
| Ł. Kowalik, M. Mucha, P. Sankowski (Uniwersytet Warszawski) |
| European Symposium on Algorithms 2004 |
| Przegląd najważniejszych prac prezentowanych podczas konferencji European Symposium on Algorithms 2004, która miała miejsce we wrześniu, w Bergen, Norwegia. |