Lista referatów

• 2011-04-21, godz. 12:15, 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 programmin...

• 2011-04-14, godz. 12:15, 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 a...

• 2011-04-07, godz. 12:15, 5870

  (Uniwersytet Warszawski)

  Brak seminarium z powodu FIT, OI

• 2011-03-31, godz. 12:15, 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, 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, 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))). Joint work with Robin A. Moser....

• 2011-03-17, godz. 12:15, 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, 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 rundz...

• 2011-03-03, godz. 12:15, 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...

• 2011-02-24, godz. 12:15, 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 th...

Strony