Marek Chrobak

TCS Journal 2025 Journal Article

A tight threshold bound for search trees with 2-way comparisons

• Sunny Atalig
• Marek Chrobak

We study search trees with 2-way comparisons (2wcst’s), which involve separate less-than and equal-to tests in their nodes, each test having two possible outcomes, yes and no. These trees have a much subtler structure than standard search trees with 3-way comparisons (3wcst’s) and are still not well understood, hampering progress towards designing an efficient algorithm for computing minimum-cost trees. One question that attracted attention in the past is whether there is an easy way to determine which type of comparison should be applied at any step of the search. In 2002, Anderson, Kannan, Karloff and Ladner studied this in terms of the ratio between the maximum and total key weight, and defined two threshold values: λ − is the largest ratio that forces the less-than test, and λ + is the smallest ratio that admits the equal-to test. They determined that λ − = 1 4, but for the higher threshold they only showed that λ + ∈ [ 3 7, 4 9 ]. We give the tight bound for the higher threshold, by proving that in fact λ + = 3 7.

I&C Journal 2021 Journal Article

Information gathering in ad-hoc radio networks

• Marek Chrobak
• Kevin P. Costello
• Leszek Gąsieniec

In the ad-hoc radio network model, nodes communicate with their neighbors via radio signals, without knowing the topology of the underlying digraph. We study the information gathering problem, where each node has a piece of information called a rumor, and the objective is to transmit all rumors to the designated target node. For the model without any collision detection we provide an O ˜ ( n 1. 5 ) deterministic protocol, significantly improving the trivial bound of O ( n 2 ). We also consider a model with a mild form of collision detection, where a node receives a 1-bit acknowledgment if its transmission was received by at least one out-neighbor. For this model we give an O ˜ ( n ) deterministic protocol for information gathering in acyclic graphs.

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.

I&C Journal 2021 Journal Article

On the cost of unsuccessful searches in search trees with two-way comparisons

• Marek Chrobak
• Mordecai Golin
• J. Ian Munro
• Neal E. Young

Search trees are commonly used to implement access operations to a set of stored keys. If this set is static and the probabilities of membership queries are known in advance, then one can precompute an optimal search tree, namely one that minimizes the expected access cost. For a non-key query, a search tree can determine its approximate location by returning the inter-key interval containing the query. This is in contrast to other dictionary data structures, like hash tables, that only report a failed search. We address the question “what is the additional cost of determining approximate locations for non-key queries”? We prove that for two-way comparison trees this additional cost is at most 1. Our proof is based on a novel probabilistic argument that involves converting a search tree that does not identify non-key queries into a random tree that does.

TCS Journal 2020 Journal Article

Towards a theory of mixing graphs: A characterization of perfect mixability

• Miguel Coviello Gonzalez
• Marek Chrobak

Some microfluidic lab-on-chip devices contain modules whose function is to mix two fluids, called reactant and buffer, in desired proportions. In one of the technologies for fluid mixing the process can be represented by a directed acyclic graph whose nodes represent micro-mixers and edges represent micro-channels. A micro-mixer has two input channels and two output channels; it receives two fluid droplets, one from each input, mixes them perfectly, and produces two droplets of the mixed fluid on its output channels. Such a mixing graph converts a set I of input droplets into a set T of output droplets, where the droplets are specified by their reactant concentrations. The most fundamental algorithmic question related to mixing graphs is to determine, given an input set I and a target set T, whether there is a mixing graph that converts I into T. We refer to this decision problem as mix-reachability. While the complexity of this problem remains open, we provide a solution to its natural sub-problem, called perfect mixability, in which we ask whether, given a collection C of droplets, there is a mixing graph that mixes C perfectly, producing only droplets whose concentration is the average concentration of C. We provide a complete characterization of such perfectly mixable sets and an efficient algorithm for testing perfect mixability. Further, we prove that any perfectly mixable set has a perfect-mixing graph of polynomial size, and that this graph can be computed in polynomial time.

SODA Conference 2019 Conference Paper

A ϕ-Competitive Algorithm for Scheduling Packets with Deadlines

• Pavel Veselý 0001
• Marek Chrobak
• Lukasz Jez
• Jirí Sgall

In the online packet scheduling problem with deadlines (PacketScheduling, for short), the goal is to schedule transmissions of packets that arrive over time in a network switch and need to be sent across a link. Each packet has a deadline, representing its urgency, and a non-negative weight, that represents its priority. Only one packet can be transmitted in any time slot, so, if the system is overloaded, some packets will inevitably miss their deadlines and be dropped. In this scenario, the natural objective is to compute a transmission schedule that maximizes the total weight of packets which are successfully transmitted. The problem is inherently online, with the scheduling decisions made without the knowledge of future packet arrivals. The central problem concerning PacketScheduling, that has been a subject of intensive study since 2001, is to determine the optimal competitive ratio of online algorithms, namely the worst-case ratio between the optimum total weight of a schedule (computed by an offline algorithm) and the weight of a schedule computed by a (deterministic) online algorithm. We solve this open problem by presenting a ϕ -competitive online algorithm for PacketScheduling (where ϕ ≈ 1. 618 is the golden ratio), matching the previously established lower bound.

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 2019 Journal Article

Online packet scheduling with bounded delay and lookahead

• Martin Böhm
• Marek Chrobak
• Łukasz Jeż
• Fei Li
• Jiří Sgall
• Pavel Veselý

We study the online bounded-delay packet scheduling problem (PacketScheduling), where packets of unit size arrive at a router over time and need to be transmitted over a network link. Each packet has two attributes: a non-negative weight and a deadline for its transmission. The objective is to maximize the total weight of the transmitted packets. This problem has been well studied in the literature; yet currently the best published upper bound is 1. 828 [8], still quite far from the best lower bound of ϕ ≈ 1. 618 [11, 2, 6]. In the variant of PacketScheduling with s-bounded instances, each packet can be scheduled in at most s consecutive slots, starting at its release time. The lower bound of ϕ applies even to the special case of 2-bounded instances, and a ϕ-competitive algorithm for 3-bounded instances was given in [5]. Improving that result, and addressing a question posed by Goldwasser [9], we present a ϕ-competitive algorithm for 4-bounded instances. We also study a variant of PacketScheduling where an online algorithm has the additional power of 1-lookahead, knowing at time t which packets will arrive at time t + 1. For PacketScheduling with 1-lookahead restricted to 2-bounded instances, we present an online algorithm with competitive ratio 1 2 ( 13 − 1 ) ≈ 1. 303 and we prove a nearly tight lower bound of 1 4 ( 1 + 17 ) ≈ 1. 281. In fact, our lower bound result is more general: using only 2-bounded instances, for any integer ℓ ≥ 0 we prove a lower bound of 1 2 ( ℓ + 1 ) ( 1 + 5 + 8 ℓ + 4 ℓ 2 ) for online algorithms with ℓ-lookahead, i. e. , algorithms that at time t can see all packets arriving by time t + ℓ. Finally, for non-restricted instances we show a lower bound of 1. 25 for randomized algorithms with ℓ-lookahead, for any ℓ ≥ 0.

I&C Journal 2018 Journal Article

Information gathering in ad-hoc radio networks with tree topology

• Marek Chrobak
• Kevin P. Costello
• Leszek Gasieniec
• Dariusz R. Kowalski

We study the problem of information gathering in ad-hoc radio networks, focusing on the case when the network forms a tree, with edges directed towards the root. Initially, each node has a rumor, and we aim to deliver all rumors to the root as quickly as possible without knowing the tree's topology in advance. In the deterministic case, where nodes are labeled with small integers, we give an O ( n ) -time protocol for the model with unbounded message size, and an O ( n log ⁡ n ) -time protocol for bounded message size. We also consider fire-and-forward protocols, in which nodes can transmit only their own rumor or the rumor received in the previous step. We give a deterministic fire-and-forward protocol with running time O ( n 1. 5 ), and show that it is asymptotically optimal. We also present a randomized O ( n log ⁡ n ) -time protocol in the model without node labels or aggregation, and show that it is asymptotically optimal.

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 2013 Journal Article

Better bounds for incremental frequency allocation in bipartite graphs

• Marek Chrobak
• Łukasz Jeż
• Jiří Sgall

We study frequency allocation in wireless networks. A wireless network is modeled by an undirected graph, with vertices corresponding to cells. In each vertex, we have a certain number of requests, and each of those requests must be assigned a different frequency. Edges represent conflicts between cells, meaning that frequencies in adjacent vertices must be different as well. The objective is to minimize the total number of used frequencies. The offline version of the problem is known to be NP-hard. In the incremental version, requests for frequencies arrive over time and the algorithm is required to assign a frequency to a request as soon as it arrives. Competitive incremental algorithms have been studied for several classes of graphs. For paths, the optimal (asymptotic) ratio is known to be 4/3, while for hexagonal-cell graphs it is between 1. 5 and 1. 9126. For ξ -colorable graphs, the ratio of ( ξ + 1 ) / 2 can be achieved. In this paper, we prove nearly tight bounds on the asymptotic competitive ratio for bipartite graphs, showing that it is between 1. 428 and 1. 433. This improves the previous lower bound of 4/3 and upper bound of 1. 5. Our proofs are based on reducing the incremental problem to a purely combinatorial (equivalent) problem of constructing set families with certain intersection properties.

TCS Journal 2011 Journal Article

Better bounds for incremental medians

• Marek Chrobak
• Mathilde Hurand

In the incremental version of the well-known k - m e d i a n p r o b l e m, the objective is to compute an incremental sequence of facility sets F 1 ⊆ F 2 ⊆ ⋯ ⊆ F n, where each F k contains at most k facilities. We say that this incremental medians sequence is R -competitive if the cost of each F k is at most R times the optimum cost of k facilities. The smallest such R is called the competitive ratio of the sequence { F k }. Mettu and Plaxton [Ramgopal R. Mettu, C. Greg Plaxton, The online median problem, in: Proc. 41st Symposium on Foundations of Computer Science, FOCS, IEEE, 2000, pp. 339–348; Ramgopal R. Mettu, C. Greg Plaxton, The online median problem, SIAM Journal on Computing 32 (3) (2003) 816–832] presented a polynomial-time algorithm that computes an incremental sequence with competitive ratio ≈30. They also showed a lower bound of 2. The upper bound on the ratio was improved to 8 in [Guolong Lin, Chandrashekha Nagarajan, Rajmohan Rajamaran, David P. Williamson, A general approach for incremental approximation and hierarchical clustering, in: Proc. 17th Symposium on Discrete Algorithms, SODA, 2006, pp. 1147–1156] and [Marek Chrobak, Claire Kenyon, John Noga, Neal Young, Online medians via online bidding, in: Proc. 7th Latin American Theoretical Informatics Symposium, LATIN, in: Lecture Notes in Computer Science, vol. 3887, 2006, pp. 311–322]. We improve both bounds in this paper. We first show that no incremental sequence can have competitive ratio better than 2. 01 and we give a probabilistic construction of a sequence whose competitive ratio is at most 2 + 4 2 ≈ 7. 656. We also propose a new approach to the problem that for instances that we refer to as equable achieves an optimal ratio of 2.

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.

TCS Journal 2010 Journal Article

Three results on frequency assignment in linear cellular networks

• Marek Chrobak
• Jiří Sgall

In the frequency assignment problem we are given a graph representing a wireless network and a sequence of requests, where each request is associated with a vertex. Each request has two more attributes: its arrival and departure times, and it is considered active from the time of arrival to the time of departure. We want to assign frequencies to all requests so that at each time step any two active requests associated with the same or adjacent vertices use different frequencies. The objective is to minimize the number of frequencies used. We focus exclusively on the special case of the problem when the underlying graph is a linear network (path). For this case, we consider both the offline and online versions of the problem, and we present three results. First, in the incremental online case, where the requests arrive over time, but never depart, we give an algorithm with an optimal (asymptotic) competitive ratio 4 3. Second, in the general online case, where the requests arrive and depart over time, we improve the current lower bound on the (asymptotic) competitive ratio to 11 7. Third, we prove that the offline version of this problem is N P -complete.

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

SODA Conference 2004 Conference Paper

The wake-up problem in multi-hop radio networks

• Marek Chrobak
• Leszek Gasieniec
• Dariusz R. Kowalski

TCS Journal 2004 Journal Article

The weighted 2-server problem

• Marek Chrobak
• Jiřı́ Sgall

We consider a generalization of the 2-server problem in which servers have different costs. We prove that, in uniform spaces, a version of the work function algorithm is 5-competitive, and that no better ratio is possible. We also give a 5-competitive randomized, memoryless algorithm for uniform spaces, and a matching lower bound. For arbitrary metric spaces, in contrast with the non-weighted case, we prove that there is no memoryless randomized algorithm with finite competitive ratio. We also propose a version of the problem in which a request specifies two points to be covered by the servers, and the algorithm must decide which server to move to which point. For this version, we show a 9-competitive algorithm and we prove that no better ratio is possible.

TCS Journal 2003 Journal Article

Errata to: “Finite Automata and Unary Languages”

• Marek Chrobak

MFCS Conference 2003 Conference Paper

Faster Algorithms for k -Medians in Trees

• Robert Benkoczi
• Binay K. Bhattacharya
• Marek Chrobak
• Lawrence L. Larmore
• Wojciech Rytter

Abstract In the k -median problem we are given a connected graph with non-negative weights associated with the nodes and lengths associated with the edges. The task is to compute locations of k facilities in order to minimize the sum of the weighted distances between each node and its closest facility. In this paper we consider the case when the graph is a tree. We show that this problem can be solved in time \(O(n {\mbox{\rm polylog}} (n))\) for the following cases: (i) directed trees (and any fixed k ), (ii) balanced undirected trees, and (iii) undirected trees with k =3.

TCS Journal 2003 Journal Article

More on randomized on-line algorithms for caching

• Marek Chrobak
• Elias Koutsoupias
• John Noga

We address the tradeoff between the competitive ratio and the resources used by randomized on-line algorithms for caching. Two algorithms reported in the literature that achieve the optimal ratio H k require a lot of memory and perform extensive computation at each step. On the other hand, a very simple algorithm called RMARK has competitive ratio 2H k −1, within a factor of 2 of the optimum. A natural question that arises here is whether there is a tradeoff between simplicity and the competitive ratio. In particular, is it possible to achieve a competitive ratio better than 2H k −1 with a simple algorithm like RMARK? We first consider marking algorithms that are natural generalizations of RMARK, and we prove that, for any ε>0, there is no randomized marking algorithm for caching with competitive ratio (2−ε)H k. Thus RMARK is essentially optimal among marking algorithms. Another model of simple caching algorithms is that of trackless algorithms. These are algorithms that do not store any information about items that are not in the cache. It is known that, for k=2, there is no randomized trackless algorithm for caching with ratio better than 37 24 ≈1. 5416. The trivial upper bound is 2, achieved even by deterministic algorithms LRU and FIFO. We reduce this gap by giving a trackless randomized algorithm with competitive ratio 1 4 (3+ 13 )≈1. 6514.

TCS Journal 2003 Journal Article

On tiling under tomographic constraints

• Marek Chrobak
• Peter Couperus
• Christoph Dürr
• Gerhard Woeginger

Given a tiling of a 2D grid with several types of tiles, we can count for every row and column how many tiles of each type it intersects. These numbers are called the projections. We are interested in the problem of reconstructing a tiling which has given projections. Some simple variants of this problem, involving tiles that are 1×1 or 1×2 rectangles, have been studied in the past, and were proved to be either solvable in polynomial time or NP -complete. In this note, we make progress toward a comprehensive classification of various tiling reconstruction problems, by proving NP -completeness results for several sets of tiles.

TCS Journal 2002 Journal Article

Solution of a problem in DNA computing

• Eric Anderson
• Marek Chrobak
• John Noga
• Jiřı́ Sgall
• Gerhard J. Woeginger

We answer a question of Rozenberg and Salomaa arising from a problem in DNA computing. This problem was posed at the ICALP conference in July 1999 in Prague.

TCS Journal 2002 Journal Article

The 3-server problem in the plane

• Wolfgang W. Bein
• Marek Chrobak
• Lawrence L. Larmore

In the k-server problem we wish to minimize, in an online fashion, the movement cost of k servers in response to a sequence of requests (we assume that k⩾2). The request issued at each step is specified by a point r in a given metric space M. To serve this request, one of the k servers must move to r. It is known that if M has at least k+1 points then no online algorithm for the k-server problem in M has competitive ratio smaller than k. The best known upper bound on the competitive ratio in arbitrary metric spaces, by Koutsoupias and Papadimitriou (J. ACM 42 (1995) 971), is 2k−1. There are only a few special cases for which k-competitive algorithms are known: for k=2, when M is a tree, or when M has at most k+2 points. We prove that the Work Function Algorithm is 3-competitive for the 3-server problem in the Manhattan plane. As a corollary, we obtain a 4. 243-competitive algorithm for 3 servers in the Euclidean plane. The best previously known competitive ratio for 3 servers in these metric spaces was 5.

TCS Journal 2001 Journal Article

Reconstructing polyatomic structures from discrete X-rays: NP-completeness proof for three atoms

• Marek Chrobak
• Christoph Dürr

We address a discrete tomography problem that arises in the study of the atomic structure of crystal lattices. A polyatomic structure T can be defined as an integer lattice in dimension D⩾2, whose points may be occupied by c distinct types of atoms. To “analyze” T, we conduct ℓ measurements that we call discrete X-rays. A discrete X-ray in direction ξ determines the number of atoms of each type on each line parallel to ξ. Given ℓ such non-parallel X-rays, we wish to reconstruct T. The complexity of the problem for c=1 (one atom type) has been completely determined by Gardner et al. (Technical Report 970. 05012, Techn. Univ. München, Fak. f. Math. , 1997), who proved that the problem is NP-complete for any dimension D⩾2 and ℓ⩾3 non-parallel X-rays, and that it can be solved in polynomial time otherwise Ryser (Mathematical Association of America and Quinn & Boden, Rahway, New Jersey, 1963). The NP-completeness result above clearly extends to any c⩾2, and therefore when studying the polyatomic case we can assume that ℓ=2. As shown in another article by the same authors (Gardner et al. , Theoret. Comput. Sci. (1997), to appear), this problem is also NP-complete for c⩾6 atoms, even for dimension D=2 and axis-parallel X-rays. Gardner et al. (1997) conjecture that the problem remains NP-complete for c=3, 4, 5, although, as they point out, the proof idea in Gardner et al. (1997) does not seem to extend to c⩽5. We resolve the conjecture from Gardner et al. (1997) by proving that the problem is indeed NP-complete for c⩾3 in 2D, even for axis-parallel X-rays. Our construction relies heavily on some structure results for the realizations of 0–1 matrices with given row and column sums.

MFCS Conference 2001 Conference Paper

The k-Median Problem for Directed Trees

• Marek Chrobak
• Lawrence L. Larmore
• Wojciech Rytter

Abstract The k -median problem is a classical facility location problem. We consider the k -median problem for directed trees, motivated by the problem of locating proxies on the World Wide Web. The two main results of the paper are an O(n log n) time algorithm for k=2 and an O(n log 2 n) time algorithm for k=3. The previously known upper bounds for these two cases were O ( n 2 ).

I&C Journal 2000 Journal Article

A Randomized Algorithm for Two Servers on the Line

• Yair Bartal
• Marek Chrobak
• Lawrence L Larmore

In the k-server problem we wish to minimize, in an online fashion, the movement cost of k servers in response to a sequence of requests. For two servers, it is known that the optimal deterministic algorithm has competitive ratio 2, and it has been a long-standing open problem whether it is possible to improve this ratio using randomization. We give a positive answer to this problem when the underlying metric space is a real line, by providing a randomized online algorithm for this case with competitive ratio at most 155 78 ≈1. 987. This is the first algorithm for two servers that achieves a competitive ratio smaller than 2 in a nonuniform metric space with more than three points. We consider a more general problem called the (k, l)-server problem, in which a request is served using l out of k available servers. We show that the randomized 2-server problem can be reduced to the deterministic (2l, l)-server problem. We prove a lower bound of 2 on the competitive ratio of the (4, 2)-server problem. This implies that one unbiased random bit is not sufficient to improve the ratio of 2 for the two-server problem. Then we give a 155 78 -competitive algorithm for the (6, 3)-server problem on the real line. Our algorithm is simple and memoryless. The solution has been obtained using linear programming techniques that may have applications for other online problems.

TCS Journal 2000 Journal Article

Competitive analysis of randomized paging algorithms

• Dimitris Achlioptas
• Marek Chrobak
• John Noga

The paging problem is defined as follows: we are given a two-level memory system, in which one level is a fast memory, called cache, capable of holding k items, and the second level is an unbounded but slow memory. At each given time step, a request to an item is issued. Given a request to an item p, a miss occurs if p is not present in the fast memory. In response to a miss, we need to choose an item q in the cache and replace it by p. The choice of q needs to be made on-line, without the knowledge of future requests. The objective is to design a replacement strategy with a small number of misses. In this paper we use competitive analysis to study the performance of randomized on-line paging algorithms. Our goal is to show how the concept of work functions, used previously mostly for the analysis of deterministic algorithms, can also be applied, in a systematic fashion, to the randomized case. We present two results: we first show that the competitive ratio of the marking algorithm is exactly 2Hk−1. Previously, it was known to be between Hk and 2Hk. Then we provide a new, Hk -competitive algorithm for paging. Our algorithm, as well as its analysis, is simpler than the known algorithm by McGeoch and Sleator. Another advantage of our algorithm is that it can be implemented with complexity bounds independent of the number of past requests: O(k2 log k) memory and O(k2) time per request.

FOCS Conference 2000 Conference Paper

Fast Broadcasting and Gossiping in Radio Networks

• Marek Chrobak
• Leszek Gasieniec
• Wojciech Rytter

We establish an O(n log/sup 2/n) upper bound on the time for deterministic distributed broadcasting in multi-hop radio networks with unknown topology. This nearly matches the known lower bound of /spl Omega/(n log n). The fastest previously known algorithm for this problem works in time O(n/sup 3/2/). Using our broadcasting algorithm, we develop an O(n/sup 3/2/log/sup 2/n) algorithm for gossiping in the same network model.

SODA Conference 1998 Conference Paper

Competive Algorithms for Multilevel Caching and Relaxed List Update (Extended Abstract)

• Marek Chrobak
• John Noga

SODA Conference 1998 Conference Paper

LRU is Better than FIFO

• Marek Chrobak
• John Noga

MFCS Conference 1998 Conference Paper

Reconstructing Polyatomic Structures from Discrete X-Rays: NP-Completeness Proof for Three Atoms

• Marek Chrobak
• Christoph Dürr

Abstract We address a discrete tomography problem that arises in the study of the atomic structure of crystal lattices. A polyatomic structure T can be defined as an integer lattice in dimension D ≥2, whose points may be occupied by c distinct types of atoms. To “analyze” T, we conduct ℓ measurements that we call discrete X-rays. A discrete X-ray in direction ξ determines the number of atoms of each type on each line parallel to ξ. Given ℓ such non-parallel X-rays, we wish to reconstruct T. The complexity of the problem for c =1 (one atom type) has been completely determined by Gardner, Gritzmann and Prangerberg [5], who proved that the problem is NP-complete for any dimension D ≥ 2 and ℓ ≥ 3 non-parallel X-rays, and that it can be solved in polynomial time otherwise [8]. The NP-completeness result above clearly extends to any c ≥ 2, and therefore when studying the polyatomic case we can assume that ℓ = 2. As shown in another article by the same authors, [4], this problem is also NP-complete for c ≥ 6 atoms, even for dimension D = 2 and axis-parallel X-rays. The authors of [4] conjecture that the problem remains NP-complete for c =3, 4, 5, although, as they point out, the proof idea in [4] does not seem to extend to c ≤ 5. We resolve the conjecture from [4] by proving that the problem is indeed NP-complete for c ≥ 3 in 2D, even for axis-parallel X-rays. Our construction relies heavily on some structure results for the realizations of 0–1 matrices with given row and column sums.

TCS Journal 1994 Journal Article

Two results on linear embeddings of complete binary trees

• Marek Chrobak
• Wojciech Rytter

Given a binary tree T with n vertices, we want to embed T onto a given set A of n points on the line so as to minimize the total embedded edge length. Polynomial-time algorithms for the two following special cases of this problem can be found in the literature: 1. when T is arbitrary but A = {1…n}. 2. when T is a complete binary tree and A is arbitrary. To the best of our knowledge, the complexity of the general problem is open. In this paper we deal with case (2). Bern et al. presented an algorithm for this case that runs in time O(n 5. 76) and uses O(n 3. 2) space. They also considered the naive embedding, which maps the root r of T into the middle point a of A, and then embeds, recursively, the left and right subtrees of r to the left and right of a, respectively. This is equivalent to embedding T from left to right according to the inorder traversal. They prove that this naive algorithm approximates the optimal solution within the factor of 3. The main results of this paper are: (i) the proof that the approximation ratio of this naive algorithm is exactly 7 3, and (ii) a more efficient algorithm for computing minimum embeddings of complete binary trees. Our algorithm runs in time O (n 1 + log 3) = O(n 2. 59), and uses O (n) space, where O (f) = O(f log c n), for some constant c > 0.

SODA Conference 1992 Conference Paper

Generosity Helps, or an 11-Competitive Algorithm for Three Servers

• Marek Chrobak
• Lawrence L. Larmore

TCS Journal 1992 Journal Article

HARMONIC is 3-competitive for two servers

• Marek Chrobak
• Lawrence L. Larmore

We consider the server algorithm, called HARMONIC, that always moves the servers with probabilities proportional to the inverses of distances to the request point. We show that for two servers HARMONIC is 3-competitive. Before it was only known that the competitiveness constant of this algorithm is between 3 and 6.

SODA Conference 1991 Conference Paper

Efficient Sequential and Parallel Algorithms for Computing Recovery Points in Trees and Paths

• Marek Chrobak
• David Eppstein
• Giuseppe F. Italiano
• Moti Yung

TCS Journal 1991 Journal Article

Planar orientations with low out-degree and compaction of adjacency matrices

• Marek Chrobak
• David Eppstein

We consider the problem of orienting the edges of a planar graph in such a way that the out-degree of each vertex is minimized. If, for each vertex v, the out-degree is at most d, then we say that such an orientation is d-bounded. We prove the following results: • Each planar graph has a 5-bounded acyclic orientation, which can be constructed in linear time. • Each planar graph has a 3-bounded orientation, which can be constructed in linear time. • A 6-bounded acyclic orientation, and a 3-bounded orientation, of each planar graph can each be constructed in parallel time O(log n log∗ n) on an EREW PRAM, using O(n/log n log∗ n) processors. As an application of these results, we present a data structure such that each entry in the adjacency matrix of a planar graph can be looked up in constant time. The data structure uses linear storage, and can be constructed in linear time.

SODA Conference 1990 Conference Paper

New Results on Server Problems

• Marek Chrobak
• Howard J. Karloff
• T. H. Payne
• Sundar Vishwanathan

MFCS Conference 1990 Conference Paper

On Fast Algorithms for Two Servers

• Marek Chrobak
• Lawrence L. Larmore

Abstract We consider 2-server algorithms with time complexity O (1) per each request. We show that the previously known algorithm BALANCE2 has competitiveness constant not better than 6, and present another algorithm whose competitiveness constant is 4.

TCS Journal 1986 Journal Article

Finite automata and unary languages

• Marek Chrobak

We prove that O(e√n log n ) states are sufficient to simulate an n-state 1nfa recognizing a unary language by a 1dfa. The lower bound is the same. Similar tight bounds are shown for the simulation of a 2dfa by a 1dfa and a 1nfa. We also show that O(n 2) states are sufficient and necessary to simulate an n-state 1nfa recognizing a unary language by a 2dfa.

TCS Journal 1986 Journal Article

Hierarchies of one-way multihead automata languages

• Marek Chrobak

Let DPDA(k) (respectively NPDA(k)) be the class of languages recognized by one-way k-head deterministic (respectively nondeterministic) pushdown automata. The main result of this paper is that, for every k>0, DPDA(k) ⊊ DPDA(k+1) and DPDA(k) ⊊NPDA(k).

FOCS Conference 1986 Conference Paper

k+1 Heads Are Better than k for PDA's

• Marek Chrobak
• Ming Li 0001

We resolve the following long-standing conjecture of Harrison and Ibarra in 1968 [HI, p. 462]: There are languages accepted by (k+1)-head 1-way deterministic pushdown automata ((k+1)-DPDA) but not by k-head 1-way pushdown automata (k-PDA), for every k. (Partial solutions for this conjecture can be found in [M1, M2, C].) On the assumption that their conjecture holds, [HI] also derived many important consequences. Now all those consequences become theorems. For example, the class of languages accepted by k-PDA's is not closed under ∩ and complementation. Several other interesting consequences also follow: CFL ⊆∪kDPDA(k) and FA(2)⊆∪kDPDA(k), where DPDA (k)={L|L is accepted by a k-DPDA} and FA(2)={L|L is accepted by a 2-head FA). Our new proof itself is also interesting in the sense that the k+l versus k heads problems was solved by diagonalization methods [I2, M2, M3, M4, S] for stronger machines (2-way, etc). and by traditional counting arguments [S2, IK, YR, M1] for weaker machines (k-FA, k-head counter machine, etc).

MFCS Conference 1986 Conference Paper

Unique Deciperability for Partially Commutative Alphabet (Extended Abstract)

• Marek Chrobak
• Wojciech Rytter

Abstract We consider the unique decipherability problem for partially commutative alphabet. It is shown that the complexity of this problem depends heavily on the size of the alphabet and the structure of the commutativity relation graph. In particular, for alphabets with ≤3 letters the problem is decidable and for alphabets with ≥4 letters the problem is undecidable.

MFCS Conference 1984 Conference Paper

Nondeterminism Is Essential for Two-Way Counter Machines

• Marek Chrobak