Algorithmic fundamentals of supply chain networks

2015/18/E/ST6/00456

Keywords

Descriptors

  • ST1_17: Teoria sterowania i optymalizacja
  • 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. Jarosław Byrka

Number of co-investigators in the project: 5

Call

SONATA BIS 5 – announced on 2015-06-15

Amount awarded
1 494 600 PLN
Project start date
2016-04-12
Project end date
2021-10-11
Project duration
66 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.

Equipment purchased [PL]

  1. Komputery przenośne (laptopy). Cost: 20 000 PLN
  2. Servwer obliczeniowy. Cost: 25 000 PLN

Information in the final report

Publication in academic press/journals (7)

  1. Online Algorithms for Multilevel Aggregation

    Authors:
    Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Marek Chrobak, Christoph Dürr, Lukas Folwarczny, Lukasz Jez, Jirí Sgall, Nguyen Kim Thang, Pavel Veselý
    Academic press:
    Operations Research (year: 2020, volume: 68(1), pages: 214-232), Publisher: INFORMS
    Status:
    Published
    DOI:
    10.1287/opre.2019.1847 – link to the publication
  2. Approximating Node-Weighted-MSTon Planar Graphs

    Authors:
    Jarosław Byrka, Mateusz Lewandowski, Joachim Spoerhase
    Academic press:
    Theory of Computing Systems (year: 2020, volume: 64, pages: 626644), Publisher: Springer
    Status:
    Published
    DOI:
    10.1007/s00224-020-09965-w – 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: ACM
    Status:
    Published
    DOI:
    10.1145/3453953.3453976 – link to the publication
  4. New results on multi-level aggregation

    Authors:
    Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Marek Chrobak, Christoph Dürr, Lukáš Folwarczný, Łukasz Jeża, 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
  5. Approximation Algorithms for Stochastic and Risk-Averse Optimization

    Authors:
    Jaroslaw Byrka and Aravind Srinivasan
    Academic press:
    SIAM Journal on Discrete Mathematics (year: 2018, volume: 32(1), pages: 44–63), Publisher: Society for Industrial and Applied Mathematics
    Status:
    Published
    DOI:
    10.1137/15M1043790 – link to the publication
  6. Dynamic Beats Fixed: On Phase-based Algorithms for File Migration

    Authors:
    Marcin Bienkowski, Jarosław Byrka, Marcin Mucha
    Academic press:
    ACM Transactions on Algorithms (year: 2019, volume: 15, pages: 46043), Publisher: ACM
    Status:
    Published
    DOI:
    10.1145/3340296 – link to the publication
  7. An Improved Approximation Algorithm for Knapsack Median Using Sparsification

    Authors:
    Jarosław Byrka, Thomas Pensyl, Bartosz Rybicki, Joachim Spoerhase, Aravind Srinivasan, Khoa Trinh
    Academic press:
    Algorithmica (year: 2018, volume: 80, pages: 1093–1114), Publisher: Springer
    Status:
    Published
    DOI:
    10.1007/s00453-017-0294-4 – link to the publication

Articles in post-conference publications (18)

  1. Dynamic Beats Fixed: On Phase-Based Algorithms for File Migration

    Authors:
    Marcin Bienkowski and Jaroslaw Byrka and Marcin Mucha
    Conference:
    44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) (year: 2017, pages: 13:1--13:14), Publisher: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
    Date:
    conference 10-14.07
    Status:
    Published
  2. Approximation Algorithms for Node-Weighted Prize-Collecting Steiner Tree Problems on Planar Graphs

    Authors:
    Jarosław Byrka, Mateusz Lewandowski, Carsten Moldenhauer
    Conference:
    15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). (year: 2016, pages: 2:1 - 2:14), Publisher: LIPIcs–Leibniz International Proceedings in Informatics
    Date:
    conference 22-24.06
    Status:
    Published
  3. Approximation Schemes for Geometric Coverage Problems

    Authors:
    Chaplick, Steven ; De, Minati ; Ravsky, Alexander ; Spoerhase, Joachim
    Conference:
    European Symposium on Algorithms (ESA 2018) (year: 2018, pages: 17:1--17:15), Publisher: Schloss Dagstuhl--Leibniz- Zentrum fuer Informatik (LIPIcs)
    Date:
    conference 20-24.08
    Status:
    Published
  4. A 4/5 - Approximation Algorithm for the Maximum Traveling Salesman Problem

    Authors:
    Szymon Dudycz, Jan Marcinkowski, Katarzyna Paluch, Bartosz Rybicki
    Conference:
    IPCO 2017: Integer Programming and Combinatorial Optimization (year: 2017, pages: 173-185), Publisher: Springer
    Date:
    conference 26-28-06
    Status:
    Published
  5. 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, and Pavel Veselý
    Conference:
    24th Annual European Symposium on Algorithms (ESA 2016) (year: 2016, pages: 12:1 - 12:17), Publisher: LIPIcs–Leibniz International Proceedings in Informatics
    Date:
    conference 22-24.08
    Status:
    Published
  6. Tight Inapproximability of Minimum Maximal Matching on Bipartite Graphs and Related Problems

    Authors:
    Szymon Dudycz, Pasin Manurangsi, Jan Marcinkowski
    Conference:
    WAOA 2021: Workshop on Approximation and Online Algorithms (year: 2021, pages: 48-64), Publisher: Springer
    Date:
    conference 9-10.09
    Status:
    Published
  7. Tight Approximation for Proportional Approval Voting

    Authors:
    Szymon Dudycz, Pasin Manurangsi, Jan Marcinkowski and Krzysztof Sornat
    Conference:
    Twenty-Ninth International Joint Conference on Artificial Intelligence (IJCAI-20) (year: 2020, pages: 276-282), Publisher: International Joint Conferences on Artificial Intelligence
    Date:
    conference 9-15.07
    Status:
    Published
  8. Concave Connection Cost Facility Location and the Star Inventory Routing Problem

    Authors:
    Jaroslaw Byrka, Mateusz Lewandowski
    Conference:
    International Workshop on Approximation and Online Algorithms WAOA 2020 (year: 2020, pages: 174-188), Publisher: Springer
    Date:
    conference 9-10.09
    Status:
    Published
  9. PTAS for Steiner Tree on Map Graphs

    Authors:
    Jaroslaw Byrka, Mateusz Lewandowski, Syed Mohammad Meesum, Joachim Spoerhase, Sumedha Uniyal
    Conference:
    LATIN 2020: Latin American Symposium on Theoretical Informatics (year: 2020, pages: 46095), Publisher: Springer
    Date:
    conference 5-8.01.2021
    Status:
    Published
  10. Breaching the 2-approximation barrier for connectivity augmentation: a reduction to Steiner tree

    Authors:
    Jaroslaw Byrka, Fabrizio Grandoni, Afrouz Jabal Ameli
    Conference:
    STOC 2020: The 52nd Annual ACM SIGACT Symposium on Theory of Computing (year: 2020, pages: 815–825), Publisher: ACM
    Date:
    conference 22-26.06
    Status:
    Published
  11. Unbounded lower bound for k-server against weak adversaries

    Authors:
    Marcin Bienkowski, Jaroslaw Byrka, Christian Coester, Lukasz Jez
    Conference:
    STOC 2020: The 52nd Annual ACM SIGACT Symposium on Theory of Computing (year: 2020, pages: 1165–1169), Publisher: ACM
    Date:
    conference 22-26.06
    Status:
    Published
  12. Better Bounds for Online Line Chasing

    Authors:
    Bienkowski, Marcin ; Byrka, Jaroslaw ; Chrobak, Marek ; Coester, Christian ; Jez, Lukasz ; Koutsoupias, Elias
    Conference:
    44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) (year: 2019, pages: 8:1--8:13), Publisher: Leibniz International Proceedings in Informatics (LIPIcs)
    Date:
    conference 43703
    Status:
    Published
  13. Proportional Approval Voting, Harmonic k- median, and Negative Association

    Authors:
    Byrka, Jaroslaw ; Skowron, Piotr ; Sornat, Krzysztof
    Conference:
    45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) (year: 2018, pages: 26:1--26:14), Publisher: Schloss Dagstuhl--Leibniz- Zentrum fuer Informatik (LIPIcs)
    Date:
    conference 9-13.07
    Status:
    Published
  14. Tight Approximation Ratio for Minimum Maximal Matching

    Authors:
    Szymon Dudycz, Mateusz Lewandowski, Jan Marcinkowski
    Conference:
    International Conference on Integer Programming and Combinatorial Optimization (IPCO) (year: 2019, pages: 181-193), Publisher: Springer
    Date:
    conference 43518
    Status:
    Published
  15. Constant-factor approximation for ordered k- median

    Authors:
    Jaroslaw Byrka, Krzysztof Sornat, Joachim Spoerhase
    Conference:
    50th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2018) (year: 2018, pages: 620--631), Publisher: ACM
    Date:
    conference 25-29.06
    Status:
    Published
  16. Constant-Factor FPT Approximation for Capacitated k-Median

    Authors:
    Marek Adamczyk, Jaroslaw Byrka, Jan Marcinkowski, Syed Mohammad Meesum, Michal Wlodarczyk
    Conference:
    European Symposium on Algorithms (ESA) (year: 2019, pages: 1:1-1:14), Publisher: Leibniz International Proceedings in Informatics (LIPIcs)
    Date:
    conference 43721
    Status:
    Published
  17. An Efficiently Recognisable Subset of Hypergraphic Sequences

    Authors:
    Meesum, Syed Mohammad
    Conference:
    International Computing and Combinatorics Conference (COCOON 2018) (year: 2018, pages: 391--402), Publisher: Springer
    Date:
    conference 2-4.07.2018
    Status:
    Published
  18. Approximating Node-Weighted k-MST on Planar Graphs

    Authors:
    Jarosław Byrka, Mateusz Lewandowski, Joachim Spoerhase
    Conference:
    International Workshop on Approximation and Online Algorithms (WAOA 2018) (year: 2018, pages: 87--101), Publisher: Springer
    Date:
    conference 23-24.08
    Status:
    Published

« New search

Graphic design and implementation: Jakub Piotrowski