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. Racke: 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)
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
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
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
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.
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
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.
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.
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.
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.
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.