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 fundamentals of supply chain networks

2015/18/E/ST6/00456

Keywords:

Combinatorial optimization aggregation approximation algorithms

Descriptors:

  • ST1_17: Applied mathematics
  • 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. 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 (Y-m-d): 2016-04-12

Project end date (Y-m-d): 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) (20 000 PLN)
  2. Servwer obliczeniowy (25 000 PLN)

Information in the final report

  • Publication in academic press/journals (7)
  • Articles in post-conference publications (18)
  1. 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: ACM
    Status:
    Published
    DOI:
    10.1145/3453953.3453976 - link to the publication
  2. 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 (rok: 2018, tom: 80, strony: 1093–1114), Wydawca: Springer
    Status:
    Published
    DOI:
    10.1007/s00453-017-0294-4 - link to the publication
  3. 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 (rok: 2021, tom: 861, strony: 133-143), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.tcs.2021.02.016 - link to the publication
  4. Approximation Algorithms for Stochastic and Risk-Averse Optimization
    Authors:
    Jaroslaw Byrka and Aravind Srinivasan
    Academic press:
    SIAM Journal on Discrete Mathematics (rok: 2018, tom: 32(1), strony: 44–63), Wydawca: Society for Industrial and Applied Mathematics
    Status:
    Published
    DOI:
    10.1137/15M1043790 - link to the publication
  5. Dynamic Beats Fixed: On Phase-based Algorithms for File Migration
    Authors:
    Marcin Bienkowski, Jarosław Byrka, Marcin Mucha
    Academic press:
    ACM Transactions on Algorithms (rok: 2019, tom: 15, strony: 45312), Wydawca: ACM
    Status:
    Published
    DOI:
    10.1145/3340296 - link to the publication
  6. Approximating Node-Weighted-MSTon Planar Graphs
    Authors:
    Jarosław Byrka, Mateusz Lewandowski, Joachim Spoerhase
    Academic press:
    Theory of Computing Systems (rok: 2020, tom: 64, strony: 626644), Wydawca: Springer
    Status:
    Published
    DOI:
    10.1007/s00224-020-09965-w - link to the publication
  7. 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 (rok: 2020, tom: 68(1), strony: 214-232), Wydawca: INFORMS
    Status:
    Published
    DOI:
    10.1287/opre.2019.1847 - link to the publication
  1. 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 (rok: 2017, ), Wydawca: Springer
    Data:
    konferencja 26-28-06
    Status:
    Published
  2. An Efficiently Recognisable Subset of Hypergraphic Sequences
    Authors:
    Meesum, Syed Mohammad
    Conference:
    International Computing and Combinatorics Conference (COCOON 2018) (rok: 2018, ), Wydawca: Springer
    Data:
    konferencja 2-4.07.2018
    Status:
    Published
  3. 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) (rok: 2019, ), Wydawca: Leibniz International Proceedings in Informatics (LIPIcs)
    Data:
    konferencja 43703
    Status:
    Published
  4. 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) (rok: 2016, ), Wydawca: LIPIcs–Leibniz International Proceedings in Informatics
    Data:
    konferencja 22-24.08
    Status:
    Published
  5. Tight Approximation Ratio for Minimum Maximal Matching
    Authors:
    Szymon Dudycz, Mateusz Lewandowski, Jan Marcinkowski
    Conference:
    International Conference on Integer Programming and Combinatorial Optimization (IPCO) (rok: 2019, ), Wydawca: Springer
    Data:
    konferencja 43518
    Status:
    Published
  6. 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). (rok: 2016, ), Wydawca: LIPIcs–Leibniz International Proceedings in Informatics
    Data:
    konferencja 22-24.06
    Status:
    Published
  7. 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 (rok: 2020, ), Wydawca: ACM
    Data:
    konferencja 22-26.06
    Status:
    Published
  8. 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) (rok: 2018, ), Wydawca: Schloss Dagstuhl--Leibniz- Zentrum fuer Informatik (LIPIcs)
    Data:
    konferencja 9-13.07
    Status:
    Published
  9. 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) (rok: 2019, ), Wydawca: Leibniz International Proceedings in Informatics (LIPIcs)
    Data:
    konferencja 43721
    Status:
    Published
  10. 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 (rok: 2020, ), Wydawca: ACM
    Data:
    konferencja 22-26.06
    Status:
    Published
  11. 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) (rok: 2018, ), Wydawca: Springer
    Data:
    konferencja 23-24.08
    Status:
    Published
  12. 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 (rok: 2020, ), Wydawca: Springer
    Data:
    konferencja 5-8.01.2021
    Status:
    Published
  13. 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) (rok: 2020, ), Wydawca: International Joint Conferences on Artificial Intelligence
    Data:
    konferencja 9-15.07
    Status:
    Published
  14. 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 (rok: 2021, ), Wydawca: Springer
    Data:
    konferencja 9-10.09
    Status:
    Published
  15. Approximation Schemes for Geometric Coverage Problems
    Authors:
    Chaplick, Steven ; De, Minati ; Ravsky, Alexander ; Spoerhase, Joachim
    Conference:
    European Symposium on Algorithms (ESA 2018) (rok: 2018, ), Wydawca: Schloss Dagstuhl--Leibniz- Zentrum fuer Informatik (LIPIcs)
    Data:
    konferencja 20-24.08
    Status:
    Published
  16. 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 (rok: 2020, ), Wydawca: Springer
    Data:
    konferencja 9-10.09
    Status:
    Published
  17. 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) (rok: 2018, ), Wydawca: ACM
    Data:
    konferencja 25-29.06
    Status:
    Published
  18. 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) (rok: 2017, ), Wydawca: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 10-14.07
    Status:
    Published

O Narodowym Centrum Nauki

Finansowanie nauki

Współpraca zagraniczna

Centrum prasowe

Deklaracja dostępności
Przetwarzanie danych osobowych
Polityka cookies

Partnerzy