Algorithmic seminar (archive)

Algorithmic seminar 2025

• 3.11.2025. Agnieszka Tatarczuk
  S. Bubeck, C. Coester, Y. Rabani: The Randomized k-Server Conjecture Is False!, STOC 2023

• 26.11.2025. Michał Łukasik
  Modern shortest path algorithms

• 1.12.2025. Bartosz Łakomy
  Fair division problems

• 19.1.2026 Szymon Kiczak
  J. Fakcharoenphol, S. Rao, K. Talwar: A tight bound on approximating arbitrary metrics by tree metrics, STOC 2003.

Algorithmic seminar 2024

• 23.10.2024. Mateusz Basiak
  N. Buchbinder, T. Kimbrel, R. Levi, K. Makarychev, M. Sviridenko: Online Make-to-Order Joint Replenishment Model: Primal-Dual Competitive Algorithms, SODA 2008

• 27.11.2024. Tomasz Orda
  A. Deligkas, M. Lotfi, A. Voudouris: Agent-Constrained Truthful Facility Location Games, SAGT 2024

• 11.12.2024. Agnieszka Tatarczuk
  H. Räcke: Optimal Hierarchical Decompositions for Congestion Minimization in Networks, STOC 2008

• 15.01.2025. Adam Ciężkowski
  Dynamic TCP-Acknowledgement Problem (from the notes The Design of Competitive Online Algorithms via a Primal-Dual Approach)

• 22.01.2025. Artur Krzyżyński
  Online graph optimization problems (from the notes The Design of Competitive Online Algorithms via a Primal-Dual Approach)

Algorithmic seminar 2023

• 17.10.2023 Michał Fica
  Dynamic Algorithms for Graph Connectivity (from the book Advanced Algorithms)

• 14.11.2023 Adam Ciężkowski
  Minimum-degree spanning tree (from the book The design of Approximation Algorithms)

• 21.11.2023 Pola Marciniak
  V. Traub, J. Vygen, R. Zenklusen, Reducing Path TSP to TSP, STOC 2020

• 28.11.2023 Maja Orłowska
  The Metrical Task System Problem on a Weighted Star (from the notes The Design of Competitive Online Algorithms via a Primal-Dual Approach)

• 12.12.2023 Jakub Kot

Balanced cuts (from the book The design of Approximation Algorithms)

• 19.12.2023 Mateusz Basiak
  N. Buchbinder, A. Gupta, M. Molinaro, J. Naor: k-Servers with a Smile: Online Algorithms via Projections, SODA 2019

• 9.1.2024 Agnieszka Tatarczuk
  S. Yan: Edge-weighted Online Stochastic Matching: Beating 1-1/e, SODA 2023

• 16.1.2024 Adrianna Struzik
  Y. Azar, C. Machluf, B. Patt-Shamir, N. Touitou: Competitive Vertex Recoloring, ICALP 2022

• 23.1.2024  Artur Krzyżyński
  H. Räcke, C. Sohler, M. Westermann: Online Scheduling for Sorting Buffers, ESA 2002

Algorithmic seminar 2022

• 25.10.2022. Mateusz Basiak
  Online Learning: Experts and Bandits

• 8.11.2022. Anna Pacanowska
  N. Bansal, B. Cloostermans: Minimizing Maximum Flow-Time on Related Machines, APPROX 2015

• 29.11.2022. Agnieszka Tatarczuk
  C. Argue, A. Gupta, G. Guruganesh: Dimension-Free Bounds on Chasing Convex Functions, COLT 2020 

• 13.12.2022. Jonatan Hrynko
  A Gupta, E Lee, J Li: An FPT algorithm beating 2-approximation for k-cut, SODA 2018

• 20.12.2022. Rafał Tatarczuk
  E. Demaine, Y. Huang, C. Liao, K. Sadakane: Approximating the Canadian Traveller Problem with Online Randomization

• 3.01.2023. Adrianna Struzik
  Algebraic algorithms for matching problems

• 17.01.2023. Oskar Fiuk
  F. Grandoni, A. Ameli, V. Traub: Breaching the 2-approximation barrier for the forest augmentation problem, STOC 2022

• 24.01.2023. Emil Kisielewicz
  M. Henzinger, S. Neumann, H. Räcke, S. Schmid: Tight Bounds for Online Graph Partitioning, SODA 2021

Algorithmic seminar 2021

• 28.10.2021. Marcin Bieńkowski
  Deterministic online algorithm for non-metric facility location

• 4.11.2021. Jarek Byrka
  Steiner tree

• 25.11.2021. Andriy Bernad
  T. Lykouris, S. Vassilvitskii: Competitive caching with machine learned advice, ICML 2018

• 9.12.2021. Kacper Puchalski
  Y. Azar, A. Chiplunkar, H. Kaplan: Polylogarithmic Bounds on the Competitiveness of Min-cost (Bipartite) Perfect Matching with Delays, SODA 2017

• 5.01.2021. Adrianna Struzik
  K. Chandrasekaran, C. Xu, X. Yu: Hypergraph k-Cut in Randomized Polynomial Time, SODA 2018

• 13.01.2021. Oskar Fiuk
  M. Feldman, O. Svensson , R. Zenklusen: A Simple O(log log(rank))-Competitive Algorithm for the Matroid Secretary Problem, SODA 2018

• 14.1.2021. Mateusz Basiak (piątek, 12:15)
  O. Svensson, J. Tarnawski, L. Végh A constant-factor approximation algorithm for the asymmetric traveling salesman problem, STOC 2018 

• 20.01.2021. Grzegorz Ciesielski
  C. Argue, A. Gupta, G. Guruganesh, Z. Tang: Chasing Convex Bodies with Linear Competitive Ratio, SODA 2020

• 21.01.2021. Agnieszka Pawicka (piątek, 12:15)
  C. Coester, E. Koutsoupias: The Online k-Taxi Problem, STOC 2018

• 27.01.2021. Dawid Barzyk
  S. Liu, W. Shen, H. Xu: Optimal Pricing of Information, EC 2021

• 3.02.2021. Agnieszka Dudek
  S. Umboh: Online Network Design Algorithms via Hierarchical Decompositions, SODA 2015

Algorithmic seminar 2017

• 1.3.2017. Paweł Schmidt
  M. Englert, H. Räcke: Reordering Buffers with Logarithmic Diameter Dependency for Trees, SODA 2017.

• 8.3.2017. Michał Gańczorz
  M. Bæk, T. Knudsen: Linear Hashing is Awesome, FOCS 2016.

• 15.3.2017. Jadwiga Pokorska
  M. Babaioff, N. Immorlica, R. Kleinberg: Matroids, secretary problems, and online mechanisms, SODA 2007.

• 22.3.2017. Piotr Ostropolski-Nalewaja
  M. Dinitz, Z. Zhang: Approximating Low-Stretch Spanners, SODA 2016.

• 29.3.2017. Bartosz Kostka
  G. Cormode, S. Muthukrishnan: An Improved Data Stream Summary: The Count-Min Sketch and its Applications, JALGO 2005.

• 5.4.2017. Jan Marcinkowski
  A. Sebo, A. van Zuylen: The Salesman's Improved Paths: A 3/2+1/34 Approximation, FOCS 2016.

• 12.4.2017. Mateusz Lewandowski
  J. Lenstra, D. Shmoys and É. Tardos: Approximation algorithms for scheduling unrelated parallel machines, Mathematical Programming.

• 26.4.2017. Krzysztof Nowicki
  K. Ahn, S. Guha, A. McGregor: Analyzing Graph Structure via Linear Measurements, SODA 2012 + H. Jowhari, M. Saglam, G. Tardos: Tight Bounds for L_p Samplers, Finding Duplicates in Streams, and Related Problems, PODS 2011.

• 10.5.2017. Wojciech Janczewski
  B. Kalyanasundaram, K. Pruhs: Speed is as Powerful as Clairvoyance, FOCS 1995

• 17.5.2017. Karol Pokorski
  S. Arora: Polynomial Time Approximation Schemes for Euclidean Traveling Salesman and other Geometric Problems, JACM 1998.

• 24.5.2017. Artur Kraska
  M. Englert, M. Westermann: Considering Suppressed Packets Improves Buffer Management in QoS Switches, SODA 2007.

• 31.5.2017. Grzegorz Głuch
  M. Cohen, Y. Lee, G. Miller, J. Pachocki, A. Sidford: Geometric Median in Nearly Linear Time, STOC 2016.

• 7.6.2017. Jakub Bieńczyk
  I. Gamzu, D. Segev: A Polynomial-Time Approximation Scheme for The Airplane Refueling Problem

• 14.6.2017. Paweł Garncarek
  L. Chen, N. Megow, K. Schewior: An O(log m)-Competitive Algorithm for Online Machine Minimization, SODA 2016.

Algorithmic seminar 2016

• 7.3.2016. Mateusz Lewandowski
  J. Fakcharoenphol, S. Rao, K. Talwar: A tight bound on approximating arbitrary metrics by tree metrics, STOC 2003.

• 14.3.2016. Maciej Pacut
  M. Chrobak, C. Dürr, B. Nilsson: Competitive Strategies for Online Clique Clustering, CIAC 2015.

• 21.3.2016. Piotr Ostropolski-Nalewaja
  Y. Bartal, A. Filtser, O. Neiman: On Notions of Distortion and an Almost Minimum Spanning Tree with Constant Average Distortion, SODA 2016.

• 4.4.2016. Jakub Sękowski
  C. Chekuri, V. Madan: Simple and Fast Rounding Algorithms for Directed and Node-weighted Multiway Cut, SODA 2016.

• 11.4.2016. Szymon Dudycz
  C. Chekuri, K. Quanrud: A Fast Approximation for Maximum Weight Matroid Intersection, SODA 2016.

• 18.4.2016. Michał Łowicki
  A. Goldberg: Scaling Algorithms for the Shortest Paths Problem, SICOMP.

• 25.4.2016. Artur Kraska
  A. Blum, C. Burch, A. Kalai: Finely-Competitive Paging. FOCS 1999.

• 9.5.2016. Michał Karpiński
  C. Annamalai: Finding Perfect Matchings in Bipartite Hypergraphs, SODA 2016.

• 16.5.2016. Paweł Garncarek

E. Burjons, J. Hromkovič, X. Muñoz, W. Unger: Online Graph Coloring with Advice and Randomized Adversary

Algorithmic seminar 2015

• 5.3.2015. Krzysztof Piecuch
  S. Nilsson: Sorting in O(n lg lg n)

• 12.3.2015. Mateusz Lewandowski
  A. Gupta, A. Kumar: Greedy Algorithms for Steiner Forest, STOC 2015.

• 9.3.2015. Jan Marcinkowski
  O. Svensson: Approximating ATSP by Relaxing Connectivity.

• 26.3.2015. Tomasz Maczyński
  A. Adamaszek, A. Wiese: A quasi-PTAS for the two-dimensional geometric knapsack problem, SODA 2015.

• 2.4.2015. Krzysztof Król
  G. Italiano, L. Laura, F. Santaroni: Finding Strong Bridges and Strong Articulation Points in Linear Time, COCOA 2010.

• 17.4.2015. Aleksandra Spyra
  J. Łącki, P. Sankowski: Optimal decremental connectivity in planar graphs, STACS 2015.

• 6.5.2015. Piotr Derkowski
  A. Karlin, C. Kenyon, D. Randall: Dynamic TCP Acknowledgement and other stories about e/(e-1), STOC 2001.

• 21.5.2015. Szymon Dudycz
  I. Giotis, L. Kirousis, K. Psaromiligkos, D. Thilikos: On the Algorithmic Lovász Local Lemma and Acyclic Edge Coloring

• 18.6.2015. Michał Gańczorz
  M. Thorup, U. Zwick: Approximate distance oracles, STOC 2001.

Algorithmic seminar 2014

• 10.10.2013. Krzysztof Piecuch
  Ford-Johnson Algorithm

• 17.10.2013. Jan Marcinkowski
  F. Grandoni, T. Rothvoss: Prizing on Paths: A PTAS for the Highway Problem, SODA 2013.

• 24.10.2013. Mateusz Sieradzan
  S. Vaya: The complexity of resolving conflicts on MAC.

• 7.11.2013. Filip Pacanowski
  S. Frischknecht, S. Holzer, R. Wattenhofer: Networks Cannot Compute Their Diameter in Sublinear Time, SODA 2012.

• 14.11.2013. Mateusz Lewandowski
  K. Jain: A factor 2 approximation algorithm for the generalized Steiner network problem, FOCS 1998.

• 21.11.2013. Adam Kunysz
  A. Björklund, T. Husfeldt,  M. Koivisto: Set partitioning via inclusion-exclusion, JCOMP 2009.

• 28.11.2013. Tadeusz Dul
  Ł. Jeż, M. Cygan: Online knapsack revisited, WAOA 2013.

• 5.12.2013. Michał Gańczorz
  R. Beier, B. Vöcking: Random knapsack in expected polynomial time, STOC 2003.

• 12.12.2013. Tomasz Maczyński
  B. Chazelle: The soft heap: an approximate priority queue with optimal error rate, JACM 2000 + H. Kaplan, U. Zwick: A simpler implementation and analysis of Chazelle's soft heaps, SODA 2009.

• 9.1.2014. Artur Kraska
  N. Megow, K. Mehlhorn, P. Schweitzer: Online Graph Exploration: New Results on Old and New Algorithms, ICALP 2011

• 16.1.2014. Krzysztof Pieprzak
  J. Łącki: Improved Deterministic Algorithms for Decremental Transitive Closure and Strongly Connected Components, SODA 2011.

• 23.1.2014. Paweł Schmidt
  M. Halldórsson, B. Patt-Shamir, D. Rawitz: Online Scheduling with Interval Conflicts, STACS 2011.

• 30.1.2014. Paweł Michalak
  B. Haeupler, T. Kavitha, R. Mathew, S. Sen, R. Tarjan: Incremental Cycle Detection, Topological Ordering, and Strong Component Maintenance

• Michał Różański.
  S. Khanna, J. Naor and D. Raz: Control Message Aggregation in Group Communication Protocols, ICALP 2002.

Algorithmic seminar 2013

• 23.10.2012. Seweryn Jagusiak
  The k-median problem (from the book The design of Approximation Algorithms)

• 6.11.2012. Krzysztof Sornat
  Single-source rent-or-buy (from the book The design of Approximation Algorithms)

• 20.11.2012. Karol Konaszyński
  Solving LPs via the Ellipsoid method.

• 4.12.2012. Paweł Kacprzak
  F. Kuhn, T. Locher, R. Wattenhofer: Distributed selection: a missing piece of data aggregation, CACM 2008.

• 11.12.2012. Kacper Król
  C. Ortolf, C. Schindelhauer: Online Multi-Robot Exploration of Grid Graphs with. Rectangular Obstacles, SPAA 2012.

• 18.12.2012. Adam Kunysz
  Exponential algorithms

• 8.1.2013. Michał Karpiński
  L. Roditty, U. Zwick: A Fully Dynamic Reachability Algorithm for Directed Graphs with an Almost Linear Update Time, STOC 2004.

• 15.1.2013. Jan Marcinkowski
  T. Mömke, O. Svensson, Approximating Graphic TSP by Matchings.

• 22.1.2013. Artur Kraska
  P. Bose, K. Douïeb, V. Dujmovic, R. Fagerberg: An O(log log n)-Competitive Binary Search Tree with Optimal Worst-Case Access Times, SWAT 2010.

• 29.1.2013. Mateusz Sieradzan
  R. Moser, G. Tardos: A Constructive Proof of the General Lovasz Local Lemma, 2009.

Algorithmic seminar 2012

• 19.10.2011. Krzysztof Piecuch
  S. Pettie, V. Ramachandran: An Optimal Spanning Tree Algorithm.

• 26.10.2011. Łukasz Kornek
  J. Augustine, S. Irani, C. Swamy: Optimal Power-Down Strategies, FOCS 2004.

• 2.11.2011 + 9.11.2011 Damian Rusak
  E. Koutsoupias: The k-server problem + Weak Adversaries for the k-Server Problem, FOCS 1999.

• 23.11.2011. Jakub Banaszewski
  H. Räcke: Minimizing Congestion in General Networks, FOCS 2002.

• 5.12.2011. Bartosz Rybicki
  J. Fakcharoenphol, S. Rao, K. Talwar: A tight bound on approximating arbitrary metrics by tree metrics, STOC 2003.

• 7.12.2011. Łukasz Zatorski
  L. Fleischer, M. Skutella: Quickest Flows Over Time, JCOMP 2007.

• 11.12.2011. Kacper Król
  A. Mehta, A. Saberi, U. Vazirani, V. Vazirani: AdWords and generalized online matching, JACM 2007.

• 19.12.2011. Paweł Kacprzak
  Planar point location using persistent search trees (from the book Advanced Algorithms)

• 21.12.2011. Jakub Tarnawski

Matchings, bipartite and non-bipartite, unweighted and weighted (from the book Advanced Algorithms)

• 4.1.2012. Damian Straszak
  Primes in P.

• 11.1.2012. Marcin Dublański
  M. Bender, J. Fineman, S. Gilbert: A new approach to incremental topological ordering, SODA 2011.

Algorithmic seminar 2011

• 22.3.2011. Przemysław Pietrzkiewicz
  J. Łącki, Improved Deterministic Algorithms for Decremental Transitive Closure and Strongly Connected Components, SODA 2011.

• 29.3.2011. Stanisław Zawadzki
  K. Jain, A factor 2 approximation algorithm for the generalized Steiner network problem, FOCS 1998.

• 12.4.2011. Krzysztof Piecuch.
  A linear-time Randomized MST algorithm.

• 19.4.2011. Michał Karpiński
  B. Chazelle: The soft heap: an approximate priority queue with optimal error rate, JACM 2000 + H. Kaplan and U. Zwick: A simpler implementation and analysis of Chazelle's soft heaps, SODA 2009.

• 10.5.2011. Krzysztof Sakwerda
  M. Paterson, U. Zwick: Overhang, SODA 2006.

• 24.5.2011. Łukasz Kornek
  N. Young: On-Line File Caching, Algorithmica 2002.

• 31.5.2011. Kamil Kaniewski
  P. Goldberg and C. Papadimitriou: Reducibility among equilibrium problems, STOC 2006.

• 7.6.2011. Piotr Walkowski
  A. Mehta, A. Saberi, U. Vazirani, V. Vazirani: AdWords and generalized online matching, JACM 2007.

• 14.6.2011. Łukasz Perzyński
  R. Beier, B. Vöcking: Random knapsack in expected polynomial time, STOC 2003

• 15.6.2011. Damian Rusak
  S. Arora: Polynomial Time Approximation Schemes for Euclidean Traveling Salesman and other Geometric Problems, JACM 1998.