Russell Martin

TCS Journal 2021 Journal Article

Maximum rooted connected expansion

• Ioannis Lamprou
• Russell Martin
• Sven Schewe
• Ioannis Sigalas
• Vassilis Zissimopoulos

Prefetching constitutes a valuable tool toward the goal of efficient Web surfing. As a result, estimating the amount of resources that need to be preloaded during a surfer's browsing becomes an important task. In this regard, prefetching can be modeled as a two-player combinatorial game (Fomin et al. (2014) [6]), where a surfer and a marker alternately play on a given graph (representing the Web graph). During its turn, the marker chooses a set of k nodes to mark (prefetch), whereas the surfer, represented as a token resting on graph nodes, moves to a neighboring node (Web resource). The surfer's objective is to reach an unmarked node before all nodes become marked and the marker wins. Intuitively, since the surfer is step-by-step traversing a subset of nodes in the Web graph, a satisfactory prefetching procedure would load in cache (without any delay) all resources lying in the neighborhood of this growing subset. Motivated by the above, we consider the following maximization problem to which we refer to as the Maximum Rooted Connected Expansion (MRCE) problem. Given a graph G and a root node v 0, we wish to find a subset of vertices S such that S is connected, S contains v 0 and the ratio | N [ S ] | | S | is maximized, where N [ S ] denotes the closed neighborhood of S, that is, N [ S ] contains all nodes in S and all nodes with at least one neighbor in S. We prove that the problem is NP-hard even when the input graph G is restricted to be a split graph. On the positive side, we demonstrate a Polynomial Time Approximation Scheme (PTAS) for split graphs. Furthermore, we present a 1 6 ( 1 − 1 e ) -approximation algorithm for general graphs based on techniques for the Budgeted Connected Domination problem (Khuller et al. (2014) [20]). Finally, we provide a polynomial-time algorithm for the special case of interval graphs. Our algorithm returns an optimal solution for MRCE in O ( n 3 ) time, where n is the number of nodes in G, and in logarithmic space.

TCS Journal 2020 Journal Article

Fast two-robot disk evacuation with wireless communication

• Ioannis Lamprou
• Russell Martin
• Sven Schewe

In the fast evacuation problem, we study the path planning problem for two robots who want to minimize the worst-case evacuation time on the unit disk, that is, the time till both of them evacuate. The robots are initially placed at the center of the disk. In order to evacuate, they need to reach an unknown point, the exit, on the boundary of the disk. Once one of the robots finds the exit, it will instantaneously, i. e. , using wireless communication, notify the other agent who will then follow a straight line to it. The problem has been studied for robots with the same speed [13]. We study a more general case where one robot has speed 1 and the other has speed s ≥ 1. We provide optimal evacuation strategies in the case that s ≥ 2. 75 by showing matching upper and lower bounds on the worst-case evacuation time. For 1 ≤ s < 2. 75, we show (non-matching) upper and lower bounds on the evacuation time with a ratio less than 1. 22. Moreover, we demonstrate that a different-speeds generalization of the two-robot search strategy from [13] is outperformed by our proposed strategies for any s ≥ 1. 71.

I&C Journal 2019 Journal Article

Communication and location discovery in geometric ring networks

• Leszek Gąsieniec
• Tomasz Jurdzinski
• Russell Martin
• Grzegorz Stachowiak

We study a distributed coordination mechanism for uniform agents located on a circle. The agents perform their actions in synchronized rounds. At the beginning of each round an agent chooses the direction of its movement from clockwise, anticlockwise, or idle, and moves at unit speed during this round. Agents are not allowed to overpass, i. e. , when an agent collides with another it instantly starts moving with the same speed in the opposite direction (without exchanging any information with the other agent). However, at the end of each round each agent has access to limited information regarding its trajectory of movement during this round. We assume that n mobile agents are initially located on a circle unit circumference at arbitrary but distinct positions unknown to other agents. The agents are equipped with unique identifiers from a fixed range. The location discovery task to be performed by each agent is to determine the initial position of every other agent. Our main result states that, if the only available information about movement in a round is limited to distance between the initial and the final position, then there is a superlinear lower bound on time needed to solve the location discovery problem. Interestingly, this result corresponds to a combinatorial symmetry breaking problem, which might be of independent interest. If, on the other hand, an agent has access to the distance to its first collision with another agent in a round, we design an asymptotically efficient and close to optimal solution for the location discovery problem. Assuming that agents are anonymous (there are no IDs distinguishing them), our solution applied to randomly chosen IDs from appropriately chosen range gives an (almost) optimal algorithm, improving upon the complexity of previous randomized results.

TCS Journal 2019 Journal Article

Eternally dominating large grids

• Ioannis Lamprou
• Russell Martin
• Sven Schewe

In the m-Eternal Domination game, a team of guard tokens initially occupies a dominating set on a graph G. An attacker then picks a vertex without a guard on it and attacks it. The guards defend against the attack: one of them has to move to the attacked vertex, while each remaining one can choose to move to one of his neighboring vertices. The new guards' placement must again be dominating. This attack-defend procedure continues eternally. The guards win if they can eternally maintain a dominating set against any sequence of attacks, otherwise the attacker wins. The m-eternal domination number for a graph G is the minimum amount of guards such that they win against any attacker strategy in G (all guards move model). We study rectangular grids and provide the first known general upper bound on the m-eternal domination number for these graphs. Our novel strategy implements a square rotation principle and eternally dominates m × n grids by using approximately m n 5 guards, which is asymptotically optimal even for ordinary domination.

TCS Journal 2015 Journal Article

Fundamentals of Computation Theory

• Leszek Gąsieniec
• Russell Martin
• Frank Wolter
• Prudence W.H. Wong

TCS Journal 2012 Journal Article

More efficient periodic traversal in anonymous undirected graphs

• Jurek Czyzowicz
• Stefan Dobrev
• Leszek Gąsieniec
• David Ilcinkas
• Jesper Jansson
• Ralf Klasing
• Ioannis Lignos
• Russell Martin

We consider the problem of periodic graph exploration in which a mobile entity with constant memory, an agent, has to visit all n nodes of an input simple, connected, undirected graph in a periodic manner. Graphs are assumed to be anonymous, that is, nodes are unlabeled. While visiting a node, the agent may distinguish between the edges incident to it; for each node v, the endpoints of the edges incident to v are uniquely identified by different integer labels called port numbers. We are interested in algorithms for assigning the port numbers together with traversal algorithms for agents using these port numbers to obtain short traversal periods. Periodic graph exploration is unsolvable if the port numbers are set arbitrarily; see Budach (1978) [1]. However, surprisingly small periods can be achieved by carefully assigning the port numbers. Dobrev et al. (2005) [4] described an algorithm for assigning port numbers and an oblivious agent (i. e. , an agent with no memory) using it, such that the agent explores any graph with n nodes within the period 10 n. When the agent has access to a constant number of memory bits, the optimal length of the period was proved in Gąsieniec et al. (2008) [7] to be no more than 3. 75 n − 2 (using a different assignment of the port numbers and a different traversal algorithm). In this paper, we improve both these bounds. More precisely, we show how to achieve a period length of at most ( 4 + 1 3 ) n − 4 for oblivious agents and a period length of at most 3. 5 n − 2 for agents with constant memory. To obtain our results, we introduce a new, fast graph decomposition technique called a three-layer partition that may also be useful for solving other graph problems in the future. Finally, we present the first non-trivial lower bound, 2. 8 n − 2, on the period length for the oblivious case.

TCS Journal 2012 Journal Article

The complexity of approximately counting stable matchings

• Prasad Chebolu
• Leslie Ann Goldberg
• Russell Martin

We investigate the complexity of approximately counting stable matchings in the k -attribute model, where the preference lists are determined by dot products of “preference vectors” with “attribute vectors”, or by Euclidean distances between “preference points “and “attribute points”. Irving and Leather (1986) [14] proved that counting the number of stable matchings in the general case is # P -complete. Counting the number of stable matchings is reducible to counting the number of downsets in a (related) partial order [14] and is interreducible, in an approximation-preserving sense, to a class of problems that includes counting the number of independent sets in a bipartite graph ( # B I S ) (Dyer et al. (2004) [6]). It is conjectured that no FPRAS exists for this class of problems. We show this approximation-preserving interreducibility remains even in the restricted k -attribute setting when k ≥ 3 (dot products) or k ≥ 2 (Euclidean distances). Finally, we show it is easy to count the number of stable matchings in the 1 -attribute dot-product setting.

TCS Journal 2008 Journal Article

On weighted balls-into-bins games

• Petra Berenbrink
• Tom Friedetzky
• Zengjian Hu
• Russell Martin

We consider the well-known problem of randomly allocating m balls into n bins. We investigate various properties of single-choice games as well as multiple-choice games in the context of weighted balls. We are particularly interested in questions that are concerned with the distribution of ball weights, and the order in which balls are allocated. Do any of these parameters influence the maximum expected load of any bin, and if yes, then how? The problem of weighted balls is of practical relevance. Balls-into-bins games are frequently used to conveniently model load balancing problems. Here, weights can be used to model resource requirements of the jobs, i. e. , memory or running time.