BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Marcin Bienkowski

Marcin Bienkowski appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Data Structures and AlgorithmsNetworking and Internet Architecture

Catalog footprint

What is connected

12works
2topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

12 published item(s)

preprint2022arXiv

Deterministic Self-Adjusting Tree Networks Using Rotor Walks

We revisit the design of self-adjusting single-source tree networks. The problem can be seen as a generalization of the classic list update problem to trees, and finds applications in reconfigurable datacenter networks. We are given a fixed balanced binary tree T connecting n nodes V = {v_1, ... , v_n}. A source node v_0, attached to the root of the tree, issues communication requests to nodes in V, in an online and adversarial manner; the access cost of a request to a node v, is given by the current depth of v in T. The online algorithm can try to reduce the access cost by performing swap operations, with which the position of a node is exchanged with the position of its parent in the tree; a swap operation costs one unit. The objective is to design an online algorithm which minimizes the total access cost plus adjustment cost (swapping). Avin et al. recently presented Random-Push, a constant competitive online algorithm for this problem, based on random walks, together with an analysis exploiting the most recently used (MRU) property of random walks. We study analytically and empirically, online algorithms for this problem. In particular, we explore how to derandomize Random-Push. We consider a simple derandomized algorithm which we call Rotor-Push, as its behavior is reminiscent of rotor walks. We first prove that Rotor-Push is constant competitive: its competitive ratio is 12 and hence by a factor of five lower than the best existing competitive ratio. In contrast to Random-Push, the algorithm does not feature the MRU property, which requires a new analysis. We present a significantly improved and simpler analysis for the randomized algorithm, showing that it is 16-competitive. We compare empirically all self-adjusting single-source tree networks, using synthetic and real data with varying locality and observe that Rotor-Push and Random-Push have almost identical performance.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

A Nearly Optimal Deterministic Online Algorithm for Non-Metric Facility Location

In the online non-metric variant of the facility location problem, there is a given graph consisting of a set $F$ of facilities (each with a certain opening cost), a set $C$ of potential clients, and weighted connections between them. The online part of the input is a sequence of clients from $C$, and in response to any requested client, an online algorithm may open an additional subset of facilities and must connect the given client to an open facility. We give an online, polynomial-time deterministic algorithm for this problem, with a competitive ratio of $O(\log |F| \cdot (\log |C| + \log \log |F|))$. The result is optimal up to loglog factors. Our algorithm improves over the $O((\log |C| + \log |F|) \cdot (\log |C| + \log \log |F|))$-competitive construction that first reduces the facility location instance to a set cover one and then later solves such instance using the deterministic algorithm by Alon et al. [TALG 2006]. This is an asymptotic improvement in a typical scenario where $|F| \ll |C|$. We achieve this by a more direct approach: we design an algorithm for a fractional relaxation of the non-metric facility location problem with clustered facilities. To handle the constraints of such non-covering LP, we combine the dual fitting and multiplicative weight updates approach. By maintaining certain additional monotonicity properties of the created fractional solution, we can handle the dependencies between facilities and connections in a rounding routine. Our result, combined with the algorithm by Naor et al. [FOCS 2011] yields the first deterministic algorithm for the online node-weighted Steiner tree problem. The resulting competitive ratio is $O(\log k \cdot \log^2 \ell)$ on graphs of $\ell$ nodes and $k$ terminals.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

An Optimal Algorithm for Online Multiple Knapsack

In the online multiple knapsack problem, an algorithm faces a stream of items, and each item has to be either rejected or stored irrevocably in one of $n$ bins (knapsacks) of equal size. The gain of an~algorithm is equal to the sum of sizes of accepted items and the goal is to maximize the total gain. So far, for this natural problem, the best solution was the $0.5$-competitive algorithm First Fit (the result holds for any $n \geq 2$). We present the first algorithm that beats this ratio, achieving the competitive ratio of $1/(1+\ln(2))-O(1/n) \approx 0.5906 - O(1/n)$. Our algorithm is deterministic and optimal up to lower-order terms, as the upper bound of $1/(1+\ln(2))$ for randomized solutions was given previously by Cygan et al. [TOCS 2016]. Furthermore, we show that the lower-order term is inevitable for deterministic algorithms, by improving their upper bound to $1/(1+\ln(2))-O(1/n)$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Dynamic Balanced Graph Partitioning

This paper initiates the study of the classic balanced graph partitioning problem from an online perspective: Given an arbitrary sequence of pairwise communication requests between $n$ nodes, with patterns that may change over time, the objective is to service these requests efficiently by partitioning the nodes into $\ell$ clusters, each of size $k$, such that frequently communicating nodes are located in the same cluster. The partitioning can be updated dynamically by migrating nodes between clusters. The goal is to devise online algorithms which jointly minimize the amount of inter-cluster communication and migration cost. The problem features interesting connections to other well-known online problems. For example, scenarios with $\ell=2$ generalize online paging, and scenarios with $k=2$ constitute a novel online variant of maximum matching. We present several lower bounds and algorithms for settings both with and without cluster-size augmentation. In particular, we prove that any deterministic online algorithm has a competitive ratio of at least $k$, even with significant augmentation. Our main algorithmic contributions are an $O(k \log{k})$-competitive deterministic algorithm for the general setting with constant augmentation, and a constant competitive algorithm for the maximum matching variant.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Unbounded lower bound for k-server against weak adversaries

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\le 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+ε) \cdot 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 $Ω(\log \log h)$, even as $k\to\infty$. 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.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Online Algorithms for Multi-Level Aggregation

In the Multi-Level Aggregation Problem (MLAP), requests arrive at the nodes of an edge-weighted tree T, and have to be served eventually. A service is defined as 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 waiting cost between its arrival and service times. The objective is to minimize the total waiting cost of all requests plus the total cost of all service subtrees. MLAP is a generalization of some well-studied optimization problems; for example, for trees of depth 1, MLAP is equivalent to the TCP Acknowledgment Problem, while for trees of depth 2, it is equivalent to the Joint Replenishment Problem. Aggregation problem for trees of arbitrary depth arise in multicasting, sensor networks, communication in organization hierarchies, and in supply-chain management. The instances of MLAP associated with these applications are naturally online, in the sense that aggregation decisions need to be made without information about future requests. Constant-competitive online algorithms are known for MLAP with one or two levels. However, it has been open whether there exist constant competitive online algorithms for trees of depth more than 2. Addressing this open problem, we give the first constant competitive online algorithm for networks of arbitrary (fixed) number of levels. The competitive ratio is O(D^4 2^D), where D is the depth of T. The algorithm works for arbitrary waiting cost functions, including the variant with deadlines. We also show several additional lower and upper bound results for some special cases of MLAP, including the Single-Phase variant and the case when the tree is a path.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Approximation Algorithms for the Joint Replenishment Problem with Deadlines

The Joint Replenishment Problem (JRP) is a fundamental optimization problem in supply-chain management, concerned with optimizing the flow of goods from a supplier to retailers. Over time, in response to demands at the retailers, the supplier ships orders, via a warehouse, to the retailers. The objective is to schedule these orders to minimize the sum of ordering costs and retailers' waiting costs. We study the approximability of JRP-D, the version of JRP with deadlines, where instead of waiting costs the retailers impose strict deadlines. We study the integrality gap of the standard linear-program (LP) relaxation, giving a lower bound of 1.207, a stronger, computer-assisted lower bound of 1.245, as well as an upper bound and approximation ratio of 1.574. The best previous upper bound and approximation ratio was 1.667; no lower bound was previously published. For the special case when all demand periods are of equal length we give an upper bound of 1.5, a lower bound of 1.2, and show APX-hardness.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Better Approximation Bounds for the Joint Replenishment Problem

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, retailers incur waiting costs 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 APX-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. 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.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

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

In the online packet buffering problem (also known as the unweighted FIFO variant of buffer management), we focus on a single network packet switching device with several input ports and one output port. This device forwards unit-size, unit-value packets from input ports to the output port. Buffers attached to input ports may accumulate incoming packets for later transmission; if they cannot accommodate all incoming packets, their excess is lost. A packet buffering algorithm has to choose from which buffers to transmit packets in order to minimize the number of lost packets and thus maximize the throughput. We present a tight lower bound of e/(e-1) ~ 1.582 on the competitive ratio of the throughput maximization, which holds even for fractional or randomized algorithms. This improves the previously best known lower bound of 1.4659 and matches the performance of the algorithm Random Schedule. Our result contradicts the claimed performance of the algorithm Random Permutation; we point out a flaw in its original analysis.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Online Strategies for Intra and Inter Provider Service Migration in Virtual Networks

Network virtualization allows one to build dynamic distributed systems in which resources can be dynamically allocated at locations where they are most useful. In order to fully exploit the benefits of this new technology, protocols need to be devised which react efficiently to changes in the demand. This paper argues that the field of online algorithms and competitive analysis provides useful tools to deal with and reason about the uncertainty in the request dynamics, and to design algorithms with provable performance guarantees. As a case study, we describe a system (e.g., a gaming application) where network virtualization is used to support thin client applications for mobile devices to improve their QoS. By decoupling the service from the underlying resource infrastructure, it can be migrated closer to the current client locations while taking into account migration cost. This paper identifies the major cost factors in such a system, and formalizes the corresponding optimization problem. Both randomized and deterministic, gravity center based online algorithms are presented which achieve a good tradeoff between improved QoS and migration cost in the worst-case, both for service migration within an infrastructure provider as well as for networks supporting cross-provider migration. The paper reports on our simulation results and also presents an explicit construction of an optimal offline algorithm which allows, e.g., to evaluate the competitive ratio empirically.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Dynamic sharing of a multiple access channel

In this paper we consider the mutual exclusion problem on a multiple access channel. Mutual exclusion is one of the fundamental problems in distributed computing. In the classic version of this problem, n processes perform a concurrent program which occasionally triggers some of them to use shared resources, such as memory, communication channel, device, etc. The goal is to design a distributed algorithm to control entries and exits to/from the shared resource in such a way that in any time there is at most one process accessing it. We consider both the classic and a slightly weaker version of mutual exclusion, called ep-mutual-exclusion, where for each period of a process staying in the critical section the probability that there is some other process in the critical section is at most ep. We show that there are channel settings, where the classic mutual exclusion is not feasible even for randomized algorithms, while ep-mutual-exclusion is. In more relaxed channel settings, we prove an exponential gap between the makespan complexity of the classic mutual exclusion problem and its weaker ep-exclusion version. We also show how to guarantee fairness of mutual exclusion algorithms, i.e., that each process that wants to enter the critical section will eventually succeed.

0 citations0 reviewsNo code linkedOpen access
preprint2008arXiv

Generalized Whac-a-Mole

We consider online competitive algorithms for the problem of collecting weighted items from a dynamic set S, when items are added to or deleted from S over time. The objective is to maximize the total weight of collected items. We study the general version, as well as variants with various restrictions, including the following: the uniform case, when all items have the same weight, the decremental sets, when all items are present at the beginning and only deletion operations are allowed, and dynamic queues, where the dynamic set is ordered and only its prefixes can be deleted (with no restriction on insertions). The dynamic queue case is a generalization of bounded-delay packet scheduling (also referred to as buffer management). We present several upper and lower bounds on the competitive ratio for these variants.

0 citations0 reviewsNo code linkedOpen access