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
Principal investigator (from the host institution)
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]
- Komputery przenośne (laptopy). Cost: 20 000 PLN
- Servwer obliczeniowy. Cost: 25 000 PLN
Information in the final report
Publication in academic press/journals (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 (year: 2020, volume: 68(1), pages: 214-232), Publisher: INFORMS
- Status:
- Published
- DOI:
- 10.1287/opre.2019.1847 – link to the publication
-
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
-
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
-
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
-
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
-
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
-
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)
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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