Seminar Algorithms

Organizers

• dr hab. Michał Pilipczuk, prof. UW

Information

Home page

List of talks

• Nov. 19, 2020, 12:15 p.m.
  Céline M. F. Swennenhuis (Eindhoven University of Technology)
  A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics
  In the Bin Packing problem one is given n items with different weights and m bins with a given capacity; the goal is to distribute the items over the bins without exceeding the capacity. Björklund, …

  ---

• Nov. 5, 2020, 12:15 p.m.
  Wojciech Nadara
  Approximating pathwidth for graphs of small treewidth
  We describe a polynomial-time algorithm which, given a graph $G$ with treewidth $t$, approximates the pathwidth of $G$ to within a ratio of $O(t\sqrt{\log t})$. Our approach builds on the following key insight: every graph …

  ---

• Oct. 22, 2020, 12:15 p.m.
  Marcin Pilipczuk
  Quasi-polynomial-time algorithm for Independent Set in P_t-free and C_{>t}-free graphs via shrinking the space of connecting subgraphs
  In a recent breakthrough work, Gartland and Lokshtanov [FOCS 2020] showed a quasi-polynomial-time algorithm for Maximum Weight Independent Set in P_t-free graphs, that is, graphs excluding a fixed path as an induced subgraph. Their algorithm …

  ---

• Oct. 8, 2020, 12:15 p.m.
  Wiktor Zuba
  The number of repetitions in 2D-strings
  The notions of periodicity and repetitions in strings, and hence these of runs and squares, naturally extend to two-dimensional strings. We consider two types of repetitions in 2D-strings: 2D-runs and quartics (quartics are a 2D-version …

  ---

• June 4, 2020, 12:15 p.m.
  Kunal Dutta (University of Warsaw)
  Dimensionality Reduction for k-distance Applied to Persistent Homology
  Given a set P of n points and a constant k, we are interested in computing the persistent homology of the Čech filtration of P for the k-distance, and investigate the effectiveness of dimensionality reduction …

  ---

• March 26, 2020, 12:15 p.m.
  Michał Pilipczuk (University of Warsaw)
  Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs
  This Thursday we will have our first virtual algorithms seminar! Please join us at https://us04web.zoom.us/j/967084831 (Meeting ID: 967 084 831). In the Maximum Independent Set problem we are asked to find a set of pairwise …

  ---

• Jan. 16, 2020, 12:15 p.m.
  Kunal Dutta (MIM UW)
  Randomized Incremental Construction of Delaunay Triangulations of Nice Point Sets
  Randomized incremental construction (RIC) is one of the most important paradigms for building geometric data structures. Clarkson and Shor developed a general theory that led to numerous algorithms that are both simple and efficient in …

  ---

• Jan. 9, 2020, 12:15 p.m.
  Panagiotis Charalampopoulos (King's College London and University of Warsaw)
  Almost Optimal Distance Oracles for Planar Graphs
  We present new tradeoffs between space and query-time for exact distance oracles in directed weighted planar graphs. These tradeoffs are almost optimal in the sense that they are within polylogarithmic, subpolynomial or arbitrarily small polynomial factors …

  ---

• Dec. 19, 2019, 12:15 p.m.
  Jakub Łącki (Google Research NY)
  Massively parallel algorithms for finding connected components
  In this talk we consider the problem of finding connected components in a distributed setting. We present state of the art algorithms that achieve near-optimal round complexity and work well in practice. Our main focus …

  ---

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

  ---