Organizatorzy

dr hab. Michał Pilipczuk, prof. ucz.

Informacje

piątki, 14:15 , sala: 5060

Strona domowa

https://semalgo.wordpress.com/

Lista referatów

12 maja 2011 12:15
Jakub Łącki (Uniwersytet Warszawski)
Min-cuts and Shortest Cycles in Planar Graphs in O (n log log n) Tim)
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 …
5 maja 2011 12:15
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 …
21 kwietnia 2011 12:15
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 …
14 kwietnia 2011 12:15
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. …
7 kwietnia 2011 12:15
- (Uniwersytet Warszawski)
Brak seminarium z powodu FIT, OI
31 marca 2011 12:15
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 …
31 marca 2011 12:15
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 …
31 marca 2011 12:15
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 …
17 marca 2011 12:15
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.
10 marca 2011 12:15
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 …
3 marca 2011 12:15
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 …
24 lutego 2011 12:15
Konstanty Junosza-Szaniawski (Politechnika Warszawska)
Exact algorithms for L (2,1)-labeling of graph)
$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 …
17 lutego 2011 12:15
dr hab Jerzy Tyszkiewicz (Uniwersytet Warszawski)
Parallel Random Access Machines and Spreadsheets are (Almost) the Sam)
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 …
20 stycznia 2011 12:15
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 …
13 stycznia 2011 12:15
- (Uniwersytet Warszawski)
Seminarium odwołane