You are not logged in |
Research seminar (Fridays, at 14.15 in room 5060)
For schedule or link to online meetings, see https://semalgo.wordpress.com/
If you want to get notifications, sign up to the mailing list algorytmy@mimuw.edu.pl
Rules for PhD studens: https://www.mimuw.edu.pl/~mp248287/algorithmsSeminarRules.pdf
Google calendar: https://calendar.google.com/calendar/embed?src=q1pbv62cra5jf9satch9ip49ms%40group.calendar.google.com&ctz=Europe%2FWarsaw
YouTube channel: https://www.youtube.com/playlist?list=PLzdZSKerwrXpfAgaKQpsH8ElCik3pINPp
Organizers
- dr hab. Michał Pilipczuk, prof. UW
Information
Fridays, 2:15 p.m. , room: 5060Home page
https://semalgo.wordpress.com/List of talks
-
March 31, 2011, 12:15 p.m.
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))). Joint work with …
-
March 31, 2011, 12:15 p.m.
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 …
-
March 17, 2011, 12:15 p.m.
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.
-
March 10, 2011, 12:15 p.m.
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 …
-
March 3, 2011, 12:15 p.m.
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 …
-
Feb. 24, 2011, 12:15 p.m.
Konstanty Junosza-Szaniawski (Politechnika Warszawska)
2,1)-labeling of graph (Exact algorithms for L)
$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 …
-
Feb. 17, 2011, 12:15 p.m.
dr hab Jerzy Tyszkiewicz (Uniwersytet Warszawski)
Almost) the Sam (Parallel Random Access Machines and Spreadsheets are)
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 …
-
Jan. 20, 2011, 12:15 p.m.
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 …
-
-
Dec. 16, 2010, 12:15 p.m.
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 …
-
Dec. 9, 2010, 12:15 p.m.
Ł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 …
-
-
Nov. 25, 2010, 12:15 p.m.
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 …
-
Nov. 4, 2010, 12:15 p.m.
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 …
-
Oct. 21, 2010, 12:15 p.m.
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 …
