Projekty finansowane przez NCN

Dane kierownika projektu i jednostki realizującej

Szczegółowe informacje o projekcie i konkursie

Słowa kluczowe

Aparatura

Wyczyść formularz

Algorytmiczne podstawy optymalizacji sieci logistycznych

2015/18/E/ST6/00456

Słowa kluczowe:

Optymalizacja kombinatoryczna agregacja algorytmy aproksymacyjne

Deskryptory:

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

Liczba wykonawców projektu: 5

Konkurs: SONATA BIS 5 - ogłoszony 2015-06-15

Przyznana kwota: 1 494 600 PLN

Rozpoczęcie projektu: 2016-04-12

Zakończenie projektu: 2021-10-11

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

Status projektu: Projekt rozliczony

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.

Zakupiona aparatura

  1. Komputery przenośne (laptopy). Za kwotę 20 000 PLN
  2. Servwer obliczeniowy. Za kwotę 25 000 PLN

Dane z raportu końcowego/rocznego

  • Publikacje w czasopismach (7)
  • Teksty w publikacjach pokonferencyjnych (18)
  1. 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: ACM
    Status:
    Opublikowana
    Doi:
    10.1145/3453953.3453976 - link do publikacji
  2. An Improved Approximation Algorithm for Knapsack Median Using Sparsification
    Autorzy:
    Jarosław Byrka, Thomas Pensyl, Bartosz Rybicki, Joachim Spoerhase, Aravind Srinivasan, Khoa Trinh
    Czasopismo:
    Algorithmica (rok: 2018, tom: 80, strony: 1093–1114), Wydawca: Springer
    Status:
    Opublikowana
    Doi:
    10.1007/s00453-017-0294-4 - link do publikacji
  3. New results on multi-level aggregation
    Autorzy:
    Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Marek Chrobak, Christoph Dürr, Lukáš Folwarczný, Łukasz Jeża, 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
  4. Approximation Algorithms for Stochastic and Risk-Averse Optimization
    Autorzy:
    Jaroslaw Byrka and Aravind Srinivasan
    Czasopismo:
    SIAM Journal on Discrete Mathematics (rok: 2018, tom: 32(1), strony: 44–63), Wydawca: Society for Industrial and Applied Mathematics
    Status:
    Opublikowana
    Doi:
    10.1137/15M1043790 - link do publikacji
  5. Dynamic Beats Fixed: On Phase-based Algorithms for File Migration
    Autorzy:
    Marcin Bienkowski, Jarosław Byrka, Marcin Mucha
    Czasopismo:
    ACM Transactions on Algorithms (rok: 2019, tom: 15, strony: 45312), Wydawca: ACM
    Status:
    Opublikowana
    Doi:
    10.1145/3340296 - link do publikacji
  6. Approximating Node-Weighted-MSTon Planar Graphs
    Autorzy:
    Jarosław Byrka, Mateusz Lewandowski, Joachim Spoerhase
    Czasopismo:
    Theory of Computing Systems (rok: 2020, tom: 64, strony: 626644), Wydawca: Springer
    Status:
    Opublikowana
    Doi:
    10.1007/s00224-020-09965-w - link do publikacji
  7. Online Algorithms for Multilevel Aggregation
    Autorzy:
    Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Marek Chrobak, Christoph Dürr, Lukas Folwarczny, Lukasz Jez, Jirí Sgall, Nguyen Kim Thang, Pavel Veselý
    Czasopismo:
    Operations Research (rok: 2020, tom: 68(1), strony: 214-232), Wydawca: INFORMS
    Status:
    Opublikowana
    Doi:
    10.1287/opre.2019.1847 - link do publikacji
  1. A 4/5 - Approximation Algorithm for the Maximum Traveling Salesman Problem
    Autorzy:
    Szymon Dudycz, Jan Marcinkowski, Katarzyna Paluch, Bartosz Rybicki
    Konferencja:
    IPCO 2017: Integer Programming and Combinatorial Optimization (rok: 2017, ), Wydawca: Springer
    Data:
    konferencja 26-28-06
    Status:
    Opublikowana
  2. An Efficiently Recognisable Subset of Hypergraphic Sequences
    Autorzy:
    Meesum, Syed Mohammad
    Konferencja:
    International Computing and Combinatorics Conference (COCOON 2018) (rok: 2018, ), Wydawca: Springer
    Data:
    konferencja 2-4.07.2018
    Status:
    Opublikowana
  3. Better Bounds for Online Line Chasing
    Autorzy:
    Bienkowski, Marcin ; Byrka, Jaroslaw ; Chrobak, Marek ; Coester, Christian ; Jez, Lukasz ; Koutsoupias, Elias
    Konferencja:
    44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) (rok: 2019, ), Wydawca: Leibniz International Proceedings in Informatics (LIPIcs)
    Data:
    konferencja 43703
    Status:
    Opublikowana
  4. 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, and Pavel Veselý
    Konferencja:
    24th Annual European Symposium on Algorithms (ESA 2016) (rok: 2016, ), Wydawca: LIPIcs–Leibniz International Proceedings in Informatics
    Data:
    konferencja 22-24.08
    Status:
    Opublikowana
  5. Tight Approximation Ratio for Minimum Maximal Matching
    Autorzy:
    Szymon Dudycz, Mateusz Lewandowski, Jan Marcinkowski
    Konferencja:
    International Conference on Integer Programming and Combinatorial Optimization (IPCO) (rok: 2019, ), Wydawca: Springer
    Data:
    konferencja 43518
    Status:
    Opublikowana
  6. Approximation Algorithms for Node-Weighted Prize-Collecting Steiner Tree Problems on Planar Graphs
    Autorzy:
    Jarosław Byrka, Mateusz Lewandowski, Carsten Moldenhauer
    Konferencja:
    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:
    Opublikowana
  7. Breaching the 2-approximation barrier for connectivity augmentation: a reduction to Steiner tree
    Autorzy:
    Jaroslaw Byrka, Fabrizio Grandoni, Afrouz Jabal Ameli
    Konferencja:
    STOC 2020: The 52nd Annual ACM SIGACT Symposium on Theory of Computing (rok: 2020, ), Wydawca: ACM
    Data:
    konferencja 22-26.06
    Status:
    Opublikowana
  8. Proportional Approval Voting, Harmonic k- median, and Negative Association
    Autorzy:
    Byrka, Jaroslaw ; Skowron, Piotr ; Sornat, Krzysztof
    Konferencja:
    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:
    Opublikowana
  9. Constant-Factor FPT Approximation for Capacitated k-Median
    Autorzy:
    Marek Adamczyk, Jaroslaw Byrka, Jan Marcinkowski, Syed Mohammad Meesum, Michal Wlodarczyk
    Konferencja:
    European Symposium on Algorithms (ESA) (rok: 2019, ), Wydawca: Leibniz International Proceedings in Informatics (LIPIcs)
    Data:
    konferencja 43721
    Status:
    Opublikowana
  10. Unbounded lower bound for k-server against weak adversaries
    Autorzy:
    Marcin Bienkowski, Jaroslaw Byrka, Christian Coester, Lukasz Jez
    Konferencja:
    STOC 2020: The 52nd Annual ACM SIGACT Symposium on Theory of Computing (rok: 2020, ), Wydawca: ACM
    Data:
    konferencja 22-26.06
    Status:
    Opublikowana
  11. Approximating Node-Weighted k-MST on Planar Graphs
    Autorzy:
    Jarosław Byrka, Mateusz Lewandowski, Joachim Spoerhase
    Konferencja:
    International Workshop on Approximation and Online Algorithms (WAOA 2018) (rok: 2018, ), Wydawca: Springer
    Data:
    konferencja 23-24.08
    Status:
    Opublikowana
  12. PTAS for Steiner Tree on Map Graphs
    Autorzy:
    Jaroslaw Byrka, Mateusz Lewandowski, Syed Mohammad Meesum, Joachim Spoerhase, Sumedha Uniyal
    Konferencja:
    LATIN 2020: Latin American Symposium on Theoretical Informatics (rok: 2020, ), Wydawca: Springer
    Data:
    konferencja 5-8.01.2021
    Status:
    Opublikowana
  13. Tight Approximation for Proportional Approval Voting
    Autorzy:
    Szymon Dudycz, Pasin Manurangsi, Jan Marcinkowski and Krzysztof Sornat
    Konferencja:
    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:
    Opublikowana
  14. Tight Inapproximability of Minimum Maximal Matching on Bipartite Graphs and Related Problems
    Autorzy:
    Szymon Dudycz, Pasin Manurangsi, Jan Marcinkowski
    Konferencja:
    WAOA 2021: Workshop on Approximation and Online Algorithms (rok: 2021, ), Wydawca: Springer
    Data:
    konferencja 9-10.09
    Status:
    Opublikowana
  15. Approximation Schemes for Geometric Coverage Problems
    Autorzy:
    Chaplick, Steven ; De, Minati ; Ravsky, Alexander ; Spoerhase, Joachim
    Konferencja:
    European Symposium on Algorithms (ESA 2018) (rok: 2018, ), Wydawca: Schloss Dagstuhl--Leibniz- Zentrum fuer Informatik (LIPIcs)
    Data:
    konferencja 20-24.08
    Status:
    Opublikowana
  16. Concave Connection Cost Facility Location and the Star Inventory Routing Problem
    Autorzy:
    Jaroslaw Byrka, Mateusz Lewandowski
    Konferencja:
    International Workshop on Approximation and Online Algorithms WAOA 2020 (rok: 2020, ), Wydawca: Springer
    Data:
    konferencja 9-10.09
    Status:
    Opublikowana
  17. Constant-factor approximation for ordered k- median
    Autorzy:
    Jaroslaw Byrka, Krzysztof Sornat, Joachim Spoerhase
    Konferencja:
    50th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2018) (rok: 2018, ), Wydawca: ACM
    Data:
    konferencja 25-29.06
    Status:
    Opublikowana
  18. Dynamic Beats Fixed: On Phase-Based Algorithms for File Migration
    Autorzy:
    Marcin Bienkowski and Jaroslaw Byrka and Marcin Mucha
    Konferencja:
    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:
    Opublikowana

O Narodowym Centrum Nauki

Finansowanie nauki

Współpraca zagraniczna

Centrum prasowe

Deklaracja dostępności
Przetwarzanie danych osobowych
Polityka cookies

Partnerzy