czwartek, 14:15 - 16:00, sala 0174

Classical, approximation and on-line algorithms, computational complexity, lower bound results, etc.

Poprzednie referaty

16.03.2017 14:15
Jakub Cisło, Grzegorz Jurdziński
Tight Hardness Results for LCS and other Sequence Similarity Measures
09.03.2017 14:00
Sylwester Klocek, Wojciech Kruk
The Alternating Stock Size Problem and the Gasoline Puzzle
05.01.2017 14:15
Jan Derbisz, Jakub Łabaj
How to sort by walking on a tree

We consider a tree with n vertices. On vertex number x there is a box with label p(x), with the function p being a permutation of {1,2,...,n}. A robot is walking on the tree, carrying at most one box at a time. If a box is placed where robot is standing, it can swap this box with the one being carried. The robot's goal is to sort the boxes, placing each one at the vertex with its number. The paper by D. Graf gives an algorithm computing the shortest possible robot's walk in quadratic time, as well as the proof that the problem becomes NP-complete if planar graphs are considered instead of trees.

15.12.2016 14:15
Michał Glapa, Franciszek Stokowacki
Maximum matching with algebraic methods

In 2006, a celebrated result by Mucha and Sankowski stated that the maximum matching problem can be done by Gaussian elimination. The complexity of this algorithm depends on matrix multiplication, but certainly beats O(n2.5) long-standing record of Micali-Vazirani algorithm.

Lech Duraj
A short tale of matrix multiplication

In recent years, some new algorithms for matrix multiplication problem were presented. Each of them is, however, only slightly faster than previous ones, while requiring substantially more complex analysis. Because of this, the long-standing question of optimal matrix multiplication algorithm seems even harder.

In my presentation, a short survery of the matrix multiplication algorithm is given. The presentation is based on François Le Gall's survey lecture of 2014.

Aleksandra Mędrek, Krzysztof Maziarz
Navigating Central Path with Electrical Flows: from Flows to Matchings, and Back

The paper by Aleksander Mądry describes a new approach to the maximum flow problem. We define an electrical flow by assigning resistances to every edge and minimizing total energy instead of maximizing flow. Any flow network can be reduced to some electrical flow problem, using auxiliary reductions to some bipartite matching problems. The main result is a new maximum flow algorithm, working in O(m10/7). The presentation will cover a simpler, O(m3/2) version of the algorithm.

Dominika Salawa, Jakub Cisło
Greedy algorithms for Steiner forest

The paper, resolves a long-standing open question: is the greedy approach for Steiner forest problem optimal up to multiplicative constant? The result by Anupam Gupta and Amit Kumar proves that in fact it is, with constant being at most 96. While some approximation algorithms for this problem, using linear programming, were previously known, this is the first known bound for a greedy algorithm.

Patryk Gołębiowski, Wojciech Kruk
Lower Bounds in the Preprocessing and Query Phases of Routing Algorithms
In the last decade, there has been a substantial amount of research in finding routing algorithms designed specifically to run on real-world graphs. The paper by Colin White analyzes some of these algorithms and gives lower bounds for their complexity.
Magdalena Gargas, Mateusz Jachna
Max flows in O(nm) time, or better
A new max-flow algorithm with O(nm + m16/15 logn) time complexity is presented. By combining this with previous results, an O(nm) algorithm may be obtained, resolving a long-standing open question. This work is due to James B. Orlin.
Krzysztof Francuz, Szymon Łukasz
Fast and simple connectivity in graph timelines

The presented paper (by J. Łącki and A. Karczmarz) deals with graph timelines - graphs with edges being created and destroyed over time. There is an effective algorithm for answering queries about reachability (finding a path between two given vertices) and biconnectivity (two disjoint paths) over some given time intervals.

Dawid Pyczek, Jakub Rówiński
Faster deterministic sorting and priority queues in linear space

The O(n log n) lower bound for sorting is valid only if the sorted objects allow no operations except comparing. For sorting integers, the bound can be broken - Mikkel Thorup's result of 1997 shows an O (n (log log n)2) algorithm for sorting arbitrary integers.

Mateusz Twaróg, Patryk Urbański
Disjoint Set Union with randomized linking

The most popular version of Find-Union algorithm uses path compression and linking by rank. The presented work of Goel, Khanna, Larkin and Tarjan gives an analysis of the same algorithm, but with arbitrary (randomized) linking.

G. Bukowiec, S.Klocek
FKT algorithm

Counting all matchings in a given graph is a #P-complete problem. However, for planar graphs it can be done in polynomial time. The FKT algorithm does it by exploiting the connection between the notions of matrix determinant and matrix permanent.

16.03.2016 14:15
Jakub Cisło, Grzegorz Jurdziński
Tight Hardness Results for LCS and other Sequence Similarity Measures