Approximation Algorithms for Key Management in Secure Multicast (2009)
Chan, Agnes, Rajaraman, Rajmohan, Sun, Zhifeng, Zhu, Feng
Many data dissemination and publish-subscribe systems that guarantee the privacy and authenticity of the participants rely on symmetric key cryptography. An important problem in such a system is to...
Reducibility Among Fractional Stability Problems (2009)
Kintali, Shiva, Poplawski, Laura J., Rajaraman, Rajmohan, Sundaram, Ravi, Teng, Shang-Hua
In this paper, we resolve the computational complexity of a number of outstanding open problems with practical applications. Here is the list of problems we show to be PPAD-complete, along with the...
ABSTRACT Compact Routing With Name Independence (2009)
Marta Arias, Rajmohan Rajaraman, Lenore J. Cowen, Orjeta Taka, Kofi A. Laing
This paper is concerned with compact routing in the name independent model first introduced by Awerbuch et al. [1] for adaptive routing in dynamic networks. A compact routing scheme that uses local...
(Almost) Tight Bounds and Existence Theorems for Single-Commodity Confluent Flows (2008)
Jiangzhuo Chen, Robert D. Kleinberg, László Lovász, Rajmohan Rajaraman, Ravi Sundaram, Adrian Vetta
A flow of a commodity is said to be confluent if at any node all the flow of the commodity leaves along a single edge. In this paper we study single-commodity confluent flow problems, where we need...
Preference Games and Personalized Equilibria, with Applications to Fractional BGP (2008)
Poplawski, Laura J., Rajaraman, Rajmohan, Sundaram, Ravi, Teng, Shang-Hua
We study the complexity of computing equilibria in two classes of network games based on flows - fractional BGP (Border Gateway Protocol) games and fractional BBC (Bounded Budget Connection) games....
Lujun Jia, Rajmohan Rajaraman, Torsten Suel
Abstract The dominating set problem asks for a small subset D of nodes in a graph such that every node is either in D or adjacent to a node in D. This problem arises in a number of distributed...
Laoutaris, Nikolaos, Poplawski, Laura J., Rajaraman, Rajmohan, Sundaram, Ravi, Teng, Shang-Hua
Motivated by applications in social networks, peer-to-peer and overlay networks, we define and study the Bounded Budget Connection (BBC) game - we have a collection of n players or nodes each of whom...
ABSTRACT Compact Routing With Name Independence (2008)
Marta Arias, Rajmohan Rajaraman, Lenore J. Cowen, Orjeta Taka, Kofi A. Laing
This paper is concerned with compact routing in the name independent model first introduced by Awerbuch et al. [1] for adaptive routing in dynamic networks. A compact routing scheme that uses local...
Johannes Gehrke, Rajmohan Rajaraman
In this project, we adopted a database approach to unite the seemingly conflicting requirements of scalability and flexibility in monitoring the physical world. The objective of this research was to...
DISS. ETH NO. 16800 Understanding Ad hoc Networks From Geometry to Mobility (2008)
Dipl Inf. -ing, Eth Zürich, Prof Dr, Roger Wattenhofer, Prof Dr, Rajmohan Rajaraman, ...
born 26.04.1980
C. Greg Plaxton, Rajmohan Rajaraman, Andr'ea W. Richa
Consider a set of shared objects in a distributed network, where several copies of each object may exist at any given time. To ensure both fast access to the objects as well as efficient utilization...
S. Muthukrishnan, Rajmohan Rajaraman, Anthony Shaheen, Johannes E. Gehrke
We consider the classical problem of online job scheduling on uniprocessor and multiprocessor machines. For a given job, we measure the quality of service provided by an algorithm by the stretch of...
Madhukar R. Korupolu, C. Greg Plaxton, Rajmohan Rajaraman
Consider a hierarchical network in which each node periodically issues a request for an object drawn from a fixed set of unit-size objects. Suppose further that the following conditions are...
Madhukar R. Korupolu, C. Greg Plaxton, Rajmohan Rajaraman
Consider a hierarchical network in which each node periodically issues a request for an object drawn from a xed set of unit-size objects. Suppose further that the following conditions are satised:...
Rajmohan Rajaraman, Andrea W. Richa
Consider an arbitrary distributed network in which large numbers of objects are continuously being created, replicated, and destroyed. A basic problem arising in such an environment is that of...
Madhukar R. Korupolu, C. Greg Plaxton, Rajmohan Rajaraman
Consider a hierarchical network in which each node periodically issues a request for an object drawn from a fixed set of unit-size objects. Suppose further that the following conditions are...
Lujun Jia, Rajmohan Rajaraman, Torsten Suel
The dominating set problem asks for a small subset D of nodes in a graph such that every node is either in D or adjacent to a node in D. This problem arises in a number of distributed network...
Micah Adler, Sanjeev Khanna, Rajmohan Rajaraman
The time-constrained packet routing problem is to schedule a set of packets to be routed through a multi-node network, where every packet has a source and a destination (as in traditional packet...
Approximation Algorithms for Multiprocessor Scheduling under Uncertainty (2007)
Lin, Guolong, Rajaraman, Rajmohan
Motivated by applications in grid computing and project management, we study multiprocessor scheduling in scenarios where there is uncertainty in the successful execution of jobs when assigned to...
A bounded-degree network formation game (2007)
Laoutaris, Nikolaos, Rajaraman, Rajmohan, Sundaram, Ravi, Teng, Shang-Hua
Motivated by applications in peer-to-peer and overlay networks we define and study the \emph{Bounded Degree Network Formation} (BDNF) game. In an $(n,k)$-BDNF game, we are given $n$ nodes, a bound...
Gist: Group-independent spanning tree for data aggregation in dense sensor networks (2006)
Lujun Jia, Guevara Noubir, Rajmohan Rajaraman, Ravi Sundaram
Abstract. Today, there exist many algorithms and protocols for constructing agregation or dissemination trees for wireless sensor networks that are optimal (for different notions of optimal, i.e....
A Space Lower Bound for Name-Independent Compact Routing in Trees ∗ (2006)
Kofi A. Laing, Rajmohan Rajaraman
Given a rooted n-node tree with arbitrary positive edge weights, and arbitrarily assigned node names, what is the minimum amount of space that a single-source compact routing algorithm could use in...
The confluent capacity of the internet: congestion vs. dilation (2006)
Jiangzhuo Chen, Madhav Marathe, Rajmohan Rajaraman, Ravi Sundaram
Using shortest paths, the Internet scales very poorly with respect to congestion [2]. Two main reasons for using shortest paths are dilation (or delay) and size of routing tables. As the Internet...
Universal approximations for TSP, Steiner tree, and set cover (2005)
Lujun Jia, Guolong Lin, Guevara Noubir, Rajmohan Rajaraman, Ravi Sundaram
We introduce a notion of universality in the context of optimization problems with partial information. Universality is a framework for dealing with uncertainty by guaranteeing a certain quality of...
Universal approximations for TSP, Steiner tree, and set cover (2005)
Lujun Jia, Guolong Lin, Guevara Noubir, Rajmohan Rajaraman, Ravi Sundaram
ABSTRACT We introduce a notion of universality in the context of optimizationproblems with partial information. Universality is a framework for dealing with uncertainty by guaranteeing a certain...
Hybrid Push-Pull Query Processing for Sensor Networks (2004)
Niki Trigoni, Yong Yao, Alan Demers, Johannes Gehrke, Rajmohan Rajaraman
Abstract: A powerful database abstraction for sensor networks has recently emerged in which clients program the sensors using a declarative query language. Existing work assumes that data is either...
Wavescheduling: energy-efficient data dissemination for sensor networks (2004)
Niki Trigoni, Yong Yao, Alan Demers, Johannes Gehrke, Rajmohan Rajaraman
Abstract Sensor networks are being increasingly deployed for diverse monitoring applications. Event data are collected at various sensors and sent to selected storage nodes for further in-network...
Mobility Models for Ad hoc Network Simulation (2004)
Guolong Lin, Guevara Noubir, Rajmohan Rajaraman
In this paper, we propose a novel general technique, based on renewal theory, for analyzing mobility models in ad hoc networks. Our technique enables an accurate derivation of the steady state...
Hybrid Push-Pull Query Processing for Sensor Networks (2004)
Niki Trigoni, Yong Yao, Alan Demers, Johannes Gehrke, Rajmohan Rajaraman
Abstract: A powerful database abstraction for sensor networks has recently emerged in which clients program the sensors using a declarative query language. Existing work assumes that data is either...
Almost) tight bounds and existence theorems for confluent flows (2004)
Jiangzhuo Chen, Robert D. Kleinberg, László Lovász, Rajmohan Rajaraman, Ravi Sundaram, Adrian Vetta
A flow is said to be confluent if at any node all the flow leaves along a single edge. Given a directed graph G with k sinks and non-negative demands on all the nodes of G, we consider the problem of...
Guruswami, Venkatesan, Khanna, Sanjeev, Rajaraman, Rajmohan, Shepherd, F. Bruce, Yannakakis, Mihalis
We study the approximability of edge-disjoint paths and related problems. In the edge-disjoint paths problem (EDP), we are given a network G with source-sink pairs (si,ti), 1 ≤ i ≤ k, and the...
Time-Constrained Scheduling of Weighted Packets On Trees and Meshes (2003)
Adler, Micah, Khanna, Sanjeev, Rajaraman, Rajmohan, Rosén, Adi
The time-constrained packet routing problem is to schedule a set of packets to be transmitted through a multi-node network, where every packet has a source and a destination (as in traditional packet...
The Cougar project: A work-in-progress report (2003)
Alan Demers, Johannes Gehrke, Rajmohan Rajaraman, Niki Trigoni, Yong Yao
Abstract — We present an update on the status of the Cougar Sensor Database Project in which we are investigating a database approach to sensor networks: Clients “program ” the sensors through...
Compact routing with name independence (2003)
Marta Arias, Lenore J. Cowen, Kofi A. Laing, Rajmohan Rajaraman, Orjeta Taka
This paper is concerned with compact routing schemes for arbitrary undirected networks in the name-independent model first introduced by Awerbuch, Bar-Noy, Linial and Peleg. A compact routing scheme...
The Cougar project: A work-in-progress report (2003)
Alan Demers, Johannes Gehrke, Rajmohan Rajaraman, Niki Trigoni, Yong Yao
Meet and Merge: Approximation Algorithms for Confluent Flows (2003)
Jiangzhuo Chen, Rajmohan Rajaraman, Ravi Sundaram
In this paper we investigate the problem of determining confluent flows with minimum congestion. A flow of a given commodity is said to be confluent if at any node all the flow of the commodity...
On Local Algorithms for Topology Control and Routing in Ad Hoc Networks (2003)
Lujun Jia, Rajmohan Rajaraman, Christian Scheideler
An ad hoc network is a collection of wireless mobile hosts forming a temporary network without the aid of any fixed infrastructure. Indeed, an important task of an ad hoc network is to determine an...
Approximation Algorithms for Average Stretch Scheduling (2003)
Michael A. Bender, S. Muthukrishnan, Rajmohan Rajaraman
We study the basic problem of preemptive scheduling of a stream of jobs on a single processor.
Energy-Efficient Data Management For Sensor (2003)
Alan Demers, Johannes Gehrke, Rajmohan Rajaraman, Niki Trigoni, Yong Yao
We give a status update of the Cougar Project, in which we investigate a database approach to sensor networks: Clients "program" the sensors through queries in a high-level declarative...
Topology Control and Routing in Ad hoc Networks: A Survey (2002)
this article, we review some of the characteristic features of ad hoc networks, formulate problems and survey research work done in the area. We focus on two basic problem domains: topology control,...
Improved Algorithms for Stretch Scheduling (2002)
Michael A. Bender, S. Muthukrishnan, Rajmohan Rajaraman
We study the basic problem of preemptive scheduling of an online stream of jobs on a single processor. The ith job arrives at time r(i) and has processing time p(i) that is known at the time of its...
Approximation Algorithms for Data Placement in Arbitrary Networks (2001)
Ivan Baev, Rajmohan Rajaraman, Chaitanya Swamy
Abstract We develop approximation algorithms for the problem of placing replicated data in arbitrary net-works, where the nodes may both issue requests for data objects and have capacity for storing...
Towards more complete models of TCP latency and throughput (2001)
Michael Mitzenmacher, Rajmohan Rajaraman
Recently, several researchers have developed equations for modeling TCP behaviors, such as the expected throughput or latency, based on Markov chains derived from TCP with additional simplifying...
Approximation Algorithms for Data Placement in Arbitrary Networks (2001)
Ivan Baev, Rajmohan Rajaraman, Chaitanya Swamy
We develop approximation algorithms for the problem of placing replicated data in arbitrary networks, where the nodes may both issue requests for data objects and have capacity for storing data...
Towards more complete models of tcp latency and throughput (2001)
Michael Mitzenmacher, Rajmohan Rajaraman
Abstract. Recently, several researchers have developed equations for modeling TCP behaviors, such as the expected throughput or latency, based on Markov chains derived from TCP with additional...
A Data Tracking Scheme for General Networks (2001)
Rajmohan Rajaraman Andr'ea, Rajmohan Rajaraman, Andr'ea W. Richa, Berthold Vocking
Consider an arbitrary distributed network in which large numbers of objects are continuously being created, replicated, and destroyed. A basic problem arising in such an environment is that of...
Placement Algorithms for (2001)
Hierarchical Cooperative Caching, Madhukar R. Korupolu, C. Greg Plaxton, Rajmohan Rajaraman
Consider a hierarchical network in which each node periodically issues a request for an object drawn from a xed set of unit-size objects. Suppose further that the following conditions are satis ed:...
Analysis of a Local Search Heuristic for Facility Location Problems (2000)
Madhukar R. Korupolu, C. Greg Plaxton, Rajmohan Rajaraman
In this paper, we study approximation algorithms for several NP-hard facility location problems.
Time-constrained scheduling of weighted packets on trees and meshes (1999)
Micah Adler, Sanjeev Khanna, Rajmohan Rajaraman, Adi Rosén
Abstract. The time-constrained packet routing problem is to schedule a set of packets to be transmitted through a multinode network, where every packet has a source and a destination (as in...
Venkatesan Guruswami, Sanjeev Khanna, Rajmohan Rajaraman, Bruce Shepherd, Mihalis Yannakakis
We study the approximability of edge-disjoint paths and related problems. In the edge-disjoint paths problem (EDP), we are given a network G with source-sink pairs (si, ti), 1 ≤ i ≤ k, and the...
Chandrashekhar Nagarajan, P. Williamson, Guolong Lin, Rajmohan Rajaraman
A current trend in business and logistics is that of a non-asset owning company where the company efficiently combines and subcontracts work to leased assets rather than owning them. Along these...
Venkatesan Guruswami, Sanjeev Khanna, Rajmohan Rajaraman, Bruce Shepherd, Mihalis Yannakakis
We study the approximability of edge-disjoint paths and related problems. In the edge-disjoint paths problem (EDP), we are given a network G with source-sink pairs (s i; t i), 1 i k, and the goal is...
A Dynamic Object Replication and Migration Protocol for an Internet Hosting Service (1999)
Michael Rabinovich, Irina Rabinovich, Rajmohan Rajaraman, Amit Aggarwal
This paper proposes a protocol suite for dynamic replication and migration of Internet objects. It consists of an algorithm for deciding on the number and location of object replicas and an algorithm...
Placement Algorithms for Hierarchical Cooperative Caching (1999)
Madhukar R. Korupolu, C. Greg Plaxton, Rajmohan Rajaraman
Consider a hierarchical network of machines in which each machine periodically issues a request for an object drawn from a fixed set of unit-size objects. Suppose further that the following...
Venkatesan Guruswami, Sanjeev Khanna, Rajmohan Rajaraman, Bruce Shepherd, Mihalis Yannakakis
We study the approximability of edge-disjoint paths and related problems. In the edge-disjoint paths problem (EDP), we are given a network G with source-sink pairs (s i; t i), 1 i k, the goal is to...
Time-Constrained Scheduling of Weighted Packets on Trees and Meshes (1999)
Micah Adler Sanjeev, Sanjeev Khanna, Rajmohan Rajaraman
The time-constrained packet routing problem is to schedule a set of packets to be routed through a multi-node network, where every packet has a source and a destination (as in traditional packet...
Time-Constrained Scheduling of Weighted Packets on Trees and Meshes (1999)
Micah Adler, Sanjeev Khanna, Rajmohan Rajaraman, Adi Rosen
The time-constrained packet routing problem is to schedule a set of packets to be routed through a multi-node network, where every packet has a source and a destination (as in traditional packet...
Scheduling to Minimize Average Stretch (1999)
Johannes E. Gehrke, S. Muthukrishnan, Rajmohan Rajaraman, Anthony Shaheen
We consider the classical problem of online preemptive job scheduling on uniprocessor and multiprocessor machines. For a given job, we measure the quality of service provided by an algorithm by the...
Venkatesan Guruswami, Sanjeev Khanna, Rajmohan Rajaraman, Bruce Shepherd, Mihalis Yannakakis
We study the approximability of two classes of network routing problems. The first class of problems in our study correspond to classical multicommodity flow problems of the following form: We are...
Placement Algorithms for Hierarchical Cooperative Caching (1999)
Madhukar R. Korupolu, C. Greg Plaxton, Rajmohan Rajaraman
z
Analysis of a local search heuristic for facility location problems (1998)
Madhukar R. Korupolu, C. Greg Plaxton, Rajmohan Rajaraman
In this paper, we study approximation algorithms for several NP-hard facility location problems. We prove that a simple local search heuristic yields polynomialtime constant-factor approximation...
Analysis of a local search heuristic for facility location problems (1998)
Madhukar R. Korupolu, C. Greg Plaxton, Rajmohan Rajaraman
In this paper, we study approximation algorithms for several NP-hard facility location problems. We prove that a simple local search heuristic yields polynomialtime constant-factor approximation...
Analysis of a Local Search Heuristic for Facility Location Problems (1998)
Madhukar R. Korupolu, C. Greg Plaxton, Rajmohan Rajaraman
In this paper, we study approximation algorithms for several NP-hard facility location problems. We prove that a simple local search heuristic yields polynomial-time constant-factor approximation...
Dynamic Replication on the Internet Work Project No. 3116-17-7006 (1998)
Michael Rabinovich, From Michael Rabinovich, Irina Rabinovich, The Dun, Rajmohan Rajaraman
This paper proposes a protocol suite for dynamic replication and migration of Internet objects. It consists of an algorithm for deciding on the number and location of object replicas and an algorithm...
An Adversarial Model for Distributed Dynamic Load Balancing (1998)
S. Muthukrishnan, Rajmohan Rajaraman
We study the problem of balancing the load on processors of an arbitrary network. If jobs arrive or depart during the process of load balancing, we have the dynamic load balancing problem; otherwise,...
Analysis of a Local Search Heuristic for Facility Location Problems (1998)
By Madhukar Korupolu, C. Greg Plaxton, Rajmohan Rajaraman
In this paper, we study approximation algorithms for several NP-hard facility location problems. We prove that a simple local search heuristic yields polynomial-time constant-factor approximation...
A Dynamic Object Replication and Migration Protocol for an Internet Hosting Service (1998)
Michael Rabinovich, Irina Rabinovich, Rajmohan Rajaraman, Amit Aggarwal
This paper proposes a protocol suite for dynamic replication and migration of Internet objects. It consists of an algorithm for deciding on the number and location of object replicas and an algorithm...
A Dynamic Object Replication and Migration Protocol for an Internet Hosting Service (1998)
Michael Rabinovich, Irina Rabinovich, Rajmohan Rajaraman, Amit Aggarwal
This paper proposes a protocol suite for dynamic replication and migration of Internet objects. It consists of an algorithm for deciding on the number and location of object replicas and an algorithm...
Accessing nearby copies of replicated objects in a distributed environment (1997)
C. Greg Plaxton, Rajmohan Rajaraman, Andr'ea W. Richa
Consider a set of shared objects in a distributed network, where several copies of each object may exist at any given time. To ensure both fast access to the objects as well as efficient utilization...
Sharing Resources in Distributed Systems (1997)
Rajmohan Rajaraman, B. Tech, Dissertation Committee
vii Chapter 1 Introduction 1 1.1 Sharing Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1.1 Model of Computation . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1.2...
Accessing Nearby Copies of Replicated Objects in a Distributed Environment (1997)
C. Greg Plaxton, Rajmohan Rajaraman, Andrea W. Richa, Andr'ea W. Richa
Consider a set of shared objects in a distributed network, where several copies of each object may exist at any given time. To ensure both fast access to the objects as well as efficient utilization...
Rapid Convergence of a Local Load Balancing Algorithm for Asynchronous Rings (1997)
Johannes E. Gehrke, C. Greg Plaxton, Rajmohan Rajaraman
. We consider the problem of load balancing in a ring network. We present an analysis of the following local algorithm. In each step, each node of the ring examines the number of tokens at its...
Accessing Nearby Copies of Replicated Objects in a Distributed Environment (1997)
C. Greg Plaxton, Rajmohan Rajaraman, Andrea W. Richa, Andr'ea W. Richa
Consider a set of shared objects in a distributed network, where several copies of each object may exist at any given time. To ensure both fast access to the objects as well as efficient utilization...
Fast Fault-Tolerant Concurrent Access to Shared Objects (1996)
C. Greg Plaxton, C. Greg, Rajmohan Rajaraman
We consider a synchronous model of distributed computation in which n nodes communicate via point-to-point messages, subject to the following constraints: (i) in a single "step", a node can...