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, 2023, DOI: 10.1609/aaai.v37i6.25835 

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/21m1469753

• Marcin 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.45
  Also presented at Workshop on Recent Trends in Online Algorithms (ICALP 2023 workshop, invited talk)

• Chen Avin, Marcin Bienkowski, Iosif Salem, Robert Sama, Stefan Schmid, 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)

• 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(6), 1009–1032, 2021, DOI: 10.1007/s00224-021-10037-w

• Martin 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
  Approximation and Online Algorithms - 19th Int. Workshop (WAOA), 224–233, 2021, DOI: 10.1007/978-3-030-92702-8_14 

• Marcin 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.28

• Janardhan 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.3461786

• Marcin 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.14

• Marcin 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)

• 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.3453976

• Chen 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/17M1158513

• Marcin 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.13

• Marcin 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):

• 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.17

• Ilan 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.10

• Fu-Hong Liu, Hsiang-Hsuan Liu, Prudence W. H. Wong: Greedy is Optimal Online Algorithm for Smart Grid Scheduling of Unit Size Jobs
  Approximation and Online Algorithms - 17th Int. Workshop (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/3340296

• Nikhil Bansal, Marek Eliáš, 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/3301314

• Thomas 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.007

• Pavel 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)

• Marcin Bienkowski, Artur Kraska, Hsiang-Hsuan Liu, Paweł Schmidt: A Primal-Dual Online Deterministic Algorithm for Matching with Delays
  Approximation and Online Algorithms - 16th Int. Workshop (WAOA), 51–68, 2018, DOI: 10.1007/978-3-030-04693-4_4
  Also presented at Modern Online Algorithms workshop (ICALP 2018 workshop)

• 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_22

• Marcin 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/3182396

• Marcin 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.2787419

• Marcin 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)

• Marcin Bienkowski, Artur Kraska, Paweł Schmidt: A Match in Time Saves Nine: Deterministic Online Matching With Delay
  Approximation and Online Algorithms - 15th Int. Workshop (WAOA), 132–146, 2017, DOI: 10.1007/978-3-319-89441-6_11

• Thomas 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_22

• Marcin 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 at 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_15

• Marcin 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