Projects funded by the NCN

Information on the principal investigator and host institution

Information of the project and the call

Keywords

Equipment

Delete all

Algorithmic online optimization for graph problems

2016/22/E/ST6/00499

Keywords:

online algorithms competitive analysis graphs

Descriptors:

  • ST6_6: Algorithms, parallel, distributed and network algorithms, algorithmic game theory

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

woj. 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 (Y-m-d): 2017-04-18

Project end date (Y-m-d): 2024-04-17

Project duration:: 60 months (the same as in the proposal)

Project status: Project completed

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)
  • Articles in post-conference publications (23)
  1. 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 (rok: 2018, tom: 26(1), strony: 591-604), Wydawca: Institute of Electrical and Electronics Engineers (IEEE)
    Status:
    Published
    DOI:
    10.1109/TNET.2017.2787419 - link to the publication
  2. A φ-Competitive Algorithm for Scheduling Packets with Deadlines
    Authors:
    Pavel Veselý, Marek Chrobak, Łukasz Jeż, Jiří Sgall
    Academic press:
    SIAM Journal on Computing (rok: 2022, tom: 51(5), strony: 1626-1691), Wydawca: Society for Industrial and Applied Mathematics (SIAM)
    Status:
    Published
    DOI:
    10.1137/21m1469753 - link to the publication
  3. 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 (rok: 2021, tom: 65(6), strony: 1009-1032), Wydawca: Springer International Publishing
    Status:
    Published
    DOI:
    10.1007/s00224-021-10037-w - link to the publication
  4. 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 (rok: 2019, tom: 15(2), strony: 28:1-28:26), Wydawca: Association for Computing Machinery (ACM)
    Status:
    Published
    DOI:
    10.1145/3301314 - link to the publication
  5. 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 (rok: 2021, tom: 861, strony: 133-143), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.tcs.2021.02.016 - link to the publication
  6. 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 (rok: 2018, tom: 14(2), strony: 21:1-21:22), Wydawca: Association for Computing Machinery (ACM)
    Status:
    Published
    DOI:
    10.1145/3182396 - link to the publication
  7. 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 (rok: 2019, tom: 788, strony: 66-78), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.tcs.2019.05.007 - 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 (rok: 2018, tom: 707, strony: 89-93), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.008 - link to the publication
  9. On packet scheduling with adversarial jamming and speedup
    Authors:
    Martin Böhm, Łukasz Jeż, Jiří Sgall, Pavel Veselý
    Academic press:
    Annals of Operations Research (rok: 2021, tom: 298, strony: 15523), Wydawca: Springer International Publishing
    Status:
    Published
    DOI:
    10.1007/s10479-019-03153-x - link to the publication
  10. 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 (rok: 2020, tom: 68(1), strony: 214-232), Wydawca: The Institute for Operations Research and the Management Sciences (INFORMS)
    Status:
    Published
    DOI:
    10.1287/opre.2019.1847 - link to the publication
  11. Dynamic Beats Fixed: On Phase-based Algorithms for File Migration
    Authors:
    Marcin Bienkowski, Jaroslaw Byrka, Marcin Mucha
    Academic press:
    ACM Transactions on Algorithms (rok: 2019, tom: 15(4), strony: 46:1-46:21), Wydawca: Association for Computing Machinery (ACM)
    Status:
    Published
    DOI:
    10.1145/3340296 - link to the publication
  12. Dynamic Balanced Graph Partitioning
    Authors:
    Chen Avin, Marcin Bienkowski, Andreas Loukas, Maciej Pacut, Stefan Schmid
    Academic press:
    SIAM Journal on Discrete Mathematics (rok: 2020, tom: 34(3), strony: 1791-1812), Wydawca: Society for Industrial and Applied Mathematics (SIAM)
    Status:
    Published
    DOI:
    10.1137/17M1158513 - link to the publication
  13. 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 (rok: 2020, tom: 48(3), strony: 99-108), Wydawca: Association for Computing Machinery (ACM)
    Status:
    Published
    DOI:
    10.1145/3453953.3453976 - link to the publication
  1. 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) (rok: 2022, ), Wydawca: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 19-21 września 2022
    Status:
    Published
  2. 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) (rok: 2021, ), Wydawca: Association for Computing Machinery (ACM)
    Data:
    konferencja 6-8 lipca 2021
    Status:
    Published
  3. 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) (rok: 2019, ), Wydawca: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 9-11 grudnia 2019
    Status:
    Published
  4. 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) (rok: 2020, ), Wydawca: Association for Computing Machinery (ACM)
    Data:
    konferencja 22-26 czerwca 2020
    Status:
    Published
  5. 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) (rok: 2017, ), Wydawca: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 10-14 lipca 2017
    Status:
    Published
  6. 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) (rok: 2019, ), Wydawca: Association for Computing Machinery (ACM)
    Data:
    konferencja 29 lipca - 2 sierpnia 2019
    Status:
    Published
  7. 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) (rok: 2017, ), Wydawca: Association for Computing Machinery (ACM)
    Data:
    konferencja 24-26 lipca 2017
    Status:
    Published
  8. An Improved Algorithm For Online Min-Sum Set Cover
    Authors:
    Marcin Bienkowski, Marcin Mucha
    Conference:
    37th AAAI Conference on Artificial Intelligence (AAAI) (rok: 2023, ), Wydawca: Association for the Advancement of Artificial Intelligence (AAAI)
    Data:
    konferencja 7-14 lutego 2023
    Status:
    Published
  9. 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) (rok: 2021, ), Wydawca: Springer International Publishing
    Data:
    konferencja 9-10 września 2021
    Status:
    Published
  10. 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) (rok: 2019, ), Wydawca: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 20-22 września 2019
    Status:
    Published
  11. 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) (rok: 2021, ), Wydawca: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 12-16 lipca 2021
    Status:
    Published
  12. An Optimal Algorithm for Online Multiple Knapsack
    Authors:
    Marcin Bienkowski, Maciej Pacut, Krzysztof Piecuch
    Conference:
    47th International Colloquium on Automata, Languages and Programming (ICALP) (rok: 2020, ), Wydawca: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 8-11 lipca 2020
    Status:
    Published
  13. 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) (rok: 2018, ), Wydawca: Springer International Publishing
    Data:
    konferencja 23–24 sierpnia 2018
    Status:
    Published
  14. 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) (rok: 2018, ), Wydawca: Springer International Publishing
    Data:
    konferencja 18-21 czerwca 2018
    Status:
    Published
  15. 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) (rok: 2019, ), Wydawca: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 26-30 sierpnia 2019
    Status:
    Published
  16. 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) (rok: 2021, ), Wydawca: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 16-19 marca 2021
    Status:
    Published
  17. 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) (rok: 2017, ), Wydawca: Springer International Publishing
    Data:
    konferencja 7-8 września 2017
    Status:
    Published
  18. 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) (rok: 2019, ), Wydawca: Society for Industrial and Applied Mathematics (SIAM)
    Data:
    konferencja 6-9 stycznia 2019
    Status:
    Published
  19. 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) (rok: 2022, ), Wydawca: Institute of Electrical and Electronics Engineers (IEEE)
    Data:
    konferencja 10-13 lipca 2022
    Status:
    Published
  20. 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) (rok: 2019, ), Wydawca: Springer International Publishing
    Data:
    konferencja 12-13 września 2019
    Status:
    Published
  21. 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), (rok: 2017, ), Wydawca: Springer International Publishing
    Data:
    konferencja 16-18 grudnia 2017
    Status:
    Published
  22. A Deterministic Algorithm for Online Steiner Tree Leasing
    Authors:
    Marcin Bienkowski, Artur Kraska, Paweł Schmidt
    Conference:
    15th Algorithms and Data Structures Symposium (WADS) (rok: 2017, ), Wydawca: Springer International Publishing
    Data:
    konferencja 31 lipca - 2 sierpnia 2017
    Status:
    Published
  23. 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) (rok: 2019, ), Wydawca: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 26-30 sierpnia 2019
    Status:
    Published

O Narodowym Centrum Nauki

Finansowanie nauki

Współpraca zagraniczna

Centrum prasowe

Deklaracja dostępności
Przetwarzanie danych osobowych
Polityka cookies

Partnerzy