Approximation algorithms under uncertainty
MNiSW grant number N N206 368839, 2010–2013
Publications
Publications
Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak, Łukasz Jeż̇, Dorian Nogneng, Jiří Sgall: Better Approximation Bounds for the Joint Replenishment Problem, SODA 2014
Marcin Bienkowski: An Optimal Lower Bound for Buffer Management in Multi-Queue Switches, Algorithmica 2014
Marcin Bienkowski, Anja Feldmann, Johannes Grassler, Gregor Schaffrath, Stefan Schmid: The Wide-Area Virtual Service Migration Problem: A Competitive Analysis Approach, IEEE/ACM Trans. Networking 2014
Marcin Bienkowski, Marek Chrobak, Christoph Dürr, Mathilde Hurand, Artur Jeż, Łukasz Jeż, Grzegorz Stachowiak: Collecting Weighted Items from a Dynamic Queue, Algorithmica 2013
Marcin Bienkowski, Marek Chrobak, Christoph Dürr, Mathilde Hurand, Artur Jeż, Łukasz Jeż, Grzegorz Stachowiak: A φ-Competitive Algorithm for Collecting Items with Increasing Weights from a Dynamic Queue, TCS 2013
Jaroslaw Byrka, Fabrizio Grandoni, Thomas Rothvoß, Laura Sanità: Steiner Tree Approximation via Iterative Randomized Rounding, J. ACM 2013
Marcin Bienkowski, Paweł Zalewski: (1,2)-Hamiltonian Completion on a Matching, IJFCS 2013
Łukasz Jeż: A Universal Randomized Packet Scheduling Algorithm, Algorithmica 2013
Łukasz Jeż, Jarett Schwartz, Jiří Sgall, József Békési: Lower bounds for online makespan minimization on a small number of related machines,
J. Scheduling 2013Marek Chrobak, Łukasz Jeż, Jiří Sgall: Better Bounds for Incremental Frequency Allocation in Bipartite Graphs, TCS 2013
Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak, Neil Dobbs, Tomasz Nowicki, Maxim Sviridenko, Grzegorz Swirszcz, Neal E. Young: Approximation Algorithms for the Joint Replenishment Problem with Deadlines, ICALP 2013
Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak, Łukasz Jeż̇, Jiří Sgall, Grzegorz Stachowiak: Online Control Message Aggregation in Chain Networks, WADS 2013 + MAPSP 2013
Marcin Bienkowski, Stefan Schmid: Competitive FIB Aggregation: Online Ski Rental on the Trie, SIROCCO 2013
Christoph Durr, Łukasz Jeż, Oscar Vásquez: Mechanism Design for Aggregating Energy Consumption and Quality of Service in Speed Scaling Scheduling, WINE 2013
Marek Cygan, Łukasz Jeż: Online Knapsack revisited, WAOA 2013
Jaroslaw Byrka, Shanfei Li, Bartosz Rybicki: Improved approximation algorithm for k-level UFL (with penalties), a simplistic view on randomizing the scaling parameter, WAOA 2013
Kevin Buchin, Maike Buchin, Jaroslaw Byrka, Martin Nöllenburg, Yoshio Okamoto, Rodrigo I. Silveira, Alexander Wolff: Drawing (Complete) Binary Tanglegrams: Hardness, Approximation, Fixed-Parameter Tractability, Algorithmica 2012
Łukasz Jeż, Fei Li, Jay Sethuraman, Cliff Stein: Online Scheduling of Packets with Agreeable Deadlines, TALG 2012
Marcin Bienkowski, Jarosław Kutyłowski: The k-Resource Problem in Uniform Metric Spaces, TCS 2012
Khaled Elbassioni, Katarzyna Paluch, Anke Van Zuylen: Simpler Approximation of the Maximum Asymmetric Traveling Salesman Problem, STACS 2012
Leah Epstein, Łukasz Jeż, Jiří Sgall, Rob van Stee: Online Scheduling of Jobs with Fixed Start Times on Related Machines, APPROX 2012
Marcin Bienkowski, Tomasz Jurdzinski, Miroslaw Korzeniowski, Dariusz R. Kowalski: Distributed Online and Stochastic Queuing on a Multiple Access Channel, DISC 2012
Katarzyna Paluch: Popular and Clan-Popular b-Matchings, ISAAC 2012
Marcin Bienkowski: An Optimal Lower Bound for Buffer Management in Multi-Queue Switches, SODA 2011
Dushyant Arora, Marcin Bienkowski, Anja Feldmann, Gregor Schaffrath, Stefan Schmid: Online Strategies for Intra and Inter Provider Service Migration in Virtual Networks, IPTComm 2011
Łukasz Jeż: One to Rule Them All: a General Randomized Algorithm for Buffer Management with Bounded Delay, ESA 2011
Marek Chrobak, Łukasz Jeż, Jiří Sgall: Better Bounds for Incremental Frequency Allocation in Bipartite Graphs, ESA 2011
Jaroslaw Byrka, MohammadReza Ghodsi, Aravind Srinivasan: LP-rounding algorithms for facility-location problems, unpublished