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

Rules for PhD studens:

Google calendar:

YouTube cannel:

Lista referatów

  • 2019-05-23, godz. 12:15, 5870

    Piotr Skowron (University of Warsaw)

    Fairness and Public Goods: the Case of Multiwinner Rules

    An instance of a multiwinner election consists of a set of alternatives, a population of voters---each voter approves a subset of alternatives, and the desired committee size k; the goal is to select a committee (a subset) of k alternatives according to the preferences (approvals) of the voters. Wha...

  • 2019-02-21, godz. 12:15, 5870

    Laszlo Kozma (Freie Universität Berlin)

    Selection from heaps, row-sorted matrices, and X+Y, using soft heaps

    We use soft heaps to obtain simpler optimal algorithms for selecting the k-th smallest item from a heap-ordered tree, from a collection of sorted lists, and from X+Y. Our results match, and in some ways extend classical results of Frederickson (1993) and Frederickson and Johnson ...

  • 2019-01-24, godz. 12:15, 5870

    Karolina Okrasa (Politechnika Warszawska)

    Subexponential algorithms for locally constrained homomorphism problems in string graphs

    We consider the complexity of finding weighted homomorphisms from string graphs with n vertices to a fixed graph H. We show that there exists an algorithm solving this problem in subexponential time, if H has no two vertices sharing two common neighbors. Otherwise there is no alg...

  • 2019-01-17, godz. 12:15, 5870

    Adrian Vladu (Boston University)

    Discrepancy and Optimization

    We consider the problem of minimizing the discrepancy of a set system. In 1985, Spencer proved that for m sets over a universe of n elements, one can always achieve a coloring with discrepancy O(sqrt(n log (m/n))), thus beating what could be achieved by a standard application of the Chernoff plus un...

  • 2018-11-29, godz. 12:15, 5870

    Krszysztof Fleszar (Univerisity of Warsaw)

    A PTAS for TSP with hyperplane neighborhoods

    A PTAS for TSP with hyperplane neighborhoods In TSP with neighborhoods, we are asked for a shortest tour visiting a given set of regions (i.e., neighborhoods). When the neighborhoods are lines in 2D, the problem is efficiently solvable. The problem becomes NP-hard for lines in 3D. What ...

  • 2018-10-25, godz. 12:15, 5870

    Stéphan Thomassé (ENS Lyon)

    EPTAS for Max Clique on Disks and Unit Balls

    We propose a polynomial-time algorithm which takes as input a finite set of points of R3 and computes, up to arbitrary precision, a maximum subset with diameter at most 1. More precisely, we give the first randomized EPTAS and deterministic PTAS for MAXIMUM CLIQUE in unit ball graphs. Our approximat...

  • 2018-10-11, godz. 12:15, 5870

    Paweł Rzążewski (MIMI PW)

    Finding list homomorphisms from bounded-treewidth graphs to reflexive graphs: a complete complexity characterization

    In the list homomorphism problem, the input consists of two graphs G and H, together with a list L(v) \subseteq V(H) for every vertex v\in V(G). The task is to find a homomorphism \phi:V(G)\to V(H) respecting the lists, that is, we have that  \phi(v)\in L(v) for every v\in V(H) and if u ...

  • 2018-07-19, godz. 12:15, 5870

    Jan van der Brand (KTH)

    Improved Algorithms for Dynamic Matrix Inverse

    The dynamic matrix inverse problem is to maintain the inverse of a matrix undergoing element and column updates. It is the main subroutine behind the best algorithms for many dynamic problems, such as maintaining the largest eigenvalue, rank and determinant of a matrix and maintaining reachabi...

  • 2018-06-11, godz. 12:15, 5870

    Krzysztof Kiljan, Wojciech Nadara, Michał Ziobro

    Three talks from Symposium on Experimental Algorithms (SEA'18)

    Krzysztof Kiljan, Experimental Evaluation of Parameterized Algorithms for Feedback Vertex Set   Feedback Vertex Set is a classic combinatorial optimization problem that asks for a minimum set of vertices in a given graph whose deletion makes the graph acyclic. From the point of ...

  • 2018-04-19, godz. 12:15, 5870

    Laszlo Kozma (TU Eindhoven)

    Trees and heaps: the many faces of basic data structures

    Binary search trees (BSTs) and heaps are the canonical comparison-based implementations of the dictionary and the priority queue data types. They are among the most extensively studied structures in computer science, yet, many basic questions about them remain open. What is the best strategy ...