Seminar Algorithms

Organizers

• dr hab. Marcin Pilipczuk, prof. UW

Information

Home page

List of talks

• May 23, 2019, 12:15 p.m.
  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 …

  ---

• Feb. 21, 2019, 12:15 p.m.
  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 …

  ---

• Jan. 24, 2019, 12:15 p.m.
  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 …

  ---

• Jan. 17, 2019, 12:15 p.m.
  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 …

  ---

• Nov. 29, 2018, 12:15 p.m.
  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 …

  ---

• Oct. 25, 2018, 12:15 p.m.
  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 …

  ---

• Oct. 11, 2018, 12:15 p.m.
  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) …

  ---

• July 19, 2018, 12:15 p.m.
  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 …

  ---

• June 11, 2018, 12:15 p.m.
  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 …

  ---

• April 19, 2018, 12:15 p.m.
  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 …

  ---

• April 5, 2018, 12:15 p.m.
  Wiktor Zuba (MIMUW)
  Hamilitonian cycles of middle-levels subgraphs of hypercubes
  The n-dimension hypercube graph is the graph with vertices represented by sequences of n bits, with edges connecting those vertices, which representations differ at exactly one position. We can divide the graph into (n+1) levels, …

  ---

• March 15, 2018, 12:15 p.m.
  Marthe Bonamy (LaBRI, CNRS, Universite de Bordeaux)
  Distributed coloring in sparse graphs with fewer colors
  Distributed coloring in sparse graphs with fewer colors Abstract : We are concerned with efficiently coloring sparse graphs in the distributed setting with as few colors as possible. According to the celebrated Four Color Theorem, …

  ---

• March 8, 2018, 12:15 p.m.
  Magnus Wahlström (University of London)
  Fine-grained structure of NP-hard SAT problems
  Say that a problem SAT(\Gamma), for a constraint language \Gamma, admits an improved algorithm if it can be solved in O(c^n) time on n variables for some c<2, and that it is hard otherwise. Many …

  ---

• March 1, 2018, 12:15 p.m.
  Marc Heinrich (LIRIS )
  Online graph coloring with bichromatic exchanges
  Greedy algorithms for the graph coloring problem require a large number of colors, even for very simple classes of graphs. For example, any greedy algorithm coloring trees requires $\Omega(\log n)$ colors in the worst case. …

  ---

• Feb. 8, 2018, 12:15 p.m.
  Lucas Pastor
  Disproving the normal graph conjecture
  A graph G is said to be normal if there exists two coverings, C and S of its vertex set such that, every member of C induces a clique, every member of S induces a …

  ---