Czekaj...Wczytywanie... Nie jesteś zalogowany | zaloguj się

## Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego

• Skala szarości
• Wysoki kontrast
• Negatyw
• Podkreślenie linków
• Reset

# Seminarium "Algorytmika"

Research seminar (FRIDAYS, usually biweekly at 14.15 in room 5060 or online)

For schedule or link to online meetings, see https://semalgo.wordpress.com/

Rules for PhD studens: https://www.mimuw.edu.pl/~mp248287/algorithmsSeminarRules.pdf

5060

## Strona domowa

https://semalgo.wordpress.com/

## Lista referatów

• 2021-04-29, godz. 12:15, online

Jana Cslovjecsek (EPFL)

Block-Structured Integer and Linear Programming in Strongly Polynomial and Near Linear Time

We consider n-fold integer programming problems and their generalizations. These are integer linear programming problems for which the linear constraints exhibit a (recursive) block-structure: The problem decomposes into independent sub-problems after deleting a small number of constraints. ...

• 2021-04-15, godz. 12:15, online

Tomáš Masařík (Simon Fraser University)

Flexible List Colorings in Graphs with Special Degeneracy Conditions

For a given ε > 0, we say that a graph G is ε-flexibly k-choosable if the following holds: for any assignment L of lists of size k on V(G), if a preferred color is requested at any set R of vertices, then at least ε |R| of these requests are satisfied by some L-coloring. W...

• 2021-04-01, godz. 12:15, online

Michał Pilipczuk

Reducing randomness in Isolation Lemma on decomposable graphs

The classic Isolation Lemma of Mulmuley et al. states that if F is a non-empty family of subsets of a universe U of size n, and we draw a weight function f : U -> {1,...,2n} uniformly at random, then with probability at least 1/2 there is a unique element of F that has the minimum weight ...

• 2021-03-18, godz. 12:15, online

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 update time O(2^{d^2}), which matches the best known parameter dependenc...

• 2021-03-04, godz. 12:15, online (link on the seminar website)

Ł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 the parameterized complexity of the bipartite permutation vertex deletion problem, whic...

• 2021-01-21, godz. 12:15, online

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 talk will also feature an introduction to the representative...

• 2021-01-07, godz. 12:15, online

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 undirected edges that maximizes the number of terminal pairs for which there is a path...

• 2020-12-17, godz. 12:15, online

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 in T cover all positions of T.   There are several algorithms computing ...

• 2020-12-03, godz. 12:15, online

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 knowledge, such a trade-off has only been previously des...

• 2020-11-19, godz. 12:15, online (link in the calendar and sent to the mailing list)

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, Husfeldt and Koivisto (SICOMP 2009) presented an O(2^n) time algorithm for Bin Packing. ...