Seminar Algorithms

Organizers

• dr hab. Michał Pilipczuk, prof. ucz.

Information

Home page

Research fields

• Algorithmics

List of talks

• June 19, 2019, 12:15 p.m.
  Karol Węgrzycki (MIMUW)
  Recent Progress on Approximate APSP
  In this talk we prove the equivalence of computing the approximate (min,+)-product of two $n \times n$ matrices with arbitrary values and (min,max)-product. This yields a first subcubic strongly polynomial approximation for the all-pairs shortest …

  ---

• June 13, 2019, 12:15 p.m.
  Anita Liebenau (University of New South Wales)
  Enumerating graphs and other discrete structures by degree sequence
  How many d-regular graphs are there on n vertices? What is the probability that G(n,p) has a specific given degree sequence, where G(n,p) is the homogeneous random graph in which every edge is inserted with …

  ---

• May 30, 2019, 12:15 p.m.
  Anish Mukherjee (Chennai Mathematical Institute, India)
  Solving connectivity problems via basic Linear Algebra
  We consider some classical graph connectivity problems like reachability, shortest path and disjoint paths in different settings. For the first two problems, we show efficient parallel algorithms in the dynamic framework, confirming a conjecture of …

  ---

• 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, …

  ---