Projects funded by the NCN

Information on the principal investigator and host institution

Information of the project and the call

Keywords

Equipment

Delete all

Online algorithms for fundamental network problems

2013/09/B/ST6/01538

Keywords:

online algorithms competitive analysis network problems probabilistic analysis combinatorial optimization

Descriptors:

  • 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. Marcin Bieńkowski 

Number of co-investigators in the project: 4

Call: OPUS 5 - announced on 2013-03-15

Amount awarded: 528 560 PLN

Project start date (Y-m-d): 2014-02-24

Project end date (Y-m-d): 2017-05-23

Project duration:: 39 months (the same as in the proposal)

Project status: Project settled

Equipment purchased [PL]

  1. Laptop (2 szt.) (14 000 PLN)
  2. Zestaw komputerowy (6 000 PLN)

Information in the final report

  • Publication in academic press/journals (9)
  • Articles in post-conference publications (14)
  1. Online Knapsack Revisited
    Authors:
    Marek Cygan, Lukasz Jez, Jirí Sgall
    Academic press:
    Theory of Computing Systems (rok: 2016, tom: 58(1), strony: 153-190), Wydawca: Springer
    Status:
    Published
    DOI:
    10.1007/s00224-014-9566-4 - link to the publication
  2. Data Locality and Replica Aware Virtual Cluster Embeddings
    Authors:
    Carlo Fuerst, Maciej Pacut, Stefan Schmid
    Academic press:
    Theoretical Computer Science (rok: 2017, tom: 697, strony: 37-57), Wydawca: Elsevier
    Status:
    Accepted for publication
    DOI:
    10.1016/j.tcs.2017.06.025 - link to the publication
  3. Approximation Algorithms for the Joint Replenishment Problem with Deadlines
    Authors:
    Marcin Bienkowski, Jarosław Byrka, Marek Chrobak, Neil Dobbs, Tomasz Nowicki, Maxim Sviridenko, Grzegorz Świrszcz, Neal E. Young
    Academic press:
    Journal of Scheduling (rok: 2015, tom: 18(6), strony: 545-560), Wydawca: Springer
    Status:
    Published
    DOI:
    10.1007/s10951-014-0392-y - link to the publication
  4. Mechanism design for aggregating energy consumption and quality of service in speed scaling scheduling
    Authors:
    Christoph Dürr, Łukasz Jeż, Óscar C. Vásquez
    Academic press:
    Theoretical Computer Science (rok: 2017, tom: 695, strony: 28-41), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.tcs.2017.07.020 - link to the publication
  5. Tight Bounds for Double Coverage Against Weak Adversaries
    Authors:
    Nikhil Bansal, Marek Eliáš, Łukasz Jeż, Grigorios Koumoutsos, Kirk Pruhs
    Academic press:
    Theory of Computing Systems (rok: 2018, tom: 62(2), strony: 349–365), Wydawca: Springer
    Status:
    Accepted for publication
    DOI:
    10.1007/s00224-016-9703-3 - link to the publication
  6. Randomized mutual exclusion on a multiple access channel
    Authors:
    Marcin Bienkowski, Marek Klonowski, Miroslaw Korzeniowski, Dariusz R. Kowalski
    Academic press:
    Distributed Computing (rok: 2016, tom: 29(5), strony: 341–359), Wydawca: Springer
    Status:
    Published
    DOI:
    10.1007/s00446-016-0265-z - link to the publication
  7. Distributed Online and Stochastic Queuing on a Multiple Access Channel
    Authors:
    Marcin Bienkowski, Tomasz Jurdzinski, Miroslaw Korzeniowski, Dariusz R. Kowalski
    Academic press:
    Transactions on Algorithms (rok: 2018, tom: 14(2), strony: 21:1-21:22), Wydawca: ACM
    Status:
    Submitted
    DOI:
    10.1145/3182396 - link to the publication
  8. Distributed Alarming in the On-Duty and Off-Duty Models
    Authors:
    Marcin Bienkowski, Leszek Gąsieniec, Marek Klonowski, Miroslaw Korzeniowski, Bernard Mans, Stefan Schmid, Roger Wattenhofer
    Academic press:
    IEEE-ACM Transactions on Networking (rok: 2016, tom: 24(1), strony: 218-230), Wydawca: IEEE
    Status:
    Published
    DOI:
    10.1109/TNET.2014.2359684 - link to the publication
  9. Scheduling under dynamic speed-scaling for minimizing weighted completion time and energy consumption
    Authors:
    Christoph Dürr, Łukasz Jeż, Oscar C. Vásquez
    Academic press:
    Discrete Applied Mathematics (rok: 2015, tom: 196, strony: 20-27), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.dam.2014.08.001 - link to the publication
  1. Leveraging Locality for FIB Aggregation
    Authors:
    Nadi Sarrar, Robert Wuttke, Stefan Schmid, Marcin Bienkowski, Steve Uhlig
    Conference:
    2014 IEEE Global Communications Conference (GLOBECOM) (rok: 2014, ), Wydawca: IEEE
    Data:
    konferencja 8-12 grudnia 2014
    Status:
    Published
  2. Online Balanced Repartitioning
    Authors:
    Chen Avin, Andreas Loukas, Maciej Pacut, Stefan Schmid
    Conference:
    30th International Symposium on Distributed Computing (DISC) (rok: 2016, ), Wydawca: Springer
    Data:
    konferencja 27-29 września 2016
    Status:
    Published
  3. A Randomized Algorithm for Online Scheduling with Interval Conflicts
    Authors:
    Marcin Bienkowski, Artur Kraska, Pawel Schmidt
    Conference:
    22nd International Colloquium on Structural Information and Communication Complexity (SIROCCO) (rok: 2015, ), Wydawca: Springer
    Data:
    konferencja 15-17 lipca 2015
    Status:
    Published
  4. Make-to-Order Integrated Scheduling and Distribution
    Authors:
    Yossi Azar, Amir Epstein, Lukasz Jez, Adi Vardi
    Conference:
    27th ACM-SIAM Symposium on Discrete Algorithms (SODA) (rok: 2016, ), Wydawca: Society for Industrial and Applied Mathematics (SIAM)
    Data:
    konferencja 10-12 stycznia 2016
    Status:
    Published
  5. Online Algorithms for Multi-Level Aggregation
    Authors:
    Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Marek Chrobak, Christoph Dürr, Lukas Folwarczny, Lukasz Jez, Jiri Sgall, Nguyen Kim Thang, Pavel Veselý
    Conference:
    24th Annual European Symposium on Algorithms (ESA) (rok: 2016, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 22-26 sierpnia 2016
    Status:
    Published
  6. Provable Fairness for TDMA Scheduling
    Authors:
    Marcin Bienkowski, Jaroslaw Byrka, Krzysztof Chrobak, Tomasz Jurdzinski, Dariusz Kowalski
    Conference:
    34rd IEEE Conference on Computer Communications (INFOCOM) (rok: 2015, ), Wydawca: IEEE
    Data:
    konferencja 26 kwietnia - 1 maja 2015
    Status:
    Published
  7. The (h, k)-Server Problem on Bounded Depth Trees
    Authors:
    Nikhil Bansal, Marek Eliás, Lukasz Jez, Grigorios Koumoutsos
    Conference:
    26th ACM-SIAM Symposium on Discrete Algorithms (SODA) (rok: 2017, ), Wydawca: Society for Industrial and Applied Mathematics (SIAM)
    Data:
    konferencja 16-19 stycznia 2017
    Status:
    Published
  8. Competitive FIB Aggregation without Update Churn
    Authors:
    Marcin Bienkowski, Nadi Sarrar, Stefan Schmid, Steve Uhlig
    Conference:
    34th International Conference on Distributed Computing Systems (ICDCS) (rok: 2014, ), Wydawca: IEEE
    Data:
    konferencja 30 czerwca - 3 lipca 2014
    Status:
    Published
  9. Online Tree Caching
    Authors:
    Marcin Bienkowski, Jan Marcinkowski, Maciej Pacut, Stefan Schmid, Aleksandra Spyra
    Conference:
    29th ACM Symp. on Parallelism in Algorithms and Architectures (SPAA) (rok: 2017, ), Wydawca: ACM
    Data:
    konferencja 24-26 lipca 2017
    Status:
    Published
  10. Tight Bounds for Double Coverage Against Weak Adversaries
    Authors:
    Nikhil Bansal, Marek Eliás, Lukasz Jez, Grigorios Koumoutsos, Kirk Pruhs
    Conference:
    13th International Workshop on Approximation and Online Algorithms (WAOA) (rok: 2015, ), Wydawca: Springer
    Data:
    konferencja 17-18 września 2015
    Status:
    Published
  11. Pricing Online Decisions: Beyond Auctions
    Authors:
    Ilan Reuven Cohen, Alon Eden, Amos Fiat, Łukasz Jeż
    Conference:
    26th ACM-SIAM Symposium on Discrete Algorithms (SODA) (rok: 2015, ), Wydawca: Society for Industrial and Applied Mathematics (SIAM)
    Data:
    konferencja 4-6 stycznia 2015
    Status:
    Published
  12. How Hard Can It Be?: Understanding the Complexity of Replica Aware Virtual Cluster Embeddings
    Authors:
    Carlo Fuerst, Maciek Pacut, Paolo Costa, Stefan Schmid
    Conference:
    23rd IEEE International Conference on Network Protocols (ICNP) (rok: 2015, ), Wydawca: IEEE
    Data:
    konferencja 10-13 listopada 2015
    Status:
    Published
  13. Online Packet Scheduling with Bounded Delay and Lookahead
    Authors:
    Martin Böhm, Marek Chrobak, Lukasz Jez, Fei Li, Jirí Sgall, Pavel Veselý
    Conference:
    27th International Symposium on Algorithms and Computation (ISAAC) (rok: 2016, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 12-14 grudnia 2016
    Status:
    Published
  14. Scheduling Multipacket Frames with Frame Deadlines
    Authors:
    Lukasz Jez, Yishay Mansour, Boaz Patt-Shamir
    Conference:
    22nd International Colloquium on Structural Information and Communication Complexity (SIROCCO) (rok: 2015, ), Wydawca: Springer
    Data:
    konferencja 15-17 lipca 2015
    Status:
    Published

O Narodowym Centrum Nauki

Finansowanie nauki

Współpraca zagraniczna

Centrum prasowe

Deklaracja dostępności
Przetwarzanie danych osobowych
Polityka cookies

Partnerzy