## Algorithms

### 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.
 08.12.2016 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.
 01.12.2016 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.
 24.11.2016 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.
 17.11.2016 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.
 10.11.2016 Magdalena Gargas, Mateusz Jachna Max flows in O(nm) time, or better A new max-flow algorithm with O(nm + m16/15 log2 n) 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.
 03.11.2016 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.
 27.10.2016 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.
 20.10.2016 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.
 13.10.2016 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