Organizatorzy

dr hab. Michał Pilipczuk, prof. ucz.

Informacje

piątki, 14:15 , sala: 5060

Strona domowa

https://semalgo.wordpress.com/

Lista referatów

18 marca 2021 12:15
Anna Zych-Pawlewicz
Efficient fully dynamic elimination forests with applications to detecting long paths and cycles
We present a data structure that in a dynamic graph of treedepth at most d, which is modified over time by edge insertions and deletions, maintains an optimum-height elimination forest. The data structure achieves worst-case …
4 marca 2021 12:15
Łukasz Bożyk
Vertex deletion into bipartite permutation graphs
A permutation graph can be defined as an intersection graph of segments whose endpoints lie on two parallel lines, one on each. A bipartite permutation graph is a permutation graph which is bipartite. We study …
21 stycznia 2021 12:15
Karol Węgrzycki (MPI Saarbrucken)
Improving Schroeppel and Shamir’s Algorithm for Subset Sum via Orthogonal Vectors
We present an O^*(2^{0.5 n}) time and O^*(2^{0.249999n}) space randomized algorithm for Subset Sum. This is the first improvement over the long-standing O^*(2^{n/2}) time and O^*(2^{n /4}) space algorithm due to Schroeppel and Shamir. This …
7 stycznia 2021 12:15
Michał Włodarczyk (Eindhoven University of Technology)
Parameterized Inapproximability for Steiner Orientation by Gap Amplification
In the k\textnormal{-}\textsc{Steiner Orientation} problem, we are given a mixed graph, that is, with both directed and undirected edges, and a set of k terminal pairs. The goal is to find an orientation of the …
17 grudnia 2020 12:15
Juliusz Straszyński
Efficient Computation of 2-Covers of a String
Quasiperiodicity is a generalization of periodicity that has been researched for almost 30 years. The notion of cover is the classic variant of quasiperiodicity. A cover of a text T is a string whose occurrences …
3 grudnia 2020 12:15
Adam Karczmarz (UW)
A Deterministic Parallel APSP Algorithm and its Applications
In this talk we show a deterministic parallel all-pairs shortest paths algorithm for real-weighted directed graphs. The algorithm has $\tilde{O}(nm+(n/d)3)$ work and $\tilde{O}(d)$ depth for any depth parameter $d\in [1,n]$. To the best of our …
19 listopada 2020 12:15
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, …
5 listopada 2020 12:15
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 …
22 października 2020 12:15
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 …
8 października 2020 12:15
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 …
4 czerwca 2020 12:15
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 …
26 marca 2020 12:15
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 …
16 stycznia 2020 12:15
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 …
9 stycznia 2020 12:15
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 …
19 grudnia 2019 12:15
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 …