Projekty finansowane przez NCN

Dane kierownika projektu i jednostki realizującej

Szczegółowe informacje o projekcie i konkursie

Słowa kluczowe

Aparatura

Wyczyść formularz

Algorytmiczna optymalizacja online dla problemów grafowych

2016/22/E/ST6/00499

Słowa kluczowe:

algorytmy online analiza konkurencyjna grafy

Deskryptory:

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

Panel:

ST6 - Informatyka i technologie informacyjne: technologie i systemy informacyjne, informatyka, obliczenia naukowe, systemy inteligentne

Jednostka realizująca:

Uniwersytet Wrocławski, Wydział Matematyki i Informatyki

woj. dolnośląskie

Inne projekty tej jednostki 

Kierownik projektu (z jednostki realizującej):

dr hab. Marcin Bieńkowski 

Liczba wykonawców projektu: 5

Konkurs: SONATA BIS 6 - ogłoszony 2016-06-15

Przyznana kwota: 1 225 850 PLN

Rozpoczęcie projektu: 2017-04-18

Zakończenie projektu: 2024-04-17

Planowany czas trwania projektu: 60 miesięcy (z wniosku)

Status projektu: Projekt zakończony

Opis Projektu

Pobierz opis projektu w formacie .pdf

Uwaga - opisy projektów zostały sporządzone przez samych autorów wniosków i w niezmienionej formie umieszczone w systemie.

Dane z raportu końcowego/rocznego

  • Publikacje w czasopismach (13)
  • Teksty w publikacjach pokonferencyjnych (23)
  1. Online Aggregation of the Forwarding Information Base: Accounting for Locality and Churn
    Autorzy:
    Marcin Bienkowski, Nadi Sarrar, Stefan Schmid, Steve Uhlig
    Czasopismo:
    IEEE/ACM Transactions on Networking (rok: 2018, tom: 26(1), strony: 591-604), Wydawca: Institute of Electrical and Electronics Engineers (IEEE)
    Status:
    Opublikowana
    Doi:
    10.1109/TNET.2017.2787419 - link do publikacji
  2. A φ-Competitive Algorithm for Scheduling Packets with Deadlines
    Autorzy:
    Pavel Veselý, Marek Chrobak, Łukasz Jeż, Jiří Sgall
    Czasopismo:
    SIAM Journal on Computing (rok: 2022, tom: 51(5), strony: 1626-1691), Wydawca: Society for Industrial and Applied Mathematics (SIAM)
    Status:
    Opublikowana
    Doi:
    10.1137/21m1469753 - link do publikacji
  3. Greedy is Optimal for Online Restricted Assignment and Smart Grid Scheduling for Unit Size Jobs
    Autorzy:
    Fu-Hong Liu, Hsiang-Hsuan Liu, Prudence W. H. Wong
    Czasopismo:
    Theory of Computing Systems (rok: 2021, tom: 65(6), strony: 1009-1032), Wydawca: Springer International Publishing
    Status:
    Opublikowana
    Doi:
    10.1007/s00224-021-10037-w - link do publikacji
  4. The (h,k)-Server Problem on Bounded Depth Trees
    Autorzy:
    Nikhil Bansal, Marek Eliás, Lukasz Jez, Grigorios Koumoutsos
    Czasopismo:
    ACM Transactions on Algorithms (rok: 2019, tom: 15(2), strony: 28:1-28:26), Wydawca: Association for Computing Machinery (ACM)
    Status:
    Opublikowana
    Doi:
    10.1145/3301314 - link do publikacji
  5. New Results on Multi-Level Aggregation
    Autorzy:
    Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Marek Chrobak, Christoph Dürr, Lukáš Folwarczný, Łukasz Jeż, Jiří Sgall, Nguyen Kim Thang, Pavel Veselý
    Czasopismo:
    Theoretical Computer Science (rok: 2021, tom: 861, strony: 133-143), Wydawca: Elsevier
    Status:
    Opublikowana
    Doi:
    10.1016/j.tcs.2021.02.016 - link do publikacji
  6. Distributed Online and Stochastic Queuing on a Multiple Access Channel
    Autorzy:
    Marcin Bienkowski, Tomasz Jurdzinski, Miroslaw Korzeniowski, Dariusz R. Kowalski
    Czasopismo:
    Transactions on Algorithms (rok: 2018, tom: 14(2), strony: 21:1-21:22), Wydawca: Association for Computing Machinery (ACM)
    Status:
    Opublikowana
    Doi:
    10.1145/3182396 - link do publikacji
  7. Complexity and online algorithms for minimum skyline coloring of intervals
    Autorzy:
    Thomas Erlebach, Fu-Hong Liu, Hsiang-Hsuan Liu, Mordechai Shalom, Prudence W. H. Wong, Shmuel Zaks
    Czasopismo:
    Theoretical Computer Science (rok: 2019, tom: 788, strony: 66-78), Wydawca: Elsevier
    Status:
    Opublikowana
    Doi:
    10.1016/j.tcs.2019.05.007 - link do publikacji
  8. Logarithmic price of buffer downscaling on line metrics
    Autorzy:
    Marcin Bienkowski, Martin Böhm, Łukasz Jeż, Paweł Laskoś-Grabowski, Jan Marcinkowski, Jirí Sgall, Aleksandra Spyra, Pavel Veselý
    Czasopismo:
    Theoretical Computer Science (rok: 2018, tom: 707, strony: 89-93), Wydawca: Elsevier
    Status:
    Opublikowana
    Doi:
    10.008 - link do publikacji
  9. On packet scheduling with adversarial jamming and speedup
    Autorzy:
    Martin Böhm, Łukasz Jeż, Jiří Sgall, Pavel Veselý
    Czasopismo:
    Annals of Operations Research (rok: 2021, tom: 298, strony: 15523), Wydawca: Springer International Publishing
    Status:
    Opublikowana
    Doi:
    10.1007/s10479-019-03153-x - link do publikacji
  10. Online Algorithms for Multi-Level Aggregation
    Autorzy:
    Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Marek Chrobak, Christoph Dürr, Lukáš Folwarczný, Łukasz Jeż, Jiří Sgall, Nguyen Kim Thang, Pavel Veselý
    Czasopismo:
    Operations Research (rok: 2020, tom: 68(1), strony: 214-232), Wydawca: The Institute for Operations Research and the Management Sciences (INFORMS)
    Status:
    Opublikowana
    Doi:
    10.1287/opre.2019.1847 - link do publikacji
  11. Dynamic Beats Fixed: On Phase-based Algorithms for File Migration
    Autorzy:
    Marcin Bienkowski, Jaroslaw Byrka, Marcin Mucha
    Czasopismo:
    ACM Transactions on Algorithms (rok: 2019, tom: 15(4), strony: 46:1-46:21), Wydawca: Association for Computing Machinery (ACM)
    Status:
    Opublikowana
    Doi:
    10.1145/3340296 - link do publikacji
  12. Dynamic Balanced Graph Partitioning
    Autorzy:
    Chen Avin, Marcin Bienkowski, Andreas Loukas, Maciej Pacut, Stefan Schmid
    Czasopismo:
    SIAM Journal on Discrete Mathematics (rok: 2020, tom: 34(3), strony: 1791-1812), Wydawca: Society for Industrial and Applied Mathematics (SIAM)
    Status:
    Opublikowana
    Doi:
    10.1137/17M1158513 - link do publikacji
  13. Online Dynamic B-Matching With Applications to Reconfigurable Datacenter Networks
    Autorzy:
    Marcin Bienkowski, David Fuchssteiner, Jan Marcinkowski, Stefan Schmid
    Czasopismo:
    ACM SIGMETRICS Performance Evaluation Review (rok: 2020, tom: 48(3), strony: 99-108), Wydawca: Association for Computing Machinery (ACM)
    Status:
    Opublikowana
    Doi:
    10.1145/3453953.3453976 - link do publikacji
  1. Online Facility Location with Linear Delay
    Autorzy:
    Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Jan Marcinkowski
    Konferencja:
    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:
    Opublikowana
  2. Scheduling Opportunistic Links in Two-Tiered Reconfigurable Datacenters
    Autorzy:
    Janardhan Kulkarni, Stefan Schmid, Paweł Schmidt
    Konferencja:
    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:
    Opublikowana
  3. Slaying Hydrae: Improved Bounds for Generalized k-Server in Uniform Metrics
    Autorzy:
    Marcin Bienkowski, Lukasz Jez, Pawel Schmidt
    Konferencja:
    30th International Symposium on Algorithms and Computation (ISAAC) (rok: 2019, ), Wydawca: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 9-11 grudnia 2019
    Status:
    Opublikowana
  4. Unbounded lower bound for k-server against weak adversaries
    Autorzy:
    Marcin Bienkowski, Jarosław Byrka, Christian Coester, Łukasz Jeż
    Konferencja:
    52nd Annual ACM Symposium on Theory of Computing (STOC) (rok: 2020, ), Wydawca: Association for Computing Machinery (ACM)
    Data:
    konferencja 22-26 czerwca 2020
    Status:
    Opublikowana
  5. Dynamic beats fixed: On phase-based algorithms for file migration
    Autorzy:
    Marcin Bienkowski, Jarosław Byrka, Marcin Mucha
    Konferencja:
    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:
    Opublikowana
  6. Hardness of exact distance queries in sparse graphs through hub labeling
    Autorzy:
    Adrian Kosowski, Przemysław Uznański, Laurent Viennot
    Konferencja:
    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:
    Opublikowana
  7. Online Tree Caching
    Autorzy:
    Marcin Bienkowski, Jan Marcinkowski, Maciej Pacut, Stefan Schmid, Aleksandra Spyra
    Konferencja:
    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:
    Opublikowana
  8. An Improved Algorithm For Online Min-Sum Set Cover
    Autorzy:
    Marcin Bienkowski, Marcin Mucha
    Konferencja:
    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:
    Opublikowana
  9. Improved Analysis of Online Balanced Clustering
    Autorzy:
    Marcin Bienkowski, Martin Böhm, Martin Koutecký, Thomas Rothvoß, Jiřı́ Sgall, Pavel Veselý
    Konferencja:
    Approximation and Online Algorithms - 19th International Workshop (WAOA) (rok: 2021, ), Wydawca: Springer International Publishing
    Data:
    konferencja 9-10 września 2021
    Status:
    Opublikowana
  10. Dynamic Pricing of Servers on Trees
    Autorzy:
    Ilan Reuven Cohen, Alon Eden, Amos Fiat, Lukasz Jez
    Konferencja:
    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:
    Opublikowana
  11. Traveling Repairperson, Unrelated Machines, and Other Stories About Average Completion Times
    Autorzy:
    Marcin Bienkowski, Artur Kraska, Hsiang-Hsuan Liu
    Konferencja:
    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:
    Opublikowana
  12. An Optimal Algorithm for Online Multiple Knapsack
    Autorzy:
    Marcin Bienkowski, Maciej Pacut, Krzysztof Piecuch
    Konferencja:
    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:
    Opublikowana
  13. A Primal-Dual Online Deterministic Algorithm for Matching with Delays
    Autorzy:
    Marcin Bienkowski, Artur Kraska, Hsiang-Hsuan Liu, Paweł Schmidt
    Konferencja:
    Approximation and Online Algorithms - 16th International Workshop (WAOA) (rok: 2018, ), Wydawca: Springer International Publishing
    Data:
    konferencja 23–24 sierpnia 2018
    Status:
    Opublikowana
  14. Online service with delay on a line
    Autorzy:
    Marcin Bienkowski, Artur Kraska, Paweł Schmidt
    Konferencja:
    25th International Colloquium on Structural Information and Communication Complexity (SIROCCO) (rok: 2018, ), Wydawca: Springer International Publishing
    Data:
    konferencja 18-21 czerwca 2018
    Status:
    Opublikowana
  15. An Improved Online Algorithm for the Traveling Repairperson Problem on a Line
    Autorzy:
    Marcin Bienkowski, Hsiang-Hsuan Liu
    Konferencja:
    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:
    Opublikowana
  16. A Nearly Optimal Deterministic Online Algorithm for Non-Metric Facility Location
    Autorzy:
    Marcin Bienkowski, Björn Feldkord, Paweł Schmidt
    Konferencja:
    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:
    Opublikowana
  17. A Match in Time Saves Nine: Deterministic Online Matching With Delay
    Autorzy:
    Marcin Bienkowski, Artur Kraska, Paweł Schmidt
    Konferencja:
    15th Workshop on Approximation and Online Algorithms (WAOA) (rok: 2017, ), Wydawca: Springer International Publishing
    Data:
    konferencja 7-8 września 2017
    Status:
    Opublikowana
  18. A φ-Competitive Algorithm for Scheduling Packets with Deadlines
    Autorzy:
    Pavel Veselý, Marek Chrobak, Łukasz Jeż, Jiří Sgall
    Konferencja:
    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:
    Opublikowana
  19. Deterministic Self-Adjusting Tree Networks Using Rotor Walks
    Autorzy:
    Chen Avin, Marcin Bienkowski, Iosif Salem, Robert Sama, Stefan Schmid, Pawel Schmidt
    Konferencja:
    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:
    Opublikowana
  20. Greedy Is Optimal for Online Restricted Assignment and Smart Grid Scheduling for Unit Size Jobs
    Autorzy:
    Fu-Hong Liu, Hsiang-Hsuan Liu, Prudence W. H. Wong
    Konferencja:
    Approximation and Online Algorithms - 17th International Workshop (WAOA) (rok: 2019, ), Wydawca: Springer International Publishing
    Data:
    konferencja 12-13 września 2019
    Status:
    Opublikowana
  21. Complexity and Online Algorithms for Minimum Skyline Coloring of Intervals
    Autorzy:
    Thomas Erlebach, Fu-Hong Liu, Hsiang-Hsuan Liu, Mordechai Shalom, Prudence W.H. Wong, Shmuel Zaks
    Konferencja:
    11th Int. Conf. on Combinatorial Optimization and Applications (COCOA), (rok: 2017, ), Wydawca: Springer International Publishing
    Data:
    konferencja 16-18 grudnia 2017
    Status:
    Opublikowana
  22. A Deterministic Algorithm for Online Steiner Tree Leasing
    Autorzy:
    Marcin Bienkowski, Artur Kraska, Paweł Schmidt
    Konferencja:
    15th Algorithms and Data Structures Symposium (WADS) (rok: 2017, ), Wydawca: Springer International Publishing
    Data:
    konferencja 31 lipca - 2 sierpnia 2017
    Status:
    Opublikowana
  23. Better Bounds for Online Line Chasing
    Autorzy:
    Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak, Christian Coester, Lukasz Jez, Elias Koutsoupias
    Konferencja:
    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:
    Opublikowana

O Narodowym Centrum Nauki

Finansowanie nauki

Współpraca zagraniczna

Centrum prasowe

Deklaracja dostępności
Przetwarzanie danych osobowych
Polityka cookies

Partnerzy