BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Marcin Bienkowski

Marcin Bienkowski contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Data Structures and Algorithms

Trust snapshot

Quick read

Trust 19 - UnverifiedVerification L1Unclaimed author
5works
0followers
1topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

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

Published work

5 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