Zmiana języka

Projects search

Algorithmic online optimization for graph problems

2016/22/E/ST6/00499

Keywords

Descriptors

  • ST6_6: Algorytmika, algorytmy równoległe, rozproszone i sieciowe, algorytmiczna teoria gier

Panel

ST6 – Computer science and informatics: informatics and information systems, computer science, scientific computing, intelligent systems

Host institution

Uniwersytet Wrocławski, Wydział Matematyki i Informatyki

Voivodeship: dolnośląskie

Other projects carried out by the institution »

Principal investigator (from the host institution)

dr hab. Marcin Bieńkowski

Number of co-investigators in the project: 5

Call

SONATA BIS 6 – announced on 2016-06-15

Amount awarded
1 225 850 PLN
Project start date
2017-04-18
Project end date
2024-04-17
Project duration
84 months (the same as in the proposal)
Project status
Project settled

Project description

Download the project description in a pdf file

Note — project descriptions were prepared by the authors of the applications themselves and placed in the system in an unchanged form.

Information in the final report

Publication in academic press/journals (13)

  1. Greedy is Optimal for Online Restricted Assignment and Smart Grid Scheduling for Unit Size Jobs

    Authors:
    Fu-Hong Liu, Hsiang-Hsuan Liu, Prudence W. H. Wong
    Academic press:
    Theory of Computing Systems (year: 2021, volume: 65(6), pages: 1009-1032), Publisher: Springer International Publishing
    Status:
    Published
    DOI:
    10.1007/s00224-021-10037-w – link to the publication

  2. New Results on Multi-Level Aggregation

    Authors:
    Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Marek Chrobak, Christoph Dürr, Lukáš Folwarczný, Łukasz Jeż, Jiří Sgall, Nguyen Kim Thang, Pavel Veselý
    Academic press:
    Theoretical Computer Science (year: 2021, volume: 861, pages: 133-143), Publisher: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.tcs.2021.02.016 – link to the publication

  3. Online Dynamic B-Matching With Applications to Reconfigurable Datacenter Networks

    Authors:
    Marcin Bienkowski, David Fuchssteiner, Jan Marcinkowski, Stefan Schmid
    Academic press:
    ACM SIGMETRICS Performance Evaluation Review (year: 2020, volume: 48(3), pages: 99-108), Publisher: Association for Computing Machinery (ACM)
    Status:
    Published
    DOI:
    10.1145/3453953.3453976 – link to the publication

  4. On packet scheduling with adversarial jamming and speedup

    Authors:
    Martin Böhm, Łukasz Jeż, Jiří Sgall, Pavel Veselý
    Academic press:
    Annals of Operations Research (year: 2021, volume: 298, pages: 15523), Publisher: Springer International Publishing
    Status:
    Published
    DOI:
    10.1007/s10479-019-03153-x – link to the publication

  5. A φ-Competitive Algorithm for Scheduling Packets with Deadlines

    Authors:
    Pavel Veselý, Marek Chrobak, Łukasz Jeż, Jiří Sgall
    Academic press:
    SIAM Journal on Computing (year: 2022, volume: 51(5), pages: 1626-1691), Publisher: Society for Industrial and Applied Mathematics (SIAM)
    Status:
    Published
    DOI:
    10.1137/21m1469753 – link to the publication

  6. Dynamic Balanced Graph Partitioning

    Authors:
    Chen Avin, Marcin Bienkowski, Andreas Loukas, Maciej Pacut, Stefan Schmid
    Academic press:
    SIAM Journal on Discrete Mathematics (year: 2020, volume: 34(3), pages: 1791-1812), Publisher: Society for Industrial and Applied Mathematics (SIAM)
    Status:
    Published
    DOI:
    10.1137/17M1158513 – link to the publication

  7. Online Aggregation of the Forwarding Information Base: Accounting for Locality and Churn

    Authors:
    Marcin Bienkowski, Nadi Sarrar, Stefan Schmid, Steve Uhlig
    Academic press:
    IEEE/ACM Transactions on Networking (year: 2018, volume: 26(1), pages: 591-604), Publisher: Institute of Electrical and Electronics Engineers (IEEE)
    Status:
    Published
    DOI:
    10.1109/TNET.2017.2787419 – link to the publication

  8. Logarithmic price of buffer downscaling on line metrics

    Authors:
    Marcin Bienkowski, Martin Böhm, Łukasz Jeż, Paweł Laskoś-Grabowski, Jan Marcinkowski, Jirí Sgall, Aleksandra Spyra, Pavel Veselý
    Academic press:
    Theoretical Computer Science (year: 2018, volume: 707, pages: 89-93), Publisher: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.tcs.2017.10.008 – link to the publication

  9. Complexity and online algorithms for minimum skyline coloring of intervals

    Authors:
    Thomas Erlebach, Fu-Hong Liu, Hsiang-Hsuan Liu, Mordechai Shalom, Prudence W. H. Wong, Shmuel Zaks
    Academic press:
    Theoretical Computer Science (year: 2019, volume: 788, pages: 66-78), Publisher: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.tcs.2019.05.007 – link to the publication

  10. Distributed Online and Stochastic Queuing on a Multiple Access Channel

    Authors:
    Marcin Bienkowski, Tomasz Jurdzinski, Miroslaw Korzeniowski, Dariusz R. Kowalski
    Academic press:
    Transactions on Algorithms (year: 2018, volume: 14(2), pages: 21:1-21:22), Publisher: Association for Computing Machinery (ACM)
    Status:
    Published
    DOI:
    10.1145/3182396 – link to the publication

  11. The (h,k)-Server Problem on Bounded Depth Trees

    Authors:
    Nikhil Bansal, Marek Eliás, Lukasz Jez, Grigorios Koumoutsos
    Academic press:
    ACM Transactions on Algorithms (year: 2019, volume: 15(2), pages: 28:1-28:26), Publisher: Association for Computing Machinery (ACM)
    Status:
    Published
    DOI:
    10.1145/3301314 – link to the publication

  12. Online Algorithms for Multi-Level Aggregation

    Authors:
    Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Marek Chrobak, Christoph Dürr, Lukáš Folwarczný, Łukasz Jeż, Jiří Sgall, Nguyen Kim Thang, Pavel Veselý
    Academic press:
    Operations Research (year: 2020, volume: 68(1), pages: 214-232), Publisher: The Institute for Operations Research and the Management Sciences (INFORMS)
    Status:
    Published
    DOI:
    10.1287/opre.2019.1847 – link to the publication

  13. Dynamic Beats Fixed: On Phase-based Algorithms for File Migration

    Authors:
    Marcin Bienkowski, Jaroslaw Byrka, Marcin Mucha
    Academic press:
    ACM Transactions on Algorithms (year: 2019, volume: 15(4), pages: 46:1-46:21), Publisher: Association for Computing Machinery (ACM)
    Status:
    Published
    DOI:
    10.1145/3340296 – link to the publication

Articles in post-conference publications (23)

  1. Traveling Repairperson, Unrelated Machines, and Other Stories About Average Completion Times

    Authors:
    Marcin Bienkowski, Artur Kraska, Hsiang-Hsuan Liu
    Conference:
    48th International Colloquium on Automata, Languages, and Programming (ICALP) (year: 2021, pages: 28:1–28:20), Publisher: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik
    Date:
    conference 12-16 lipca 2021
    Status:
    Published

  2. Online Facility Location with Linear Delay

    Authors:
    Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Jan Marcinkowski
    Conference:
    International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) (year: 2022, pages: 45:1-45:17), Publisher: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik
    Date:
    conference 19-21 września 2022
    Status:
    Published

  3. Deterministic Self-Adjusting Tree Networks Using Rotor Walks

    Authors:
    Chen Avin, Marcin Bienkowski, Iosif Salem, Robert Sama, Stefan Schmid, Pawel Schmidt
    Conference:
    42nd IEEE International Conference on Distributed Computing Systems (ICDCS) (year: 2022, pages: 67-77), Publisher: Institute of Electrical and Electronics Engineers (IEEE)
    Date:
    conference 10-13 lipca 2022
    Status:
    Published

  4. An Improved Algorithm For Online Min-Sum Set Cover

    Authors:
    Marcin Bienkowski, Marcin Mucha
    Conference:
    37th AAAI Conference on Artificial Intelligence (AAAI) (year: 2023, pages: 6815-6822), Publisher: Association for the Advancement of Artificial Intelligence (AAAI)
    Date:
    conference 7-14 lutego 2023
    Status:
    Published

  5. Greedy Is Optimal for Online Restricted Assignment and Smart Grid Scheduling for Unit Size Jobs

    Authors:
    Fu-Hong Liu, Hsiang-Hsuan Liu, Prudence W. H. Wong
    Conference:
    Approximation and Online Algorithms - 17th International Workshop (WAOA) (year: 2019, pages: 217-231), Publisher: Springer International Publishing
    Date:
    conference 12-13 września 2019
    Status:
    Published

  6. Dynamic Pricing of Servers on Trees

    Authors:
    Ilan Reuven Cohen, Alon Eden, Amos Fiat, Lukasz Jez
    Conference:
    International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) (year: 2019, pages: 10:1-10:22), Publisher: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik
    Date:
    conference 20-22 września 2019
    Status:
    Published

  7. Better Bounds for Online Line Chasing

    Authors:
    Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak, Christian Coester, Lukasz Jez, Elias Koutsoupias
    Conference:
    44th International Symposium on Mathematical Foundations of Computer Science (MFCS) (year: 2019, pages: 8:1-8:13), Publisher: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik
    Date:
    conference 26-30 sierpnia 2019
    Status:
    Published

  8. Hardness of exact distance queries in sparse graphs through hub labeling

    Authors:
    Adrian Kosowski, Przemysław Uznański, Laurent Viennot
    Conference:
    38th ACM Symposium on Principles of Distributed Computing (PODC) (year: 2019, pages: 272-279), Publisher: Association for Computing Machinery (ACM)
    Date:
    conference 29 lipca - 2 sierpnia 2019
    Status:
    Published

  9. An Improved Online Algorithm for the Traveling Repairperson Problem on a Line

    Authors:
    Marcin Bienkowski, Hsiang-Hsuan Liu
    Conference:
    44th International Symposium on Mathematical Foundations of Computer Science (MFCS) (year: 2019, pages: 6:1-6:12), Publisher: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik
    Date:
    conference 26-30 sierpnia 2019
    Status:
    Published

  10. Scheduling Opportunistic Links in Two-Tiered Reconfigurable Datacenters

    Authors:
    Janardhan Kulkarni, Stefan Schmid, Paweł Schmidt
    Conference:
    33rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) (year: 2021, pages: 318-327), Publisher: Association for Computing Machinery (ACM)
    Date:
    conference 6-8 lipca 2021
    Status:
    Published

  11. An Optimal Algorithm for Online Multiple Knapsack

    Authors:
    Marcin Bienkowski, Maciej Pacut, Krzysztof Piecuch
    Conference:
    47th International Colloquium on Automata, Languages and Programming (ICALP) (year: 2020, pages: 13:1-13:17), Publisher: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik
    Date:
    conference 8-11 lipca 2020
    Status:
    Published

  12. Improved Analysis of Online Balanced Clustering

    Authors:
    Marcin Bienkowski, Martin Böhm, Martin Koutecký, Thomas Rothvoß, Jiřı́ Sgall, Pavel Veselý
    Conference:
    Approximation and Online Algorithms - 19th International Workshop (WAOA) (year: 2021, pages: 224–233), Publisher: Springer International Publishing
    Date:
    conference 9-10 września 2021
    Status:
    Published

  13. Slaying Hydrae: Improved Bounds for Generalized k-Server in Uniform Metrics

    Authors:
    Marcin Bienkowski, Lukasz Jez, Pawel Schmidt
    Conference:
    30th International Symposium on Algorithms and Computation (ISAAC) (year: 2019, pages: 14:1-14:14), Publisher: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik
    Date:
    conference 9-11 grudnia 2019
    Status:
    Published

  14. A Nearly Optimal Deterministic Online Algorithm for Non-Metric Facility Location

    Authors:
    Marcin Bienkowski, Björn Feldkord, Paweł Schmidt
    Conference:
    38th International Symposium on Theoretical Aspects of Computer Science (STACS) (year: 2021, pages: 14:1-14:17), Publisher: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik
    Date:
    conference 16-19 marca 2021
    Status:
    Published

  15. A Deterministic Algorithm for Online Steiner Tree Leasing

    Authors:
    Marcin Bienkowski, Artur Kraska, Paweł Schmidt
    Conference:
    15th Algorithms and Data Structures Symposium (WADS) (year: 2017, pages: 169-180), Publisher: Springer International Publishing
    Date:
    conference 31 lipca - 2 sierpnia 2017
    Status:
    Published

  16. Dynamic beats fixed: On phase-based algorithms for file migration

    Authors:
    Marcin Bienkowski, Jarosław Byrka, Marcin Mucha
    Conference:
    44th Int. Colloq. on Automata, Languages, and Programming (ICALP) (year: 2017, pages: 13:1-13:14), Publisher: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik
    Date:
    conference 10-14 lipca 2017
    Status:
    Published

  17. Unbounded lower bound for k-server against weak adversaries

    Authors:
    Marcin Bienkowski, Jarosław Byrka, Christian Coester, Łukasz Jeż
    Conference:
    52nd Annual ACM Symposium on Theory of Computing (STOC) (year: 2020, pages: 1165-1169), Publisher: Association for Computing Machinery (ACM)
    Date:
    conference 22-26 czerwca 2020
    Status:
    Published

  18. Online Tree Caching

    Authors:
    Marcin Bienkowski, Jan Marcinkowski, Maciej Pacut, Stefan Schmid, Aleksandra Spyra
    Conference:
    29th ACM Symp. on Parallelism in Algorithms and Architectures (SPAA) (year: 2017, pages: 329-338), Publisher: Association for Computing Machinery (ACM)
    Date:
    conference 24-26 lipca 2017
    Status:
    Published

  19. Complexity and Online Algorithms for Minimum Skyline Coloring of Intervals

    Authors:
    Thomas Erlebach, Fu-Hong Liu, Hsiang-Hsuan Liu, Mordechai Shalom, Prudence W.H. Wong, Shmuel Zaks
    Conference:
    11th Int. Conf. on Combinatorial Optimization and Applications (COCOA), (year: 2017, pages: 317-332), Publisher: Springer International Publishing
    Date:
    conference 16-18 grudnia 2017
    Status:
    Published

  20. Online service with delay on a line

    Authors:
    Marcin Bienkowski, Artur Kraska, Paweł Schmidt
    Conference:
    25th International Colloquium on Structural Information and Communication Complexity (SIROCCO) (year: 2018, pages: 237-248), Publisher: Springer International Publishing
    Date:
    conference 18-21 czerwca 2018
    Status:
    Published

  21. A Primal-Dual Online Deterministic Algorithm for Matching with Delays

    Authors:
    Marcin Bienkowski, Artur Kraska, Hsiang-Hsuan Liu, Paweł Schmidt
    Conference:
    Approximation and Online Algorithms - 16th International Workshop (WAOA) (year: 2018, pages: 51-68), Publisher: Springer International Publishing
    Date:
    conference 23–24 sierpnia 2018
    Status:
    Published

  22. A φ-Competitive Algorithm for Scheduling Packets with Deadlines

    Authors:
    Pavel Veselý, Marek Chrobak, Łukasz Jeż, Jiří Sgall
    Conference:
    30th ACM-SIAM Symposium on Discrete Algorithms (SODA) (year: 2019, pages: 123–142), Publisher: Society for Industrial and Applied Mathematics (SIAM)
    Date:
    conference 6-9 stycznia 2019
    Status:
    Published

  23. A Match in Time Saves Nine: Deterministic Online Matching With Delay

    Authors:
    Marcin Bienkowski, Artur Kraska, Paweł Schmidt
    Conference:
    15th Workshop on Approximation and Online Algorithms (WAOA) (year: 2017, pages: 132-146), Publisher: Springer International Publishing
    Date:
    conference 7-8 września 2017
    Status:
    Published

« New search

Graphic design and implementation: Jakub Piotrowski