Marcin Bienkowski

IJCAI Conference 2024 Conference Paper

Contract Scheduling with Distributional and Multiple Advice

• Spyros Angelopoulos
• Marcin Bienkowski
• Christoph Dürr
• Bertrand Simon

Contract scheduling is a widely studied framework for designing real-time systems with interruptible capabilities. Previous work has showed that a prediction on the interruption time can help improve the performance of contract-based systems, however it has relied on a single prediction that is provided by a deterministic oracle. In this work, we introduce and study more general and realistic learning-augmented settings in which the prediction is in the form of a probability distribution, or it is given as a set of multiple possible interruption times. For both prediction settings, we design and analyze schedules which perform optimally if the prediction is accurate, while simultaneously guaranteeing the best worst-case performance if the prediction is adversarial. We also provide evidence that the resulting system is robust to prediction errors in the distributional setting. Last, we present an experimental evaluation that confirms the theoretical findings, and illustrates the performance improvements that can be attained in practice.

AAAI Conference 2023 Conference Paper

An Improved Algorithm for Online Min-Sum Set Cover

• Marcin Bienkowski
• Marcin Mucha

We study a fundamental model of online preference aggregation, where an algorithm maintains an ordered list of n elements. An input is a stream of preferred sets R_1, R_2,..., R_t,... Upon seeing R_t and without knowledge of any future sets, an algorithm has to rerank elements (change the list ordering), so that at least one element of R_t is found near the list front. The incurred cost is a sum of the list update costs (the number of swaps of neighboring list elements) and access cost (the position of the first element of R_t on the list). This scenario occurs naturally in applications such as ordering items in an online shop using aggregated preferences of shop customers. The theoretical underpinning of this problem is known as Min-Sum Set Cover. Unlike previous work that mostly studied the performance of an online algorithm ALG in comparison to the static optimal solution (a single optimal list ordering), in this paper, we study an arguably harder variant where the benchmark is the provably stronger optimal dynamic solution OPT (that may also modify the list ordering). In terms of an online shop, this means that the aggregated preferences of its user base evolve with time. We construct a computationally efficient randomized algorithm whose competitive ratio (ALG-to-OPT cost ratio) is O(r^2) and prove the existence of a deterministic O(r^4)-competitive algorithm. Here, r is the maximum cardinality of sets R_t. This is the first algorithm whose ratio does not depend on n: the previously best algorithm for this problem was O(r^(3/2) * n^(1/2))-competitive and Ω(r) is a lower bound on the performance of any deterministic online algorithm.

TCS Journal 2021 Journal Article

New results on multi-level aggregation

• Marcin Bienkowski
• Martin Böhm
• Jaroslaw Byrka
• Marek Chrobak
• Christoph Dürr
• Lukáš Folwarczný
• Łukasz Jeż
• Jiří Sgall

In the Multi-Level Aggregation Problem (MLAP ), requests for service arrive at the nodes of an edge-weighted rooted tree T. Each service is represented by a subtree X of T that contains its root. This subtree X serves all requests that are pending in the nodes of X, and the cost of this service is equal to the total weight of X. Each request also incurs a waiting cost between its arrival and service time. The objective is to minimize the total waiting cost of all requests plus the total cost of all service subtrees. The currently best online algorithms for the MLAP achieve competitive ratios polynomial in the tree depth, while the best lower bound is only 3. 618. In this paper, we report some progress towards closing this gap, by improving this lower bound and providing several tight bounds for restricted variants of MLAP: (1) We first study a Single-Phase variant of MLAP where all requests are released at the beginning and expire at some unknown time θ, for which we provide an online algorithm with optimal competitive ratio of 4. (2) We prove a lower bound of 4 on the competitive ratio for MLAP, even when the tree is a path. We complement this with a matching upper bound for the deadline variant of MLAP on paths. Additionally, we provide two results for the offline case: (3) We prove that the Single-Phase variant can be solved optimally in polynomial time, and (4) we give a simple 2-approximation algorithm for offline MLAP with deadlines.

STOC Conference 2020 Conference Paper

Unbounded lower bound for k-server against weak adversaries

• Marcin Bienkowski
• Jaroslaw Byrka
• Christian Coester
• Lukasz Jez

We study the resource augmented version of the k -server problem, also known as the k -server problem against weak adversaries or the ( h , k )-server problem. In this setting, an online algorithm using k servers is compared to an offline algorithm using h servers, where h ≤ k . For uniform metrics, it has been known since the seminal work of Sleator and Tarjan (1985) that for any є>0, the competitive ratio drops to a constant if k =(1+є) · h . This result was later generalized to weighted stars (Young 1994) and trees of bounded depth (Bansal et al. 2017). The main open problem for this setting is whether a similar phenomenon occurs on general metrics. We resolve this question negatively. With a simple recursive construction, we show that the competitive ratio is at least Ω(loglog h ), even as k →∞. Our lower bound holds for both deterministic and randomized algorithms. It also disproves the existence of a competitive algorithm for the infinite server problem on general metrics.

MFCS Conference 2019 Conference Paper

An Improved Online Algorithm for the Traveling Repairperson Problem on a Line

• Marcin Bienkowski
• Alison Hsiang-Hsuan Liu

In the online variant of the traveling repairperson problem (TRP), requests arrive in time at points of a metric space X and must be eventually visited by a server. The server starts at a designated point of X and travels at most at unit speed. Each request has a given weight and once the server visits its position, the request is considered serviced; we call such time completion time of the request. The goal is to minimize the weighted sum of completion times of all requests. In this paper, we give a 5. 429-competitive deterministic algorithm for line metrics improving over 5. 829-competitive solution by Krumke et al. (TCS 2003). Our result is obtained by modifying the schedule by serving requests that are close to the origin first. To compute the competitive ratio of our approach, we use a charging scheme, and later evaluate its properties using a factor-revealing linear program which upper-bounds the competitive ratio.

MFCS Conference 2019 Conference Paper

Better Bounds for Online Line Chasing

• Marcin Bienkowski
• Jaroslaw Byrka
• Marek Chrobak
• Christian Coester
• Lukasz Jez
• Elias Koutsoupias

We study online competitive algorithms for the line chasing problem in Euclidean spaces R^d, where the input consists of an initial point P_0 and a sequence of lines X_1, X_2, .. ., X_m, revealed one at a time. At each step t, when the line X_t is revealed, the algorithm must determine a point P_t in X_t. An online algorithm is called c-competitive if for any input sequence the path P_0, P_1, .. ., P_m it computes has length at most c times the optimum path. The line chasing problem is a variant of a more general convex body chasing problem, where the sets X_t are arbitrary convex sets. To date, the best competitive ratio for the line chasing problem was 28. 1, even in the plane. We improve this bound by providing a simple 3-competitive algorithm for any dimension d. We complement this bound by a matching lower bound for algorithms that are memoryless in the sense of our algorithm, and a lower bound of 1. 5358 for arbitrary algorithms. The latter bound also improves upon the previous lower bound of sqrt{2}~=1. 412 for convex body chasing in 2 dimensions.

TCS Journal 2018 Journal Article

Logarithmic price of buffer downscaling on line metrics

• Marcin Bienkowski
• Martin Böhm
• Łukasz Jeż
• Paweł Laskoś-Grabowski
• Jan Marcinkowski
• Jiří Sgall
• Aleksandra Spyra
• Pavel Veselý

We consider the reordering buffer problem on a line consisting of n equidistant points. We show that, for any constant δ, an (offline) algorithm that has a buffer ( 1 − δ ) ⋅ k performs worse by a factor of Ω ( log ⁡ n ) than an offline algorithm with buffer k. In particular, this demonstrates that the O ( log ⁡ n ) -competitive online algorithm MovingPartition by Gamzu and Segev (2009) [9] is essentially optimal against any offline algorithm with a slightly larger buffer.

SODA Conference 2014 Conference Paper

Better Approximation Bounds for the Joint Replenishment Problem

• Marcin Bienkowski
• Jaroslaw Byrka
• Marek Chrobak
• Lukasz Jez
• Dorian Nogneng
• Jirí Sgall

The Joint Replenishment Problem (JRP) deals with optimizing shipments of goods from a supplier to retailers through a shared warehouse. Each shipment involves transporting goods from the supplier to the warehouse, at a fixed cost C, followed by a redistribution of these goods from the warehouse to the retailers that ordered them, where transporting goods to a retailer ρ has a fixed cost c ρ. In addition, we incur waiting costs for each order, possibly an arbitrary non-decreasing function of time, different for each order. The objective is to minimize the overall cost of satisfying all orders, namely the sum of all shipping and waiting costs. JRP has been well studied in Operations Research and, more recently, in the area of approximation algorithms. For arbitrary waiting cost functions, the best known approximation ratio is 1. 8. This ratio can be reduced to ≈ 1. 574 for the JRP-D model, where there is no cost for waiting but orders have deadlines. As for hardness results, it is known that the problem is ℙ -hard and that the natural linear program for JRP has integrality gap at least 1. 245. Both results hold even for JRP-D. In the online scenario, the best lower and upper bounds on the competitive ratio are 2. 64 and 3, respectively. The lower bound of 2. 64 applies even to the restricted version of JRP, denoted JRP-L, where the waiting cost function is linear. We provide several new approximation results for JRP. In the offline case, we give an algorithm with ratio ≈ 1. 791, breaking the barrier of 1. 8. We also show that the integrality gap of the linear program for JRP-L is at least 12/11 ≈ 1. 09. In the online case, we show a lower bound of ≈ 2. 754 on the competitive ratio for JRP-L (and thus JRP as well), improving the previous bound of 2. 64. We also study the online version of JRP-D, for which we prove that the optimal competitive ratio is 2.

TCS Journal 2013 Journal Article

A ϕ -competitive algorithm for collecting items with increasing weights from a dynamic queue

• Marcin Bienkowski
• Marek Chrobak
• Christoph Dürr
• Mathilde Hurand
• Artur Jeż
• Łukasz Jeż
• Grzegorz Stachowiak

The bounded-delay packet scheduling (or buffer management) problem is to schedule transmissions of packets arriving in a buffer of a network link. Each packet has a deadline and a weight associated with it. The objective is to maximize the weight of packets that are transmitted before their deadlines, assuming that only one packet can be transmitted in one time step. Online packet scheduling algorithms have been extensively studied. It is known that no online algorithm can achieve a competitive ratio better than ϕ ≈ 1. 618 (the golden ratio), while the currently best upper bound on the competitive ratio is 2 2 − 1 ≈ 1. 824. Closing the gap between these bounds remains a major open problem. The above mentioned lower bound of ϕ uses instances where item weights increase exponentially over time. In fact, all lower bounds for various versions of buffer management problems involve instances of this type. In this paper, we design an online algorithm for packet scheduling with competitive ratio ϕ when packet weights are increasing, thus matching this lower bound. Our algorithm applies, in fact, to a much more general version of packet scheduling, where only the relative order of the deadlines is known, not their exact values.

TCS Journal 2012 Journal Article

The k -resource problem in uniform metric spaces

• Marcin Bienkowski
• Jarosław Kutyłowski

We define a natural generalization of the prominent k -server problem, the k -resource problem. It occurs in a metric space with some integer demands given at its points. The demands may vary with time, but the total demand may never exceed k. An online algorithm has k servers at its disposal and its goal is to satisfy demands by moving servers, while minimizing the cost of their transport. We show asymptotically tight bounds on the competitive ratio of the k -resource problem in the uniform metric space of n points: we prove that the optimal competitive ratios are between min { k, n − 1 } and min { k, 2 ( n − 1 ) } for deterministic algorithms and between min { H k, H n − 1 } and min { H k, 2 ⋅ H n − 1 } for randomized ones. This extends known results for k -server in such spaces to the more general setting of k -resource.

SODA Conference 2011 Conference Paper

An Optimal Lower Bound for Buffer Management in Multi-Queue Switches

• Marcin Bienkowski

TCS Journal 2011 Journal Article

Randomized competitive algorithms for online buffer management in the adaptive adversary model

• Marcin Bienkowski
• Marek Chrobak
• Łukasz Jeż

In the problem of buffer management with bounded delay, packets with weights and deadlines arrive at a network switch over time, and the goal is to send those packets on the outgoing link while maximizing the total weight of the packets that are sent before their deadlines. We present a study of randomized algorithms that are competitive against an adaptive adversary. Previous studies considered only the oblivious adversary model that does not capture dependency of network traffic on the packet scheduling algorithm. We give a new analysis of a previously known algorithm, which shows that it remains e / ( e − 1 ) -competitive even against an adaptive adversary. We complement this with a 4/3 lower bound on the competitive ratio on 2-bounded instances, in which each packet has a lifespan of one or two steps. We also study more restricted 2-uniform instances, in which every packet has a lifespan of exactly two steps. For such instances we give a 1. 2 lower bound on the competitive ratio of arbitrary algorithms and 4/3 lower bound on the competitive ratio of memoryless scale-invariant algorithms. Finally, we devise a 4/3-competitive memoryless scale-invariant algorithm for 2-bounded instances, matching two of these lower bounds.

SODA Conference 2009 Conference Paper

Collecting weighted items from a dynamic queue

• Marcin Bienkowski
• Marek Chrobak
• Christoph Dürr
• Mathilde Hurand
• Artur Jez
• Lukasz Jez
• Grzegorz Stachowiak

MFCS Conference 2005 Invited Paper

Page Migration in Dynamic Networks

• Marcin Bienkowski
• Friedhelm Meyer auf der Heide

Abstract In the last couple of decades, network connected systems have gradually replaced centralized parallel computing machines. To provide smooth operation of network applications, the underlying system has to provide so-called basic services. One of the most crucial services is to provide a transparent access to data like variables, databases, memory pages, or. les, which are shared by the instances of programs running at nodes of the network.