Algorithmic seminar (archive)

Algorithmic seminar 2022

• 25.10.2022. Mateusz Basiak
  Online Learning: Experts and Bandits

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

• 29.11.2022. Agnieszka Tatarczuk
  C.J. Argue, Anupam Gupta, Guru 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
  Monika Henzinger, Stefan Neumann, Harald Räcke, Stefan 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
  Thodoris Lykouris, Sergei Vassilvitskii: Competitive caching with machine learned advice, ICML 2018

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

• 5.01.2021. Adrianna Struzik
  Karthekeyan Chandrasekaran, Chao Xu, Xilin Yu: Hypergraph k-Cut in Randomized Polynomial Time, SODA 2018

• 13.01.2021. Oskar Fiuk
  Moran Feldman, Ola Svensson , Rico 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, LA Végh A constant-factor approximation algorithm for the asymmetric traveling salesman problem, STOC 2018

• 20.01.2021. Grzegorz Ciesielski
  C.J. Argue, Anupam Gupta, Guru Guruganesh, Ziye Tang: Chasing Convex Bodies with Linear Competitive Ratio, SODA 2020

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

• 27.01.2021. Dawid Barzyk
  Shuze Liu, Weiran Shen, Haifeng Xu: Optimal Pricing of Information, EC 2021

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

Algorithmic seminar 2017

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

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

• 15.3.2017. Jadwiga Pokorska
  Moshe Babaioff, Nicole Immorlica, Robert Kleinberg: Matroids, secretary problems, and online mechanisms, SODA 2007.

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

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

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

• 12.4.2017. Mateusz Lewandowski
  Jan Karel Lenstra, David B. Shmoys and Éva Tardos: Approximation algorithms for scheduling unrelated parallel machines, Mathematical Programming.

• 26.4.2017. Krzysztof Nowicki
  Kook Jin Ahn, Sudipto Guha, Andrew McGregor: Analyzing Graph Structure via Linear Measurements, SODA 2012 + Hossein Jowhari, Mert Saglam, Gabor Tardos: Tight Bounds for L_p Samplers, Finding Duplicates in Streams, and Related Problems, PODS 2011.

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

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

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

• 31.5.2017. Grzegorz Głuch
  Michael B. Cohen, Yin Tat Lee, Gary Miller, Jakub Pachocki, Aaron Sidford: Geometric Median in Nearly Linear Time, STOC 2016.

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

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

Algorithmic seminar 2016

• 7.3.2016. Mateusz Lewandowski
  Jittat Fakcharoenphol, Satish Rao, Kunal Talwar: A tight bound on approximating arbitrary metrics by tree metrics, STOC 2003.

• 14.3.2016. Maciej Pacut
  Marek Chrobak, Christoph Dürr, Bengt J. Nilsson: Competitive Strategies for Online Clique Clustering, CIAC 2015.

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

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

• 11.4.2016. Szymon Dudycz
  Chandra Chekuri, Kent 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
  Avrim Blum, Carl Burch, Adam Kalai: Finely-Competitive Paging. FOCS 1999.

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

• 16.5.2016. Paweł Garncarek
  Online Graph Coloring with Advice and Randomized Adversary

Algorithmic seminar 2015

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

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

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

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

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

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

• 6.5.2015. Piotr Derkowski
  Anna R. Karlin, Claire Kenyon, Dana Randall: Dynamic TCP Acknowledgement and other stories about e/(e-1), STOC 2001.

• 21.5.2015. Szymon Dudycz
  Ioannis Giotis, Lefteris Kirousis, Kostas I. Psaromiligkos, Dimitrios M. Thilikos: On the Algorithmic Lovász Local Lemma and Acyclic Edge Coloring. ANALCO 2015.

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

Algorithmic seminar 2014

• 10.10.2013. Krzysztof Piecuch
  Ford-Johnson Algorithm

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

• 24.10.2013. Mateusz Sieradzan
  Shailesh 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
  Andreas Björklund, Thore Husfeldt, and Mikko Koivisto: Set partitioning via inclusion-exclusion, JCOMP 2009.

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

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

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

• 9.1.2014. Artur Kraska
  Nicole Megow, Kurt Mehlhorn, Pascal Schweitzer: Online Graph Exploration: New Results on Old and New Algorithms, ICALP 2011

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

• 23.1.2014. Paweł Schmidt
  Magnús M. Halldórsson, Boaz Patt-Shamir, Dror Rawitz: Online Scheduling with Interval Conflicts, STACS 2011.

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

• Michał Różański.
  Sanjeev Khanna, Joseph Seffi Naor and Dan Raz: Control Message Aggregation in Group Communication Protocols, ICALP 2002.

Algorithmic seminar 2013

• 23.10.2012. Seweryn Jagusiak
  The k-median problem. Williamson, Shmoys, chapter 7.7.

• 6.11.2012. Krzysztof Sornat
  Single-source rent-or-buy. Williamson, Shmoys, chapter 12.2.

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

• 4.12.2012. Paweł Kacprzak
  Fabian Kuhn, Thomas Locher, Roger Wattenhofer: Distributed selection: a missing piece of data aggregation, CACM 2008.

• 11.12.2012. Kacper Król
  Christian Ortolf, Christian 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
  Liam Roditty, Uri Zwick: A Fully Dynamic Reachability Algorithm for Directed Graphs with an Almost Linear Update Time, STOC 2004.

• 15.1.2013. Jan Marcinkowski
  Tobias Mömke, Ola Svensson, Approximating Graphic TSP by Matchings.

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

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

Algorithmic seminar 2012

• 19.10.2011. Krzysztof Piecuch
  Seth Pettie, Vijaya Ramachandran: An Optimal Spanning Tree Algorithm.

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

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

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

• 5.12.2011. Bartosz Rybicki
  Jittat Fakcharoenphol, Satish Rao, Kunal Talwar: A tight bound on approximating arbitrary metrics by tree metrics, STOC 2003.

• 7.12.2011. Łukasz Zatorski
  Lisa Fleischer and Martin Skutella: Quickest Flows Over Time, JCOMP 2007.

• 11.12.2011. Kacper Król
  Aranyak Mehta, Amin Saberi, Umesh Vazirani, Vijay Vazirani: AdWords and generalized online matching, JACM 2007.

• 19.12.2011. Paweł Kacprzak
  Lecture 23 from CMU Advanced Algorithms: Planar point location using persistent search trees.

• 21.12.2011. Jakub Tarnawski
  Lecture 12 from CMU Advanced Algorithms: Matchings, bipartite and non-bipartite, unweighted and weighted.

• 4.1.2012. Damian Straszak
  Primes in P.

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

Algorithmic seminar 2011

• 22.3.2011. Przemysław Pietrzkiewicz
  Jakub Łą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
  Bernard Chazelle: The soft heap: an approximate priority queue with optimal error rate, JACM 2000 + Heim Kaplan and Uri Zwick: A simpler implementation and analysis of Chazelle's soft heaps, SODA 2009.

• 10.5.2011. Krzysztof Sakwerda
  Mike Paterson, Uri Zwick: Overhang, SODA 2006.

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

• 31.5.2011. Kamil Kaniewski
  Paul W. Goldberg and Christos H. Papadimitriou: Reducibility among equilibrium problems, STOC 2006.

• 7.6.2011. Piotr Walkowski
  Aranyak Mehta, Amin Saberi, Umesh Vazirani, Vijay Vazirani: AdWords and generalized online matching, JACM 2007.

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

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