Algorithmic online optimization for graph problems
Polish National Science Centre grant 2016/22/E/ST6/00499, 2017–2022
The goal of this project is to deliver new algorithmic methods for various problems related to online optimization. The considered problems span vast areas of computer networks, telecommunications, distribution networks and supply-chain management. We address a broad scope of fundamental building blocks, split into three categories: (i) developing online algorithms for efficient dynamic placement of resources in a graph, (ii) developing online algorithms for leasing of resources, (iii) investigating gains of reordering and aggregating demands.
Project publications (2023)
Marcin Bienkowski, Marcin Mucha: An Improved Algorithm For Online Min-Sum Set Cover
37th AAAI Conf. on Artificial Intelligence (AAAI), 37(6), 6815–6822, DOI: 10.1609/aaai.v37i6.25835
Project publications (2022)
Project publications (2022)
Pavel Veselý, Marek Chrobak, Łukasz Jeż, Jiří Sgall: A φ-Competitive Algorithm for Scheduling Packets with Deadlines
SIAM Journal on Computing, vol. 51(5), 1626–1691, 2022, DOI: 10.1137/21m1469753Marcin Bienkowski, Martin Böhm, Jarosław Byrka, Jan Marcinkowski: Online Facility Location with Linear Delay
Int. Conf. on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 45:1–45:17, 2022, DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.45Chen Avin, Marcin Bienkowski, Iosif Salem, Robert Sama, Stefan Schmid and Paweł Schmidt: Deterministic Self-Adjusting Tree Networks Using Rotor Walks
42nd IEEE Int. Conf. on Distributed Computing Systems (ICDCS), 67-77, 2022, DOI: 10.1109/ICDCS54860.2022.00016
Project publications (2021)
Project publications (2021)
Fu-Hong Liu, Hsiang-Hsuan Liu, Prudence W. H. Wong: Greedy is Optimal for Online Restricted Assignment and Smart Grid Scheduling for Unit Size Jobs
Theory of Computing Systems, vol. 65, 1009–1032, 2021, DOI: 10.1007/s00224-021-10037-wMartin Böhm, Lukasz Jez, Jirí Sgall, Pavel Veselý: On packet scheduling with adversarial jamming and speedup
Annals of Operations Research, vol. 298(1), 7–42, 2021, DOI: 10.1007/s10479-019-03153-x
Marcin Bienkowski, Martin Böhm, Martin Koutecký, Thomas Rothvoß, Jiří Sgall, Pavel Veselý: Improved Analysis of Online Balanced Clustering
19th Workshop on Approximation and Online Algorithms (WAOA), 224-233, 2021, DOI: 10.1007/978-3-030-92702-8_14Marcin Bienkowski, Artur Kraska and Hsiang-Hsuan Liu: Traveling Repairperson, Unrelated Machines, and Other Stories About Average Completion Times
48th Int. Colloq. on Automata, Languages and Programming (ICALP), 28:1–28:20, 2021, DOI: 10.4230/LIPIcs.ICALP.2021.28Janardhan Kulkarni, Stefan Schmid, Paweł Schmidt: Scheduling Opportunistic Links in Two-Tiered Reconfigurable Datacenters
33th ACM Symp. on Parallelism in Algorithms and Architectures (SPAA), 318–327, 2021, DOI: 10.1145/3409964.3461786Marcin Bienkowski, Björn Feldkord, Paweł Schmidt: A Nearly Optimal Deterministic Online Algorithm for Non-Metric Facility Location
38th Int. Symp. on Theoretical Aspects of Computer Science (STACS), 14:1-14:17, 2021, DOI: 10.4230/LIPIcs.STACS.2021.14Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Marek Chrobak, Christoph Dürr, Lukáš Folwarczný, Łukasz Jeż, Jiří Sgall, Nguyen Kim Thang, Pavel Veselý: New Results on Multi-Level Aggregation
Theoretical Computer Science, vol. 861, 133-143, 2021, DOI: 10.1016/j.tcs.2021.02.016
Project publications (2020)
Project publications (2020)
Marcin Bienkowski, David Fuchssteiner, Jan Marcinkowski, Stefan Schmid: Online Dynamic B-Matching: With Applications to Reconfigurable Datacenter Networks
ACM SIGMETRICS Performance Evaluation Review, vol. 48(3), 99–108, 2020 DOI: 10.1145/3453953.3453976Chen Avin, Marcin Bienkowski, Andreas Loukas, Maciej Pacut, Stefan Schmid: Dynamic Balanced Graph Partitioning
SIAM Journal on Discrete Mathematics, vol. 34(3), 1791-1812, 2020, DOI: 10.1137/17M1158513Marcin Bienkowski, Jarosław Byrka, Christian Coester, Łukasz Jeż: Unbounded lower bound for k-server against weak adversaries
52nd Annual ACM Symp. on Theory of Computing (STOC), 1165–1169, 2020, DOI: 10.1145/3357713.3384306
Also presented at 5th Highlights of Algorithms (HALG 2020)Marcin Bienkowski, Maciej Pacut, Krzysztof Piecuch: An Optimal Algorithm for Online Multiple Knapsack
47th Int. Colloq. on Automata, Languages and Programming (ICALP), 13:1–13:17, 2020, DOI: 10.4230/LIPIcs.ICALP.2020.13Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Marek Chrobak, Christoph Dürr, Lukáš Folwarczný, Łukasz Jeż, Jiří Sgall, Nguyen Kim Thang, Pavel Veselý: Online Algorithms for Multi-Level Aggregation
Operations Research, vol. 68(1), 214–232, 2020, DOI: 10.1287/opre.2019.1847
Project publications (2019):
Project publications (2019):
Marcin Bienkowski, Łukasz Jeż, Paweł Schmid: Slaying Hydrae: Improved Bounds for Generalized k-Server in Uniform Metrics
30th Int. Symp. on Algorithms and Computation (ISAAC), 14:1–14:14, 2019, DOI: 10.4230/LIPIcs.ISAAC.2019.17Ilan Reuven Cohen, Alon Eden, Amos Fiat, Łukasz Jeż: Dynamic Pricing of Servers on Trees
22nd Int. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 10:1–10:22, 2019, DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.10Fu-Hong Liu, Hsiang-Hsuan Liu, Prudence W. H. Wong: Greedy is Optimal Online Algorithm for Smart Grid Scheduling of Unit Size Jobs
17th Workshop on Approximation and Online Algorithms (WAOA), 217–231, 2019, DOI: 10.1007/978-3-030-39479-0_15
Also presented at 14th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP 2019)Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak, Christian Coester, Lukasz Jez, Elias Koutsoupias: Better Bounds for Online Line Chasing
44th Int. Symp. on Mathematical Foundations of Computer Science (MFCS), 8:1–8:13, 2019, DOI: 10.4230/LIPIcs.MFCS.2019.8
Also presented at 4rd Highlights of Algorithms (HALG 2019)Marcin Bienkowski, Hsiang-Hsuan Liu: Improved Online Algorithm for The Traveling Repairperson Problem on the Line
44th Int. Symp. on Mathematical Foundations of Computer Science (MFCS), 6:1–6:12, 2019, DOI: 10.4230/LIPIcs.MFCS.2019.6
Also presented at 14th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP 2019)Marcin Bienkowski, Jarosław Byrka, Marcin Mucha: Dynamic beats fixed: On phase-based algorithms for file migration
ACM Transactions on Algorithms, vol. 15(4), 46:1–46:21, 2019, DOI: 10.1145/3340296Nikhil Bansal, Marek Eliés, Lukasz Jez, Grigorios Koumoutsos: The (h,k)-Server Problem on Bounded Depth Trees
ACM Transactions on Algorithms, vol. 15(2), 28:1-28:26, 2019, DOI: 10.1145/3301314Thomas Erlebach, Fu-Hong Liu, Hsiang-Hsuan Liu, Mordechai Shalom, Prudence W. H. Wong, Shmuel Zaks: Complexity and Online Algorithms for Minimum Skyline Coloring of Intervals
Theoretical Computer Science, vol. 788, 66–78, 2019, DOI: 10.1016/j.tcs.2019.05.007Pavel Veselý, Marek Chrobak, Łukasz Jeż, Jiří Sgall: A φ-Competitive Algorithm for Scheduling Packets with Deadlines
30th ACM-SIAM Symp. on Discrete Algorithms (SODA), 123–142, 2019, DOI: 10.1137/1.9781611975482.9
Also presented at 14th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP 2019)Adrian Kosowski, Przemysław Uznański, Laurent Viennot: Hardness of exact distance queries in sparse graphs through hub labeling
38th ACM Symp. on Principles of Distributed Computing (PODC), 272–279, 2019, DOI: 10.1145/3293611.3331625
Project publications (2018)
Project publications (2018)
Marcin Bienkowski, Artur Kraska, Hsiang-Hsuan Liu, Paweł Schmidt: A Primal-Dual Online Deterministic Algorithm for Matching with Delays
16th Workshop on Approximation and Online Algorithms (WAOA), 51–68, 2018, DOI: 10.1007/978-3-030-04693-4_4
Also presented at Modern Online Algorithms workshop (MOLI 2018)Marcin Bienkowski, Artur Kraska, Paweł Schmidt: Online service with delay on a line
25th Int. Colloq. on Structural Information and Communication Complexity (SIROCCO), 237-248, 2018, DOI: 10.1007/978-3-030-01325-7_22Marcin Bienkowski, Tomasz Jurdzinski, Miroslaw Korzeniowski, Dariusz R. Kowalski: Distributed Online and Stochastic Queuing on a Multiple Access Channel
ACM Transactions on Algorithms, vol. 14(2), 21:1-21:22, 2018, DOI: 10.1145/3182396Marcin Bienkowski, Nadi Sarrar, Stefan Schmid, Steve Uhlig: Online Aggregation of the Forwarding Information Base: Accounting for Locality and Churn
IEEE/ACM Transactions on Networking, vol. 26(1), 591–604, 2018, DOI: 10.1109/TNET.2017.2787419Marcin Bienkowski, Martin Böhm, Łukasz Jeż, Paweł Laskoś-Grabowski, Jan Marcinkowski, Jirí Sgall, Aleksandra Spyra, Pavel Veselý: Logarithmic price of buffer downscaling on line metrics
Theoretical Computer Science, vol. 707, 89–93, 2018, DOI: 10.1016/j.tcs.2017.10.008
Project publications (2017)
Project publications (2017)
Marcin Bienkowski, Artur Kraska, Paweł Schmidt: A Match in Time Saves Nine: Deterministic Online Matching With Delay
15th Workshop on Approximation and Online Algorithms (WAOA), 132–146, 2017, DOI: 10.1007/978-3-319-89441-6_11Thomas Erlebach, Fu-Hong Liu, Hsiang-Hsuan Liu, Mordechai Shalom, Prudence W. H. Wong, Shmuel Zaks: Complexity and Online Algorithms for Minimum Skyline Coloring of Intervals
11th Int. Conf. on Combinatorial Optimization and Applications (COCOA), 317–332, 2017, DOI: 10.1007/978-3-319-71147-8_22Marcin Bienkowski, Jarosław Byrka, Marcin Mucha: Dynamic beats fixed: On phase-based algorithms for file migration
44th Int. Colloq. on Automata, Languages, and Programming (ICALP), 13:1–13:14, 2017, DOI: 10.4230/LIPIcs.ICALP.2017.13
Also presented at 3rd Highlights of Algorithms (HALG 2018) and 23rd Int. Symp. on Mathematical Programming (ISMP 2018).Marcin Bienkowski, Artur Kraska, Paweł Schmidt: A Deterministic Algorithm for Online Steiner Tree Leasing
15th Algorithms and Data Structures Symposium (WADS), 169–180, 2017, DOI: 10.1007/978-3-319-62127-2_15Marcin Bienkowski, Jan Marcinkowski, Maciej Pacut, Stefan Schmid, Aleksandra Spyra: Online Tree Caching
29th ACM Symp. on Parallelism in Algorithms and Architectures (SPAA), 329–338, 2017, DOI: 10.1145/3087556.3087558