54 citations · 165 across the 36 of their papers we have counts for
44 papers
A 3.3904-Competitive Online Algorithm for List Update with Uniform Costs
Mateusz Basiak, Marcin Bienkowski, Martin Böhm +4
We consider the List Update problem where the cost of each swap is assumed to be 1. This is in contrast to the ``standard'' model, in which an algorithm is allowed to swap the requ…
Structural Properties of Search Trees with 2-way Comparisons
Sunny Atalig, Marek Chrobak, Erfan Mousavian +2
Optimal 3-way comparison search trees (3WCST's) can be computed using standard dynamic programming in time O(n^3), and this can be further improved to O(n^2) by taking advantage of…
Classification via Two-Way Comparisons
Marek Chrobak, Neal E. Young
Given a weighted, ordered query set and a partition of into classes, we study the problem of computing a minimum-cost decision tree that, given any query in , uses e…
Cross-chain Swaps with Preferences
Eric Chan, Marek Chrobak, Mohsen Lesani
Extreme valuation and volatility of cryptocurrencies require investors to diversify often which demands secure exchange protocols. A cross-chain swap protocol allows distrusting pa…
Better Hardness Results for the Minimum Spanning Tree Congestion Problem
Huong Luu, Marek Chrobak
In the spanning tree congestion problem, given a connected graph , the objective is to compute a spanning tree in that minimizes its maximum edge congestion, where the c…
Online Paging with Heterogeneous Cache Slots
Marek Chrobak, Samuel Haney, Mehraneh Liaee +4
It is natural to generalize the online -Server problem by allowing each request to specify not only a point , but also a subset of servers that may serve it. For uniform…