Nie jesteś zalogowany | zaloguj się

Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego

  • Skala szarości
  • Wysoki kontrast
  • Negatyw
  • Podkreślenie linków
  • Reset

Seminarium "Algorytmika"

Research seminar (FRIDAYS, usually biweekly at 14.15 in room 5060 or online)

For schedule or link to online meetings, see https://semalgo.wordpress.com/

If you want  to get notifications of the talks 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=q1pbv62cra5jf9satch9ip49m...

YouTube cannel: https://www.youtube.com/playlist?list=PLzdZSKerwrXpfAgaKQpsH8ElCik3pINPp


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