Rajmohan Rajaraman
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Rajmohan Rajaraman has a total of 58 co-authors. Here are the top co-authors by number of shared publications:
- Ravi Sundaram
Northeastern University
7 shared publications - Shang-Hua Teng
Department of Computer Science, Boston University, Boston, MA 02215, USA
4 shared publications - Gopal Pandurangan
University of Houston, Houston, USA
3 shared publications Laura J. Poplawski
3 shared publications- Mehraneh Liaee
Northeastern University
3 shared publications - Chen Avin
Ben-Gurion University of the Negev, Beer Sheva, Israel
2 shared publications
Latest Publications
- 17 March 2026
- Published by Elsevier in Theoretical Computer Science
- Vol. 1073
Stability of peer-to-peer networks under greedy peering
- 17 March 2026
- Published by Elsevier in Theoretical Computer Science
- Vol. 1073
Stability of peer-to-peer networks under greedy peering
- Open Access
- 17 October 2024
- Published by Springer Nature in Algorithmica
- Vol. 87 (1) , 89-131
Online Paging with Heterogeneous Cache Slots
It is natural to generalize the online $$k$$ -Server problem by allowing each request to specify not only a point p, but also a subset S of servers that may serve it. To date, only a few special cases of this problem have been studied. The objective of the work presented in this paper has been to more systematically explore this generalization in the case of uniform and star metrics. For uniform metrics, the problem is equivalent to a generalization of Paging in which each request specifies not only a page p, but also a subset S of cache slots, and is satisfied by having a copy of p in some slot in S. We call this problem Slot-Heterogenous Paging. In realistic settings only certain subsets of cache slots or servers would appear in requests. Therefore we parameterize the problem by specifying a family $${\mathcal {S}}\subseteq 2^{[k]}$$ of requestable slot sets, and we establish bounds on the competitive ratio as a function of the cache size k and family $${\mathcal {S}}$$ : If all request sets are allowed ( $${\mathcal {S}}=2^{[k]}\setminus \{\emptyset \}$$ ), the optimal deterministic and randomized competitive ratios are exponentially worse than for standard Paging ( $${\mathcal {S}}=\{[k]\}$$ ). As a function of $$|{\mathcal {S}}|$$ and k, the optimal deterministic ratio is polynomial: at most $$O(k^2|{\mathcal {S}}|)$$ and at least $$\Omega (\sqrt{|{\mathcal {S}}|})$$ . For any laminar family $${\mathcal {S}}$$ of height h, the optimal ratios are O(hk) (deterministic) and $$O(h^2\log k)$$ (randomized). The special case of laminar $${\mathcal {S}}$$ that we call All-or-One Paging extends standard Paging by allowing each request to specify a specific slot to put the requested page in. The optimal deterministic ratio for weighted All-or-One Paging is $$\Theta (k)$$ . Offline All-or-One Paging is $$\mathbb{N}\mathbb{P}$$ -hard. Some results for the laminar case are shown via a reduction to the generalization of Paging in which each request specifies a set $$P$$ of pages, and is satisfied by fetching any page from $$P$$ into the cache. The optimal ratios for the latter problem (with laminar family of height h) are at most hk (deterministic) and $$hH_k$$ (randomized).- 17 October 2024
- Published by Springer Nature in Algorithmica
- Vol. 87 (1) , 89-131
Open AccessOnline Paging with Heterogeneous Cache Slots
It is natural to generalize the online $$k$$ -Server problem by allowing each request to specify not only a point p, but also a subset S of servers that may serve it. To date, only a few special cases of this problem have been studied. The objective of the work presented in this paper has been to more systematically explore this generalization in the case of uniform and star metrics. For uniform metrics, the problem is equivalent to a generalization of Paging in which each request specifies not only a page p, but also a subset S of cache slots, and is satisfied by having a copy of p in some slot in S. We call this problem Slot-Heterogenous Paging. In realistic settings only certain subsets of cache slots or servers would appear in requests. Therefore we parameterize the problem by specifying a family $${\mathcal {S}}\subseteq 2^{[k]}$$ of requestable slot sets, and we establish bounds on the competitive ratio as a function of the cache size k and family $${\mathcal {S}}$$ : If all request sets are allowed ( $${\mathcal {S}}=2^{[k]}\setminus \{\emptyset \}$$ ), the optimal deterministic and randomized competitive ratios are exponentially worse than for standard Paging ( $${\mathcal {S}}=\{[k]\}$$ ). As a function of $$|{\mathcal {S}}|$$ and k, the optimal deterministic ratio is polynomial: at most $$O(k^2|{\mathcal {S}}|)$$ and at least $$\Omega (\sqrt{|{\mathcal {S}}|})$$ . For any laminar family $${\mathcal {S}}$$ of height h, the optimal ratios are O(hk) (deterministic) and $$O(h^2\log k)$$ (randomized). The special case of laminar $${\mathcal {S}}$$ that we call All-or-One Paging extends standard Paging by allowing each request to specify a specific slot to put the requested page in. The optimal deterministic ratio for weighted All-or-One Paging is $$\Theta (k)$$ . Offline All-or-One Paging is $$\mathbb{N}\mathbb{P}$$ -hard. Some results for the laminar case are shown via a reduction to the generalization of Paging in which each request specifies a set $$P$$ of pages, and is satisfied by fetching any page from $$P$$ into the cache. The optimal ratios for the latter problem (with laminar family of height h) are at most hk (deterministic) and $$hH_k$$ (randomized). - Open Access
- 11 October 2024
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 20 (4) , 1-28
Competitive Data-Structure Dynamization
Data-structure dynamization is a general approach for making static data structures dynamic. It is used extensively in geometric settings and in the guise of so-called merge (or compaction) policies in big-data databases such as LevelDB and Google Bigtable. Previous theoretical work is based on worst-case analyses for uniform inputs—insertions of one item at a time and non-varying read rate. In practice, merge policies must not only handle batch insertions and varying read/write ratios, they can take advantage of such non-uniformity to reduce cost on a per-input basis. To model this, we initiate the study of data-structure dynamization through the lens of competitive analysis via two new online set-cover problems. For each, the input is a sequence of disjoint sets of weighted items. The sets are revealed one at a time. The algorithm must respond to each with a set cover that covers all items revealed so far. It obtains the cover incrementally from the previous cover by adding one or more sets and optionally removing existing sets. For each new set the algorithm incurs build cost equal to the weight of the items in the set. In the first problem the objective is to minimize total build cost plus total query cost , where the algorithm incurs a query cost at each time \(t\) equal to the current cover size. In the second problem, the objective is to minimize the build cost while keeping the query cost from exceeding \(k\) (a given parameter) at any time. We give deterministic online algorithms for both variants, with competitive ratios of \(\Theta(\log^{*}n)\) and \(k\) , respectively. The latter ratio is optimal for the second variant.- 11 October 2024
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 20 (4) , 1-28
Open AccessCompetitive Data-Structure Dynamization
Data-structure dynamization is a general approach for making static data structures dynamic. It is used extensively in geometric settings and in the guise of so-called merge (or compaction) policies in big-data databases such as LevelDB and Google Bigtable. Previous theoretical work is based on worst-case analyses for uniform inputs—insertions of one item at a time and non-varying read rate. In practice, merge policies must not only handle batch insertions and varying read/write ratios, they can take advantage of such non-uniformity to reduce cost on a per-input basis. To model this, we initiate the study of data-structure dynamization through the lens of competitive analysis via two new online set-cover problems. For each, the input is a sequence of disjoint sets of weighted items. The sets are revealed one at a time. The algorithm must respond to each with a set cover that covers all items revealed so far. It obtains the cover incrementally from the previous cover by adding one or more sets and optionally removing existing sets. For each new set the algorithm incurs build cost equal to the weight of the items in the set. In the first problem the objective is to minimize total build cost plus total query cost , where the algorithm incurs a query cost at each time \(t\) equal to the current cover size. In the second problem, the objective is to minimize the build cost while keeping the query cost from exceeding \(k\) (a given parameter) at any time. We give deterministic online algorithms for both variants, with competitive ratios of \(\Theta(\log^{*}n)\) and \(k\) , respectively. The latter ratio is optimal for the second variant. - Open Access
Scheduling Flows on a Switch to Optimize Response Times
We study the scheduling of flows on a switch with the goal of optimizing metrics related to the response time of the flows. The input to the problem is a sequence of flow requests on a switch, where the switch is represented by a bipartite graph with a capacity on each vertex (or port), and a flow request is an edge with associated demand. In each round, a subset of edges can be scheduled subject to the constraint that the total demand of the scheduled edges incident on any vertex is at most the capacity of the vertex. Previous work has essentially settled the complexity of metrics based on {\em completion time}. The objective of average or maximum {\em response time}, however, is much more challenging. We present approximation algorithms for flow scheduling over a switch to optimize response time based metrics. For the average response time metric, whose NP-hardness follows directly from past work, we present an offline $O(1 + O(\log(n))/c)$ approximation algorithm for unit flows, assuming that the port capacities of the switch can be increased by a factor of $1 + c$, for any given positive integer $c$. For the maximum response time metric, we first establish that it is NP-hard to achieve an approximation factor of better than 4/3 without augmenting capacity. We then present an offline algorithm that achieves {\em optimal maximum response time}, assuming the capacity of each port is increased by at most $2 d_{max} - 1$, where $d_{max}$ is the maximum demand of any flow. Both algorithms are based on linear programming relaxations. We also study the online version of flow scheduling using the lens of competitive analysis, and present preliminary results along with experiments that evaluate the performance of fast online heuristics.Open AccessScheduling Flows on a Switch to Optimize Response Times
We study the scheduling of flows on a switch with the goal of optimizing metrics related to the response time of the flows. The input to the problem is a sequence of flow requests on a switch, where the switch is represented by a bipartite graph with a capacity on each vertex (or port), and a flow request is an edge with associated demand. In each round, a subset of edges can be scheduled subject to the constraint that the total demand of the scheduled edges incident on any vertex is at most the capacity of the vertex. Previous work has essentially settled the complexity of metrics based on {\em completion time}. The objective of average or maximum {\em response time}, however, is much more challenging. We present approximation algorithms for flow scheduling over a switch to optimize response time based metrics. For the average response time metric, whose NP-hardness follows directly from past work, we present an offline $O(1 + O(\log(n))/c)$ approximation algorithm for unit flows, assuming that the port capacities of the switch can be increased by a factor of $1 + c$, for any given positive integer $c$. For the maximum response time metric, we first establish that it is NP-hard to achieve an approximation factor of better than 4/3 without augmenting capacity. We then present an offline algorithm that achieves {\em optimal maximum response time}, assuming the capacity of each port is increased by at most $2 d_{max} - 1$, where $d_{max}$ is the maximum demand of any flow. Both algorithms are based on linear programming relaxations. We also study the online version of flow scheduling using the lens of competitive analysis, and present preliminary results along with experiments that evaluate the performance of fast online heuristics. - Open Access
Scheduling Precedence-Constrained Jobs on Related Machines with Communication Delay
We consider the problem of scheduling $n$ precedence-constrained jobs on $m$ uniformly-related machines in the presence of an arbitrary, fixed communication delay $\rho$. We consider a model that allows job duplication, i.e. processing of the same job on multiple machines, which, as we show, can reduce the length of a schedule (i.e., its makespan) by a logarithmic factor. Our main result is an $O(\log m \log \rho / \log \log \rho)$-approximation algorithm for minimizing makespan, assuming the minimum makespan is at least $\rho$. Our algorithm is based on rounding a linear programming relaxation for the problem, which includes carefully designed constraints capturing the interaction among communication delay, precedence requirements, varying speeds, and job duplication. Our result builds on two previous lines of work, one with communication delay but identical machines (Lepere, Rapine 2002) and the other with uniformly-related machines but no communication delay (Chudak, Shmoys 1999). We next show that the integrality gap of our mathematical program is $\Omega(\sqrt{\log \rho})$. Our gap construction employs expander graphs and exploits a property of robust expansion and its generalization to paths of longer length. Finally, we quantify the advantage of duplication in scheduling with communication delay. We show that the best schedule without duplication can have makespan $\Omega(\rho/\log \rho)$ or $\Omega(\log m/\log\log m)$ or $\Omega(\log n/\log \log n)$ times that of an optimal schedule allowing duplication. Nevertheless, we present a polynomial time algorithm to transform any schedule to a schedule without duplication at the cost of a $O(\log^2 n \log m)$ factor increase in makespan. Together with our makespan approximation algorithm for schedules allowing duplication, this also yields a polylogarithmic-approximation algorithm for the setting where duplication is not allowed.Open AccessScheduling Precedence-Constrained Jobs on Related Machines with Communication Delay
We consider the problem of scheduling $n$ precedence-constrained jobs on $m$ uniformly-related machines in the presence of an arbitrary, fixed communication delay $\rho$. We consider a model that allows job duplication, i.e. processing of the same job on multiple machines, which, as we show, can reduce the length of a schedule (i.e., its makespan) by a logarithmic factor. Our main result is an $O(\log m \log \rho / \log \log \rho)$-approximation algorithm for minimizing makespan, assuming the minimum makespan is at least $\rho$. Our algorithm is based on rounding a linear programming relaxation for the problem, which includes carefully designed constraints capturing the interaction among communication delay, precedence requirements, varying speeds, and job duplication. Our result builds on two previous lines of work, one with communication delay but identical machines (Lepere, Rapine 2002) and the other with uniformly-related machines but no communication delay (Chudak, Shmoys 1999). We next show that the integrality gap of our mathematical program is $\Omega(\sqrt{\log \rho})$. Our gap construction employs expander graphs and exploits a property of robust expansion and its generalization to paths of longer length. Finally, we quantify the advantage of duplication in scheduling with communication delay. We show that the best schedule without duplication can have makespan $\Omega(\rho/\log \rho)$ or $\Omega(\log m/\log\log m)$ or $\Omega(\log n/\log \log n)$ times that of an optimal schedule allowing duplication. Nevertheless, we present a polynomial time algorithm to transform any schedule to a schedule without duplication at the cost of a $O(\log^2 n \log m)$ factor increase in makespan. Together with our makespan approximation algorithm for schedules allowing duplication, this also yields a polylogarithmic-approximation algorithm for the setting where duplication is not allowed. - 29 July 2019
- Published by Springer Nature in Theory of Computing Systems
- Vol. 64 (2) , 272-310
Cache Me if You Can: Capacitated Selfish Replication Games in Networks
- 29 July 2019
- Published by Springer Nature in Theory of Computing Systems
- Vol. 64 (2) , 272-310
Cache Me if You Can: Capacitated Selfish Replication Games in Networks
- Open Access
Retracting Graphs to Cycles
We initiate the algorithmic study of retracting a graph into a cycle in the graph, which seeks a mapping of the graph vertices to the cycle vertices, so as to minimize the maximum stretch of any edge, subject to the constraint that the restriction of the mapping to the cycle is the identity map. This problem has its roots in the rich theory of retraction of topological spaces, and has strong ties to well-studied metric embedding problems such as minimum bandwidth and 0-extension. Our first result is an O(min{k, sqrt{n}})-approximation for retracting any graph on n nodes to a cycle with k nodes. We also show a surprising connection to Sperner's Lemma that rules out the possibility of improving this result using natural convex relaxations of the problem. Nevertheless, if the problem is restricted to planar graphs, we show that we can overcome these integrality gaps using an exact combinatorial algorithm, which is the technical centerpiece of the paper. Building on our planar graph algorithm, we also obtain a constant-factor approximation algorithm for retraction of points in the Euclidean plane to a uniform cycle.
Open AccessRetracting Graphs to Cycles
We initiate the algorithmic study of retracting a graph into a cycle in the graph, which seeks a mapping of the graph vertices to the cycle vertices, so as to minimize the maximum stretch of any edge, subject to the constraint that the restriction of the mapping to the cycle is the identity map. This problem has its roots in the rich theory of retraction of topological spaces, and has strong ties to well-studied metric embedding problems such as minimum bandwidth and 0-extension. Our first result is an O(min{k, sqrt{n}})-approximation for retracting any graph on n nodes to a cycle with k nodes. We also show a surprising connection to Sperner's Lemma that rules out the possibility of improving this result using natural convex relaxations of the problem. Nevertheless, if the problem is restricted to planar graphs, we show that we can overcome these integrality gaps using an exact combinatorial algorithm, which is the technical centerpiece of the paper. Building on our planar graph algorithm, we also obtain a constant-factor approximation algorithm for retraction of points in the Euclidean plane to a uniform cycle.
- Open Access
- 31 March 2018
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Parallel Computing
- Vol. 5 (1) , 1-30
Robust and Probabilistic Failure-Aware Placement
Motivated by the growing complexity and heterogeneity of modern data centers, and the prevalence of commodity component failures, this article studies the failure-aware placement problem of placing tasks of a parallel job on machines in the data center with the goal of increasing availability. We consider two models of failures: adversarial and probabilistic. In the adversarial model, each node has a weight (higher weight implying higher reliability) and the adversary can remove any subset of nodes of total weight at most a given bound W and our goal is to find a placement that incurs the least disruption against such an adversary. In the probabilistic model, each node has a probability of failure and we need to find a placement that maximizes the probability that at least K out of N tasks survive at any time. For adversarial failures, we first show that (i) the problems are in Σ 2 , the second level of the polynomial hierarchy; (ii) a variant of the problem that we call R obust F ap (for Robust Failure-Aware Placement) is co-NP-hard; and (iii) an all-or-nothing version of R obust F ap is Σ 2 -complete. We then give a polynomial-time approximation scheme (PTAS) for R obust F ap , a key ingredient of which is a solution that we design for a fractional version of R obust F ap . We then study H ier R obust F ap , which is the fractional R obust F ap problem over a hierarchical network, in which failures can occur at any subset of nodes in the hierarchy, and a failure at a node can adversely impact all of its descendants in the hierarchy. To solve H ier R obust F ap , we introduce a notion of hierarchical max-min fairness and a novel Generalized Spreading algorithm, which is simultaneously optimal for every upper bound W on the total weight of nodes that an adversary can fail. These generalize the classical notion of max-min fairness to work with nodes of differing capacities, differing reliability weights, and hierarchical structures. Using randomized rounding, we extend this to give an algorithm for integral H ier R obust F ap . For the probabilistic version, we first give an algorithm that achieves an additive ϵ approximation in the failure probability for the single level version, called P rob F ap , while giving up a (1 + ϵ) multiplicative factor in the number of failures. We then extend the result to the hierarchical version, H ier P rob F ap , achieving an ϵ additive approximation in failure probability while giving up an (L + ϵ) multiplicative factor in the number of failures, where L is the number of levels in the hierarchy.
- 31 March 2018
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Parallel Computing
- Vol. 5 (1) , 1-30
Open AccessRobust and Probabilistic Failure-Aware Placement
Motivated by the growing complexity and heterogeneity of modern data centers, and the prevalence of commodity component failures, this article studies the failure-aware placement problem of placing tasks of a parallel job on machines in the data center with the goal of increasing availability. We consider two models of failures: adversarial and probabilistic. In the adversarial model, each node has a weight (higher weight implying higher reliability) and the adversary can remove any subset of nodes of total weight at most a given bound W and our goal is to find a placement that incurs the least disruption against such an adversary. In the probabilistic model, each node has a probability of failure and we need to find a placement that maximizes the probability that at least K out of N tasks survive at any time. For adversarial failures, we first show that (i) the problems are in Σ 2 , the second level of the polynomial hierarchy; (ii) a variant of the problem that we call R obust F ap (for Robust Failure-Aware Placement) is co-NP-hard; and (iii) an all-or-nothing version of R obust F ap is Σ 2 -complete. We then give a polynomial-time approximation scheme (PTAS) for R obust F ap , a key ingredient of which is a solution that we design for a fractional version of R obust F ap . We then study H ier R obust F ap , which is the fractional R obust F ap problem over a hierarchical network, in which failures can occur at any subset of nodes in the hierarchy, and a failure at a node can adversely impact all of its descendants in the hierarchy. To solve H ier R obust F ap , we introduce a notion of hierarchical max-min fairness and a novel Generalized Spreading algorithm, which is simultaneously optimal for every upper bound W on the total weight of nodes that an adversary can fail. These generalize the classical notion of max-min fairness to work with nodes of differing capacities, differing reliability weights, and hierarchical structures. Using randomized rounding, we extend this to give an algorithm for integral H ier R obust F ap . For the probabilistic version, we first give an algorithm that achieves an additive ϵ approximation in the failure probability for the single level version, called P rob F ap , while giving up a (1 + ϵ) multiplicative factor in the number of failures. We then extend the result to the hierarchical version, H ier P rob F ap , achieving an ϵ additive approximation in failure probability while giving up an (L + ϵ) multiplicative factor in the number of failures, where L is the number of levels in the hierarchy.
- 4 September 2016
- Published by Springer Nature
- p. 399-413
Information Spreading in Dynamic Networks Under Oblivious Adversaries
- 4 September 2016
- Published by Springer Nature
- p. 399-413
Information Spreading in Dynamic Networks Under Oblivious Adversaries
- Open Access
Information Spreading in Dynamic Networks under Oblivious Adversaries
We study the problem of gossip in dynamic networks controlled by an adversary that can modify the network arbitrarily from one round to another, provided that the network is always connected. In the gossip problem, $n$ tokens are arbitrarily distributed among the $n$ network nodes, and the goal is to disseminate all the $n$ tokens to every node. Our focus is on token-forwarding algorithms, which do not manipulate tokens in any way other than storing, copying, and forwarding them. Gossip can be completed in linear time in any static network, but a basic open question for dynamic networks is the existence of a distributed protocol that can do significantly better than an easily achievable bound of $O(n^2)$ rounds. In previous work, it has been shown that under adaptive adversaries, every token forwarding algorithm requires $\Omega(n^2/\log n)$ rounds. In this paper, we study oblivious adversaries, which differ from adaptive adversaries in one crucial aspect--- they are oblivious to random choices made by the protocol. We present an $\tilde{\Omega}(n^{3/2})$ lower bound under an oblivious adversary for RANDDIFF, a natural algorithm in which neighbors exchange a token chosen uniformly at random from the difference of their token sets. We also present an $\tilde{\Omega}(n^{4/3})$ bound under a stronger notion of oblivious adversary for symmetric knowledge-based algorithms. On the positive side, we present a centralized algorithm that completes gossip in $\tilde{O}(n^{3/2})$ rounds. We also show an $\tilde{O}(n^{5/3})$ upper bound for RANDDIFF in a restricted class of oblivious adversaries, which we call paths-respecting.Open AccessInformation Spreading in Dynamic Networks under Oblivious Adversaries
We study the problem of gossip in dynamic networks controlled by an adversary that can modify the network arbitrarily from one round to another, provided that the network is always connected. In the gossip problem, $n$ tokens are arbitrarily distributed among the $n$ network nodes, and the goal is to disseminate all the $n$ tokens to every node. Our focus is on token-forwarding algorithms, which do not manipulate tokens in any way other than storing, copying, and forwarding them. Gossip can be completed in linear time in any static network, but a basic open question for dynamic networks is the existence of a distributed protocol that can do significantly better than an easily achievable bound of $O(n^2)$ rounds. In previous work, it has been shown that under adaptive adversaries, every token forwarding algorithm requires $\Omega(n^2/\log n)$ rounds. In this paper, we study oblivious adversaries, which differ from adaptive adversaries in one crucial aspect--- they are oblivious to random choices made by the protocol. We present an $\tilde{\Omega}(n^{3/2})$ lower bound under an oblivious adversary for RANDDIFF, a natural algorithm in which neighbors exchange a token chosen uniformly at random from the difference of their token sets. We also present an $\tilde{\Omega}(n^{4/3})$ bound under a stronger notion of oblivious adversary for symmetric knowledge-based algorithms. On the positive side, we present a centralized algorithm that completes gossip in $\tilde{O}(n^{3/2})$ rounds. We also show an $\tilde{O}(n^{5/3})$ upper bound for RANDDIFF in a restricted class of oblivious adversaries, which we call paths-respecting.