Online algorithms for fundamental network problems
Polish National Science Centre grant 2013/09/B/ST6/01538, 2014-2017
The goal of the project is to design and analyze online algorithms that introduce or improve quality of service (QoS) for network applications.
Applications of interest include (i) mechanisms used within a single network device, such as managing packet queues or routing tables, and
(ii) constructing efficient policies for data flow and data management in networks.
Publications
Marcin Bienkowski, Tomasz Jurdzinski, Miroslaw Korzeniowski, Dariusz R. Kowalski: Distributed Online and Stochastic Queuing on a Multiple Access Channel, TALG 2018
Nikhil Bansal, Marek Eliáš, Łukasz Jeż, Grigorios Koumoutsos, Kirk Pruhs: Tight Bounds for Double Coverage Against Weak Adversaries, TOCS 2018
Christoph Dürr, Łukasz Jeż, Óscar C.Vásquez: Mechanism design for aggregating energy consumption and quality of service in speed scaling scheduling, TCS 2017
Carlo Fuerst, Maciej Pacut, Stefan Schmid: Data Locality and Replica Aware Virtual Cluster Embeddings, TCS 2017
Marcin Bienkowski, Jan Marcinkowski, Maciej Pacut, Stefan Schmid, Aleksandra Spyra: Online Tree Caching, SPAA 2017
Nikhil Bansal, Marek Eliáš, Łukasz Jeż, Grigorios Koumoutsos: The (h,k)-Server Problem on Bounded Depth Trees, SODA 2017
Martin Böhm, Marek Chrobak, Łukasz Jeż, Fei Li, Jirí Sgall, Pavel Veselý: Online Packet Scheduling with Bounded Delay and Lookahead, ISAAC 2016
Chen Avin, Andreas Loukas, Maciej Pacut, Stefan Schmid: Online Balanced Repartitioning, DISC 2016
Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Marek Chrobak, Christoph Dürr, Lukáš Folwarczný, Łukasz Jeż, Jiří Sgall, Nguyen Kim Thang, Pavel Veselý: Online Algorithms for Multi-Level Aggregation, ESA 2016 + MAPSP 2015
Marcin Bienkowski, Marek Klonowski, Miroslaw Korzeniowski, Dariusz R. Kowalski: Randomized Mutual Exclusion Problem on a Multiple Access Channel, Dist. Comp. 2016
Marcin Bienkowski, Leszek Gąsieniec, Marek Klonowski, Miroslaw Korzeniowski, Bernard Mans, Stefan Schmid, Roger Wattenhofer: Distributed Alarming in the On-Duty and Off-Duty Models, ACM/IEEE Trans. Netw. 2016
Marek Cygan, Łukasz Jeż, Jiří Sgall: Online Knapsack Revisited, TOCS 2016
Yossi Azar, Amir Epstein, Łukasz Jeż, Adi Vardi: Make-to-Order Integrated Scheduling and Distribution, SODA 2016
Nikhil Bansal, Marek Elias, Łukasz Jeż, Grigorios Koumoutsos, Kirk Pruhs: Tight bounds for Double Coverage against weak adversaries, WAOA 2015
Marcin Bienkowski, Artur Kraska, Paweł Schmidt: A Randomized Algorithm for Online Scheduling with Interval Conflicts, SIROCCO 2015
Łukasz Jeż, Yishay Mansour, Boaz Patt-Shamir: Scheduling Multipacket Frames With Frame Deadlines, SIROCCO 2015
Ilan Reuven Cohen, Alon Eden, Amos Fiat, Łukasz Jeż: Pricing Online Decisions: Beyond Auctions, SODA 2015
Carlo Fuerst, Maciej Pacut, Paolo Costa, Stefan Schmid: How Hard Can It Be? Understanding the Complexity of Replica Aware Virtual Cluster Embeddings, ICNP 2015
Marcin Bienkowski, Jaroslaw Byrka, Krzysztof Chrobak, Tomasz Jurdzinski, Dariusz Kowalski: Provable Fairness for TDMA Scheduling, INFOCOM 2015
Christoph Dürr, Łukasz Jeż, Oscar C. Vásquez: Scheduling under dynamic speed-scaling for minimizing weighted completion time and energy consumption, Disc. Appl. Math. 2015
Marcin Bienkowski, Jarosław Byrka, Marek Chrobak, Neil Dobbs, Tomasz Nowicki, Maxim Sviridenko, Grzegorz Świrszcz, Neal E. Young: Approximation Algorithms for the Joint Replenishment Problem with Deadlines, J. Scheduling 2015
Marcin Bienkowski, Nadi Sarrar, Stefan Schmid, Steve Uhlig: Competitive FIB Aggregation without Update Churn, ICDCS 2014
Nadi Sarrar, Robert Wuttke, Stefan Schmid, Marcin Bienkowski, Steve Uhlig: Leveraging Locality for FIB Aggregation, GLOBECOM 2014