You are not logged in |
Research seminar (Fridays, at 14.15 in room 5060)
For schedule or link to online meetings, see https://semalgo.wordpress.com/
If you want to get notifications, 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=q1pbv62cra5jf9satch9ip49ms%40group.calendar.google.com&ctz=Europe%2FWarsaw
YouTube channel: https://www.youtube.com/playlist?list=PLzdZSKerwrXpfAgaKQpsH8ElCik3pINPp
Organizers
- dr hab. Michał Pilipczuk, prof. ucz.
Information
Fridays, 2:15 p.m. , room: 5060Home page
https://semalgo.wordpress.com/List of talks
-
Dec. 12, 2019, 12:15 p.m.
Erik Jan van Leeuwen (Utrecht University)
On Geometric Set Cover for Orthants
We study Set Cover for orthants: Given a set of points in a d-dimensional Euclidean space and a set of orthants of the form (-infty,p_1] x ... x (-infty,p_d], select a minimum number of orthants …
-
Nov. 28, 2019, 12:15 p.m.
Petteri Kaski (Department of Computer Science, Aalto University)
Probabilistic tensors and opportunistic Boolean matrix multiplication
We introduce probabilistic extensions of classical deterministic measures of algebraic complexity of a tensor, such as the rank and the border rank. We show that these probabilistic extensions satisfy various natural and algorithmically serendipitous properties, …
-
Nov. 14, 2019, 12:15 p.m.
Piotr Sankowski (University of Warsaw)
Walking Randomly, Massively, and Efficiently
We introduce an approach that allows for efficiently generating many independent random walks in big graph models, such as the Massive Parallel Computation (MPC) model. We consider the case where the space per machine is …
-
Nov. 7, 2019, 12:15 p.m.
Marcin Pilipczuk (University of Warsaw)
A Polynomial-Time Approximation Scheme for Facility Location on Planar Graphs
We consider the classic Facility Location problem on planar graphs (non-uniform, uncapacitated). Given an edge-weighted planar graph $G$, a set of clients $C\subseteq V(G)$, a set of facilities $F \subseteq V(G)$, and opening costs $w …
-
Oct. 31, 2019, 12:15 p.m.
François Dross (University of Warsaw)
Trees in tournaments
A tournament is an orientation of a complete graph. A digraph is n-unavoidable if it is contained (as a subdigraph) in every tournament of order n. The unavoidability of a digraph D is the minimum …
-
Oct. 24, 2019, 1 p.m.
Solon Pissis (CWI)
Even Faster Elastic-Degenerate String Matching via Fast Matrix Multiplication
An elastic-degenerate (ED) string is a sequence of n sets of strings of total length N, which was recently proposed to model a set of similar sequences. The ED string matching (EDSM) problem is to …
-
Oct. 24, 2019, 12:15 p.m.
Krzysztof Nowicki (UWr)
Faster Algorithms for Edge Connectivity via Random 2-Out Contractions
We provide a simple new randomized contraction approach to the global minimum cut problem for simple undirected graphs. The contractions exploit 2-out edge sampling from each vertex rather than the standard uniform edge sampling. We …
-
Oct. 17, 2019, 12:15 p.m.
Stéphane Bessy (LIRMM Montpellier)
Triangle and cycle packing in tournaments: complexity and algorithms
Given a tournament T and a positive integer k, we study different question dealing with packing (oriented) cycles in tournament: does T contain k vertex-disjoint cycles (k-VCT)? k arc-disjoint cycles (k-ACT)? k-arc-disjoint triangles (k-ATT)?, where …
-
Oct. 10, 2019, 12:15 p.m.
Edouard Bonnet (ENS Lyon)
Parameterized Complexity of Grundy Coloring and its variants
(Connected/Partial/Weak) Grundy Coloring, b-Coloring, b-Chromatic Core, etc. are maximization coloring problems, where one asks for the worst case of a first-fit coloring strategy. They were introduced to analyze if some coloring heuristics have performance guarantee. …
-
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 …
