Distributed Ranked Search (2009)
Vijay Gopalakrishnan, Ruggero Morselli, Bobby Bhattacharjee, Pete Keleher, Aravind Srinivasan
Abstract. P2P deployments are a natural infrastructure for building distributed search networks. Proposed systems support locating and retrieving all results, but lack the information necessary to...
On k-Column Sparse Packing Programs (2009)
Bansal, Nikhil, Korula, Nitish, Nagarajan, Viswanath, Srinivasan, Aravind
We consider the class of packing integer programs (PIPs) that are column sparse, i.e. there is a specified upper bound k on the number of constraints that each variable appears in. We give an...
É.: Cost-sharing mechanisms for network design (2009)
Anupam Gupta, Aravind Srinivasan, Éva Tardos
We consider a single-source network design problem from a game-theoretic perspective. Gupta, Kumar and Roughgarden (Proc. 35th Annual ACM STOC, pages 365–372, 2003) developed a simple method for a...
Fast Distributed Algorithms for (Weakly) Connected Dominating Sets and Linear-Size Skeletons (2009)
Devdatt Dubhashi\lambda Aless, Ro Meiy Aless, Ro Panconesiz, Jaikumar Radhakrishnanx, Aravind Srinivasan
Key words and phrases. Ad hoc networks, dominating sets, distributed algorithms.
Scheduling on Unrelated Machines under Tree-Like Precedence Constraints* (2009)
V. S. Anil, Kumar Madhav, V. Marathe, Srinivasan Parthasarathy, Aravind Srinivasan
Devdatt Dubhashi Aless, Ro Meit Aless, Ro Panconesi, Jaikumar Radhakrishnan, Aravind Srinivasan
Motivated by routing issues in ad hoc networks, we present polylogarithmic-time distributed algorithms for two problems. Given a network, we first show how to compute connected and weakly connected...
Storage and Retrieval]: Systems and Software—Distributed (2009)
Ruggero Morselli, Bobby Bhattacharjee, Aravind Srinivasan
We present LMS, a protocol for efficient lookup on unstructured networks. Our protocol uses a virtual namespace without imposing specific topologies. It is more efficient than existing lookup...
Abstract P 5: A Protocol for Scalable Anonymous Communication ∗ (2008)
Rob Sherwood, Bobby Bhattacharjee, Aravind Srinivasan
We present a protocol for anonymous communication over the Internet. Our protocol, called P 5 (Peerto-Peer Personal Privacy Protocol) provides sender-, receiver-, and sender-receiver anonymity. P 5...
Capacity of Asynchronous Random-Access Scheduling in Wireless Networks (2008)
Deepti Chafekar, Dave Levin, Madhav V. Marathe, Srinivasan Parthasarathy, Aravind Srinivasan
Abstract—We study the throughput capacity of wireless networks which employ (asynchronous) random-access scheduling as opposed to deterministic scheduling. The central question we answer is: how...
Ranking Search Results in P2P Systems (2008)
Vijay Gopalakrishnan, Ruggero Morselli, Bobby Bhattacharjee, Peter Keleher, Aravind Srinivasan
P2P deployments are a natural infrastructure for building distributed search networks. Proposed systems support locating and retrieving all results, but lack the information necessary to rank them....
Anupam Gupta, Aravind Srinivasan, 'eva Tardos
Abstract. We consider a single source network design problem from a game-theoretic perspective. Gupta, Kumar and Roughgarden (Proc. 35th Annual ACM STOC, pages 365-372, 2003) developed a simple...
Scheduling on Unrelated Machines under Tree-Like Precedence Constraints ∗ (2008)
V. S. Anil, Kumar Madhav, V. Marathe, Srinivasan Parthasarathy, Aravind Srinivasan
We present polylogarithmic approximations for the R|prec|Cmax and R|prec | � j wjCj problems, when the precedence constraints are “treelike ”- i.e., when the undirected graph underlying the...
Approximation Algorithms for Computing Capacity of Wireless Networks with SINR constraints (2008)
Deepti Chafekar, Madhav V. Marathe, Srinivasan Parthasarathy, Aravind Srinivasan
Abstract—A fundamental problem in wireless networks is to estimate its throughput capacity- given a set of wireless nodes, and a set of connections, what is the maximum rate at which data can be...
Andris Ambainis, William Gasarch, Andrey Utis, Aravind Srinivasan
Alice and Bob want to know if two strings of length n are almost equal. That is, do they differ on at most a bits? Let 0 ≤ a ≤ n − 1. We show that any deterministic protocol, as well as any...
An Improved Approximation Algorithm For Vertex Cover with Hard Capacities (Extended Abstract) (2008)
Rajiv G, Eran Halperin, Samir Khuller, Guy Kortsarz, Aravind Srinivasan
Abstract. In this paper we study the capacitated vertex cover problem, a generalization of the well-known vertex cover problem. Given a graph G = (V, E), the goal is to cover all the edges by picking...
Chris Barrett, Doug Cook, Gregory Hicks, Vance Faber, Achla Marathe, Madhav Marathe, ...
work was done while at the National University of Singapore. Email:
COMPLEXITY—Tradeoffs between Complexity Measures General Terms (2008)
Virginia Bio-informatics, Srinivasan Parthasarathy, Madhav V. Marathe, Virginia Bio-informatics, Aravind Srinivasan
Given a wireless network and a collection of source-destination pairs {(si, ti)}, what is the maximum end-to-end rate (throughput) at which the network can transfer data from the sources to their...
Provable Algorithms for Parallel Sweep Scheduling on Unstructured (2008)
V. S. Anil, Kumar Madhav, V. Marathe, Srinivasan Parthasarathy, Aravind Srinivasan, Sibylle Zust
We present provably efficient parallel algorithms for sweep scheduling on unstructured meshes. Sweep scheduling is a commonly used technique in Radiation Transport problems, and involves inverting an...
Algorithmic Aspects of Capacity in Wireless Networks (2008)
V. S. Anil, Kumar Madhav, V. Marathe, Srinivasan Parthasarathy, Aravind Srinivasan
This paper considers two inter-related questions: (i) Given a wireless ad-hoc network and a collection of source-destination pairs {(si,ti)}, what is the maximum throughput capacity of the network,...
Approximating the Domatic Number Uriel Feige \Lambda Magn'us M. Halld'orsson y (2008)
Guy Kortsarz, Aravind Srinivasan
Abstract A set of vertices in a graph is a dominating set if every vertex outside the set has a neighbor in the set. The domatic number problem is that of partitioning the vertices of a graph into...
Ranking Search Results in P2P Systems (2008)
Vijay Gopalakrishnan, Ruggero Morselli, Bobby Bhattacharjee, Peter Keleher, Aravind Srinivasan
P2P deployments are a natural infrastructure for building distributed search networks. Proposed systems support locating and retrieving all results, but lack the information necessary to rank them....
Scheduling on Unrelated Machines under Tree-Like Precedence Constraints (2008)
V. S. Anil, Kumar Madhav, V. Marathe, Srinivasan Parthasarathy, Aravind Srinivasan
We present polylogarithmic approximations for the R|prec|Cmax and R|prec | � j wjCj problems, when the precedence constraints are “treelike ”- i.e., when the undirected graph underlying the...
Infrastructure and Analysis (2008)
Madhav V. Marathe, Virginia Bioinformatics, Aravind Srinivasan
This paper considers two inter-related questions: (i) Given a wireless ad-hoc network and a collection of source-destination pairs {(si,ti)}, what is the maximum throughput capacity of the network,...
1 c○0000 (copyright holder) (2008)
Stephen Eubank, Madhav V. Marathe, Aravind Srinivasan, Nan Wang, S. Eubank, ...
Abstract. Traditional epidemiological research has focused on ratebased differential-equation models on completely mixing populations. In this paper, we outline an approach based on a combination of...
Randomized Algorithms and Probabilistic Analysis in Wireless Networking ⋆ (2008)
Abstract. Devices connected wirelessly, in various forms including computers, hand-held devices, ad hoc networks, and embedded systems, are expected to become ubiquitous all around us. Wireless...
Storage and Retrieval]: Systems and Software—Distributed (2008)
Ruggero Morselli, Bobby Bhattacharjee, Aravind Srinivasan
We present LMS, a protocol for efficient lookup on unstructured networks. Our protocol uses a virtual namespace without imposing specific topologies. It is more efficient than existing lookup...
Yi Li, Aravind Srinivasan, Philip M. Long
We present a new general upper bound on the number of examples required to estimate all of the expectations of a set of random variables uniformly well. The quality of the estimates is measured using...
Andris Ambainis, William Gasarch, Aravind Srinivasan, Andrey Utis
Abstract. Alice and Bob want to know if two strings of length n are almost equal. That is, do they differ on at most a bits? Let 0 ≤ a ≤ n − 1. We show that any deterministic protocol, as well...
Approximation Algorithms for Channel Allocation Problems in Broadcast Networks (2008)
Rajiv G, Samir Khuller, Aravind Srinivasan, Nan Wang
Abstract. We study two packing problems that arise in the area of dissemination-based information systems; a second theme is the study of distributed approximation algorithms. The problems considered...
1 Our result. Domatic Partitions and the Lovász Local Lemma (2008)
We resolve the problem posed as the main open question in [4]: letting δ(G), ∆(G) and D(G) respectively denote the minimum degree, maximum degree, and domatic number (defined below) of an...
End-to-End Packet-Scheduling in Wireless Ad-hoc Networks (2008)
V. S. Anil, Kumar Madhav, V. Marathe, Srinivasan Parthasarathy, Aravind Srinivasan
Abstract Packet-scheduling is a particular challenge in wireless networks due to interference from nearby transmissions. A distance-2 interference model serves as a useful abstraction here, and we...
Suresh Chari, Pankaj Rohatgi, Aravind Srinivasan
We present two techniques for constructing sample spaces that approximate probability distributions. The first is a simple method for constructing the small-bias probability spaces introduced by Naor...
An Improved Approximation Algorithm For Vertex Cover with Hard Capacities (Extended Abstract) (2008)
Rajiv G, Eran Halperin, Samir Khuller, Guy Kortsarz, Aravind Srinivasan
ABSTRACT Resilient Multicast using Overlays (2008)
Suman Banerjee, Seungjoon Lee, Bobby Bhattacharjee, Aravind Srinivasan
Michael Saks, Aravind Srinivasan, Shiyu Zhou, David Zuckerman
Motivated by a problem of filtering near-duplicate Web documents, Broder, Charikar, Frieze & Mitzenmacher defined the following notion of #-approximate min-wise independent permutation families....
Magnus M. Halldorsson y (2007)
Uriel Feige, Guy Kortsarz, Aravind Srinivasan
The domatic number problem is that of partitioning the vertices of an undirected graph into the maximum number of disjoint dominating sets. Let n denote the number of vertices in a graph, the minimum...
Low-Bandwidth Routing and Electrical Power Networks (2007)
Doug Cook, Vance Faber, Madhav Marathe, Aravind Srinivasan, Yoram J. Sussmann
. Given a graph G and a (multi-)set of pairs of vertices in it, the classical NP-hard maximum edge-disjoint-paths problem (MDP) is to connect as many of the given pairs as possible using pairwise...
epsilon-Optimal Solutions to Nonlinear 0-1 Integer Programs Using the Subgradient Algorithm (2007)
Aravind Srinivasan, Suresh Chari, Pankaj Rohatgi, Zhijun Wu, Zhijun Wu, Theodore Johnson
S PARALLEL PROCESSING OF DISCRETE OPTIMIZATION PROBLEMS April 28-29, 1994 DIMACS Organized by P.M. Pardalos, M.G.C. Resende, and K.G. Ramakrishnan The talks in this workshop have covered a wide...
Chris Barrett, Achla Marathe, Madhav Marathe, Doug Cook, Gregory Hicks, Vance Faber, ...
We carry out a detailed empirical analysis of simple heuristics and provable algorithms for bilateral contract-satisfaction problems. Such problems arise due to the proposed deregulation of the...
Devdatt Dubhashi Aless, Ro Mei Aless, Ro Panconesi, Jaikumar Radhakrishnan, Aravind Srinivasan
Motivated by routing issues in ad hoc networks, we present polylogarithmic-time distributed algorithms for two problems. Given a network, we first show how to compute connected and weakly connected...
Devdatt Dubhashi, Alessandro Mei, Alessandro Panconesi, Jaikumar Radhakrishnan, Aravind Srinivasan
Motivated by routing issues in ad hoc networks, we present polylogarithmic-time distributed algorithms for two problems. Given a network, we rst show how to compute connected and weakly connected...
1 Resilient Multicast using Overlays (2007)
Suman Banerjee, Seungjoon Lee, Bobby Bhattacharjee, Aravind Srinivasan
We introduce PRM (Probabilistic Resilient Multicast): a multicast data recovery scheme that improves data delivery ratios while maintaining low end-to-end latencies. PRM has both a proactive and a...
Dependent Rounding in Bipartite Graphs Rajiv Gandhi (2007)
Samir Khuller, Srinivasan Parthasarathy, Aravind Srinivasan
We combine the pipage rounding technique of Ageev & Sviridenko witha recent rounding method developed by Srinivasan, to develop a new randomized rounding approach for fractional vectors defined...
(Peer-to-Peer Personal Privacy Protocol) provides sender-, receiver-, and sender-receiver (2007)
Rob Sherwood, Bobby Bhattacharjee, Aravind Srinivasan
We present a protocol for anonymous communication over the Internet. Our protocol, called P 5
Yi Li, Philip M. Long, Aravind Srinivasan
Haussler, Littlestone and Warmuth described a general-purpose algorithm for learning according to the prediction model, and proved an upper bound on the probability that their algorithm makes a...
Goran Konjevod, R. Ravi, Aravind Srinivasan
The covering Steiner problem is a common generalization of the k-MST and the group Steiner problems: given an edge-weighted graph, with subsets of vertices called the groups, and a nonnegative...
Wavelength rerouting in optical networks, or the Venetian routing problem (2007)
Alberto Caprara, G. Mohan, Alessandro Panconesi, Aravind Srinivasan
Wavelength rerouting has been suggested as a viable and cost-eective method to improve the blocking performance of wavelength-routed Wavelength-Division Multiplexing (WDM) networks. This method leads...
Samir Khuller, Aravind Srinivasan
We study the generalization of covering problems to partial covering. Here we wish to cover only a desired number of elements, rather than covering all elements as in standard covering problems. For...
Finding Large Independent Sets of Hypergraphs in Parallel (2007)
Hadas Shachnai, Aravind Srinivasan
A basic problem in hypergraphs is that of finding a large independent set--one of guaranteed size--in a given hypergraph. Understanding the parallel complexity of this and related independent set...
Improved bounds on the sample complexity of learning (2007)
Yi Li, Philip M. Long, Aravind Srinivasan
We present two improved bounds on the sample complexity of learning. First, we present a new general upper bound on the number of examples required to estimate all of the expectations of a set of...
Yi Li, Philip M. Long, Aravind Srinivasan
Haussler, Littlestone and Warmuth described a general-purpose algorithm for learning according to the prediction model, and proved a bound on the probability that their algorithm made a mistake in...
Leslie Ann Goldberg, Philip D. Mackenzie, Mike Paterson, Aravind Srinivasan
We study contention resolution in a multiple-access channel such as the Ethernet channel. In the model that we consider, n users generate messages for the channel according to a probability...
An Improved Approximation Algorithm for Vertex Cover with Hard Capacities (Extended Abstract) (2007)
Rajiv Gandhi, Eran Halperin, Samir Khuller, Guy Kortsarz, Aravind Srinivasan
Rajiv Gandhi , Eran Halperin , Samir Khuller , Guy Kortsarz , and Aravind Srinivasan Department of Computer Science, University of Maryland, College Park, MD 20742. Research supported by NSF Award...
The One-Inclusion Graph Algorithm is Near-Optimal for the Prediction Model of Learning (2007)
Yi Li, Philip M. Long, Aravind Srinivasan
Haussler, Littlestone and Warmuth described a general-purpose algorithm for learning according to the prediction model, and proved an upper bound on the probability that their algorithm makes a...
When Does a Random Robin Hood Win? (2007)
William Gasarch, Evan Golub, Aravind Srinivasan
A certain two-person infinite game (between “Robin Hood ” and the “Sheriff”) has been studied in the context of set theory. In certain cases, it is known that for any deterministic strategy...
Efficient Lookup on Unstructured Topologies (2006)
Morselli, Ruggero, Bhattacharjee, Bobby, Marsh, Michael A., Srinivasan, Aravind
We present LMS, a protocol for efficient lookup on unstructured networks. Our protocol uses a virtual namespace without imposing specific topologies. It is more efficient than existing lookup...
Efficient Lookup on Unstructured Topologies (2006)
Morselli, Ruggero, Bhattacharjee, Bobby, Marsh, Michael A., Srinivasan, Aravind
We present LMS, a protocol for efficient lookup on unstructured networks. Our protocol uses a virtual namespace without imposing specific topologies. It is more efficient than existing lookup...
Ranking Search Results in Peer-to-Peer Systems (2006)
Gopalakrishnan, Vijay, Morselli, Ruggero, Bhattacharjee, Bobby, Keleher, Peter, Srinivasan, Aravind
P2P deployments are a natural infrastructure for building distributed search networks. Proposed systems support locating and retrieving all results, but lack the information necessary to rank them....
Ranking Search Results in Peer-to-Peer Systems (2006)
Gopalakrishnan, Vijay, Morselli, Ruggero, Bhattacharjee, Bobby, Keleher, Peter, Srinivasan, Aravind
P2P deployments are a natural infrastructure for building distributed search networks. Proposed systems support locating and retrieving all results, but lack the information necessary to rank them....
Innovization: Innovative Design Principles Through Optimization (2006)
Kalyanmoy Deb, Aravind Srinivasan
This paper introduces a new design methodology (we called it an “innovization ” task) in the context of finding new and innovative design principles by means of optimization techniques. Although...
Anupam Gupta, Aravind Srinivasan
Abstract: In the Covering Steiner problem, we are given an undirected graph with edgecosts, and some subsets of vertices called groups, with each group being equipped with a non-negative integer...
Dependent rounding and its applications to approximation algorithms (2006)
Samir Khuller, Srinivasan Parthasarathy, Aravind Srinivasan
Abstract We develop a new randomized rounding approach for fractional vectors defined on the edge-sets of bipartite graphs. We show various ways of combining this technique with other ideas, leading...
Dependent rounding and its applications to approximation algorithms (2006)
Rajiv Gandhi, Samir Khuller, Srinivasan Parthasarathy, Aravind Srinivasan
We develop a new randomized rounding approach for fractional vectors defined on the edge-sets of bipartite graphs. We show various ways of combining this technique with other ideas, leading to...
A client-driven approach for channel management in wireless LANs (2006)
Arunesh Mishra, Vladimir Brik, Suman Banerjee, Aravind Srinivasan, William Arbaugh
Abstract — We propose an efficient client-based approach for channel management (channel assignment and load balancing) in 802.11-based WLANs that lead to better usage of the wireless spectrum....
The Catalytic Machinery of Chondroitinase ABC I Utilizes a Calcium Coordination (2006)
Strategy To Optimally, Vikas Prabhakar, Ishan Capila, Rahul Raman, Aravind Srinivasan, Carlos J. Bosques, ...
The chondroitinases are bacterial lyases that specifically cleave chondroitin sulfate and/or dermatan sulfate glycosaminoglycans. One of these enzymes, chondroitinase ABC I from Proteus Vulgaris, has...
On the Covering Steiner Problem (2006)
Anupam Gupta, Aravind Srinivasan
Abstract. The Covering Steiner problem is a common generalization of the k-MST and Group Steiner problems. An instance of the Covering Steiner problem consists of an undirected graph with edge-costs,...
A client-driven approach for channel management in wireless LANs (2006)
Arunesh Mishra, Vladimir Brik, Suman Banerjee, Aravind Srinivasan, William Arbaugh
We propose an efficient client-based approach for channel management (channel assignment and load balancing) in 802.11-based WLANs that lead to better usage of the wireless spectrum. This approach is...
A client-driven approach for channel management in wireless LANs (2006)
Arunesh Mishra, Vladimir Brik, Suman Banerjee, Aravind Srinivasan, William Arbaugh
Abstract — We propose an efficient client-based approach for channel management (channel assignment and load balancing) in 802.11-based WLANs that lead to better usage of the wireless spectrum....
The electronic and geometric properties of silicon-carbon fullerene-like nanostructures with two, four, six, twenty and twenty four carbon atoms on the surface of the Si60 cages by substitution, as...
Efficient Strategies for Channel Management in Wireless LANs (2005)
Arunesh Mishra, Vladimir Brik, Suman Banerjee, Aravind Srinivasan, William Arbaugh
We define efficient algorithms for channel management (channel assignment and load balancing among APs) in 802.11-based WLANs that lead to better usage of the wireless spectrum. These algorithms...
Efficient and Resilient Backbones for Multihop Wireless Networks (2005)
Seungjoon Lee, Bobby Bhattacharjee, Aravind Srinivasan, Samir Khuller
Abstract — We consider the problem of finding “backbones” in multihop wireless networks. The backbone provides end-toend connectivity, allowing non-backbone nodes to save energy since they do...
Efficient Lookup on Unstructured Topologies (2005)
Ruggero Morselli Bobby, Bobby Bhattacharjee, Michael A. Marsh, Aravind Srinivasan
We present LMS, a protocol for efficient lookup on unstructured networks. Our protocol uses a virtual namespace without imposing specific topologies. It is vastly more efficient than existing lookup...
Efficient and Resilient Backbones for Multihop Wireless Networks (2005)
Seungjoon Lee, Bobby Bhattacharjee, Aravind Srinivasan, Samir Khuller
Abstract — We consider the problem of finding “backbones” in mobile ad-hoc networks. The backbone provides end-to-end connectivity, allowing non-backbone nodes to save energy since they do not...
Efficient lookup on unstructured topologies (2005)
Ruggero Morselli, Bobby Bhattacharjee, Michael A. Marsh, Aravind Srinivasan
We present LMS, a protocol for efficient lookup on unstructured networks. Our protocol uses a virtual namespace without imposing specific topologies. It is more efficient than existing lookup...
Scalable resilient media streaming (2004)
Suman Banerjee, Seungjoon Lee, Ryan Braud, Bobby Bhattacharjee, Aravind Srinivasan
We present a low-overhead media streaming system, called SRMS (Scalable Resilient Media Streaming) that can be used to scalably deliver streaming data to a large group of receivers. SRMS uses overlay...
Approximation Algorithms for Partial Covering Problems (2004)
Rajiv Gandhi, Samir Khuller, Aravind Srinivasan
We study a generalization of covering problems called partial covering . Here we wish to cover only a desired number of elements, rather than covering all elements as in standard covering problems....
A Scalable Algorithm for the Minimum Expected Cost Restorable Flow Problem (2004)
Lisa Fleischer, Adam Meyerson, Iraj Saniee, Bruce Shepherd, Aravind Srinivasan
We introduce a model for the computation of a multicommodity flow together with back-up flows for each commodity after any of a given set of failure states occurs in a network. We call such a total...
Scalable resilient media streaming (2004)
Suman Banerjee, Seungjoon Lee, Bobby Bhattacharjee, Aravind Srinivasan, Ryan Braud
Abstract---We present a low-overhead media streaming system, called SRMS (Scalable Resilient Media Streaming) that can be used to scalably deliver streaming data to a large group of receivers. SRMS...
Scalable resilient media streaming (2004)
Suman Banerjee, Seungjoon Lee, Bobby Bhattacharjee, Aravind Srinivasan, Ryan Braud
Abstract—We present a low-overhead media streaming system, called SRMS (Scalable Resilient Media Streaming) that can be used to scalably deliver streaming data to a large group of receivers. SRMS...
An Extension of the Lovasz Local Lemma, and its Applications to Integer Programming (2003)
The Lovasz Local Lemma due to Erdos and Lovasz is a powerful tool in proving the existence of rare events. We present an extension of this lemma, which works well when the event to be shown to exist...
Scalable Resilient Media Streaming (2003)
Banerjee, Suman, Braud, Ryan, Lee, Seungjoon, Bhattacharjee, Bobby, Srinivasan, Aravind
We present a low-overhead media streaming system, called SRMS (Scalable Resilient Media Streaming) that can be used to scalably deliver streaming data to a large group of receivers. SRMS uses overlay...
Scalable Resilient Media Streaming (2003)
Banerjee, Suman, Braud, Ryan, Lee, Seungjoon, Bhattacharjee, Bobby, Srinivasan, Aravind
We present a low-overhead media streaming system, called SRMS (Scalable Resilient Media Streaming) that can be used to scalably deliver streaming data to a large group of receivers. SRMS uses overlay...
An Improved Approximation Algorithm For Vertex Cover with Hard Capacities (2003)
Gandhi, Rajiv, Halperin, Eran, Khuller, Samir, Kortsarz, Guy, Srinivasan, Aravind
In this paper we study the capacitated vertex cover problem, a generalization of the well-known vertex cover problem. Given a graph $G=(V,E)$, the goal is to cover all the edges by picking a minimum...
An Improved Approximation Algorithm For Vertex Cover with Hard Capacities (2003)
Gandhi, Rajiv, Halperin, Eran, Khuller, Samir, Kortsarz, Guy, Srinivasan, Aravind
In this paper we study the capacitated vertex cover problem, a generalization of the well-known vertex cover problem. Given a graph $G=(V,E)$, the goal is to cover all the edges by picking a minimum...
Resilient Multicast using Overlays (2003)
Suman Banerjee, Seungjoon Lee, Bobby Bhattacharjee, Aravind Srinivasan
(PRM): a multicast data recovery scheme that improves data delivery ratios while maintaining low end-to-end latencies. PRM has both a proactive and a reactive components; in this paper we describe...
Integrality ratio for group steiner trees and directed steiner trees (2003)
Eran Halperin, Guy Kortsarz, Robert Krauthgamer, Aravind Srinivasan, Nan Wang
The natural relaxation for the Group Steiner Tree problem, as well as for its generalization, the Directed Steiner Tree problem, is a flow-based linear programming relaxation. We prove new lower...
Scalable Resilient Media Streaming (2003)
Suman Banerjee Seungjoon, Suman Banerjee, Seungjoon Lee, Ryan Braud, Bobby Bhattacharjee, Aravind Srinivasan
We present a low-overhead media streaming system, called SRMS (Scalable Resilient Media Streaming) that can be used to scalably deliver streaming data to a large group of receivers. SRMS uses overlay...
Resilient Multicast Using Overlays (2003)
Suman Banerjee, Seungjoon Lee, Bobby Bhattacharjee, Aravind Srinivasan
We introduce PRM (Probabilistic Resilient Multicast): a multicast data recovery scheme that improves data delivery ratios while maintaining low end-to-end latencies. PRM has both a proactive and a...
A Scalable Algorithm for the Minimum Expected Cost Restorable Flow Problem (2003)
Lisa Fleischer, Adam Meyerson, Iraj Saniee, Bruce Shepherd, Aravind Srinivasan
We introduce a model for the computation of a multicommodity flow together with back-up flows for each commodity after any of a given set of failure states occurs in a network. We call such a total...
Resilient Multicast using Overlays (2003)
Suman Banerjee, Seungjoon Lee, Bobby Bhattacharjee, Aravind Srinivasan
We introduce PRM (Probabilistic Resilient Multicast): a multicast data recovery scheme that improves data de-livery ratios while maintaining low end-to-end latencies. PRM has both a proactive and a...
Integrality ratio for group steiner trees and directed steiner trees (2003)
Eran Halperin, Guy Kortsarz, Robert Krauthgamer, Aravind Srinivasan, Nan Wang
We present an Ω(log 2 k) lower bound on the integrality ratio of the flow-based relaxation for the Group Steiner Tree problem, where k denotes the number of groups; this holds even for input graphs...
Integrality ratio for group steiner trees and directed steiner trees (2003)
Eran Halperin, Guy Kortsarz, Robert Krauthgamer, Aravind Srinivasan, Nan Wang
The natural relaxation for the Group Steiner Tree problem, as well as for its generalization, the Directed Steiner Tree problem, is a flow-based linear programming relaxation. We prove new lower...
Integrality ratio for group steiner trees and directed steiner trees (2003)
Eran Halperin, Guy Kortsarz, Robert Krauthgamer, Aravind Srinivasan, Nan Wang
The natural relaxation for the Group Steiner Tree problem, as well as for its generalization, the Directed Steiner Tree problem, is a flow-based linear programming relaxation. We prove new lower...
Resilient Multicast using Overlays (2003)
Suman Banerjee, Seungjoon Lee, Bobby Bhattacharjee, Aravind Srinivasan
Multicast): a multicast data recovery scheme that improves data delivery ratios while maintaining low end-to-end latencies. PRM has both a proactive and a reactive components; in this paper we...
Integrality ratio for group steiner trees and directed steiner trees (2003)
Eran Halperin, Guy Kortsarz, Robert Krauthgamer, Aravind Srinivasan
We present an Ω(log 2 k) lower bound on the integrality ratio of the flow-based relaxation for the Group Steiner Tree problem, where k denotes the number of groups; this holds even for input graphs...
P 5 : A Protocol for Scalable Anonymous Communication (2002)
Rob Sherwood, Bobby Bhattacharjee, Aravind Srinivasan
We present a protocol for anonymous communication over the Internet. Our protocol, called P 5 (Peer-to-Peer Personal Privacy Protocol) provides sender-, receiver-, and sender-receiver anonymity. P 5...
Clustering and Server Selection Using Passive Monitoring (2002)
Matthew Andrews, Bruce Shepherd, Aravind Srinivasan, Peter Winkler, Francis Zane
Abstract — We consider the problem of client assignment in a distributed system of content servers. We present a system called Webmapper for clustering IP addresses and assigning each cluster to an...
P 5 : a protocol for scalable anonymous communication (2002)
Rob Sherwood, Bobby Bhattacharjee, Aravind Srinivasan
We present a protocol for anonymous communication over the
SCHEDULING AND ROUTING FOR DEMAND RESPONSIVE TRANSIT OPERATIONS (2001)
Aravind Srinivasan. Scheduling and Routing for Demand Responsive Transit Operations. (Under the direction of Dr. John W. Baugh and Dr. John R. Stone.)The multi-vehicle dial-a-ride problem has been...
Approximation Algorithms for Partial Covering Problems (2001)
Gandhi, Rajiv, Khuller, Samir, Srinivasan, Aravind
We study the generalization of covering problems to partial covering. Here we wish to cover only a desired number of elements, rather than covering all elements as in standard covering problems. For...
Approximation Algorithms for Partial Covering Problems (2001)
Gandhi, Rajiv, Khuller, Samir, Srinivasan, Aravind
We study the generalization of covering problems to partial covering. Here we wish to cover only a desired number of elements, rather than covering all elements as in standard covering problems. For...
Bi-directional packing of compressed multimedia data for improved error resiliency / (2001)
Thesis (M.S.)--Texas Tech University, 2001.
SCHEDULING AND ROUTING FOR DEMAND RESPONSIVE TRANSIT OPERATIONS (2001)
The multi-vehicle dial-a-ride problem has been proven to be intractable and NP-hard. Re-searchers have proposed numerous techniques for furnishing approximate solutions, but most of these aim at...
Approximation algorithms for partial covering problems (2001)
Samir Khuller, Aravind Srinivasan
We study the generalization of covering problems to partial covering. Here we wish to cover only a desired number of elements, rather than covering all elements as in standard covering problems. For...
Optimal Design of Signaling Networks for Internet Telephony (2000)
Aravind Srinivasan, K. G. Ramakrishnan, Krishnan Kumaran, Murali Aravamudan, Shamim Naqvi
We present an approach for efficient design of a signaling network for a network of software switches supporting Internet telephony. While one may take an Integer Programming approach to solve this...
Approximation algorithms for disjoint paths and related routing and packing problems (2000)
Alok Baveja, Aravind Srinivasan
Abstract. Given a network and a set of connection requests on it, we consider the maximum edge-disjoint paths and related generalizations and routing problems that arise in assigning paths for these...
Low discrepancy sets yield approximate min-wise independent permutation families (1999)
Michael Saks, Aravind Srinivasan, Shiyu Zhou, David Zuckerman
Motivated by a problem of filtering near-duplicate Web documents, Broder, Charikar, Frieze & Mitzenmacher defined the following notion of ffl-approximate min-wise independent permutation...
Approximation algorithms via randomized rounding: A survey (1999)
Approximation algorithms provide a natural way to approach computationally hard problems. There are currently many known paradigms in this area, including greedy algorithms, primal-dual methods,...
A Protocol for Scalable Anonymous (1999)
Communication Rob Sherwood, Rob Sherwood, Bobby Bhattacharjee, Aravind Srinivasan
We present a protocol for anonymous communication over the Internet.
Prasad Jayanti, Fillia Makedon, Aravind Srinivasan, Neal E. Young, Roger D. Sloboda, Stavros G. Kolliopoulos, ...
ii Network flow problems form a core area of Combinatorial Optimization. Their significance arises both from their very large number of applications and their theoretical importance. This thesis...
Contention Resolution with Constant Expected Delay (1998)
Leslie Ann Goldberg, Philip D. Mackenzie, Mike Paterson, Aravind Srinivasan
We study contention resolution in a multiple-access channel such as the Ethernet channel. In the model that we consider, n users generate messages for the channel according to a probability...
Explicit OR-Dispersers with Polylogarithmic Degree (1998)
Michael Saks, Aravind Srinivasan, Shiyu Zhou
An (N; M;T)-OR-disperser is a bipartite multigraph G = (V; W;E) with jV j = N , and jW j = M , having the following expansion property: any subset of V having at least T vertices has a neighbor set...
Abstract not available.
Better approximation guarantees for job-shop scheduling (1997)
Leslie Ann Goldberg, Mike Paterson, Aravind Srinivasan, Elizabeth Sweedyk
Abstract. Job-shop scheduling is a classical NP-hard problem. Shmoys, Stein, and Wein presented the first polynomial-time approximation algorithm for this problem that has a good (polylogarithmic)...
Aravind Srinivasan, Chung-piaw Teo
Abstract. We present the first constant-factor approximation algorithm for a fundamental problem: the store-and-forward packet routing problem on arbitrary networks. Furthermore, the queue sizes...
Aravind Srinivasan, Chung-piaw Teo
Abstract. We present the first constant-factor approximation algorithm for a fundamental problem: the store-and-forward packet routing problem on arbitrary networks. Furthermore, the queue sizes...
Approximating Hyper-Rectangles: Learning and Pseudo-random Sets (1997)
Peter Auer, Philip M. Long, Aravind Srinivasan
The PAC learning of rectangles has been studied because they have been found experimentally to yield excellent hypotheses for several applied learning problems. Also, pseudorandom sets for rectangles...
Randomized Distributed Edge Coloring via an Extension of the Chernoff-Hoeffding Bounds (1997)
Alessandro Panconesi, Aravind Srinivasan
. Certain types of routing, scheduling, and resource-allocation problems in a distributed setting can be modeled as edge-coloring problems. We present fast and simple randomized algorithms for edge...
Improved Algorithms via Approximations of Probability Distributions (1997)
Suresh Chari, Pankaj Rohatgi, Aravind Srinivasan
We present two techniques for approximating probability distributions. The first is a simple method for constructing the small-bias probability spaces introduced by Naor & Naor. We show how to...
Better Approximation Guarantees for Job-shop Scheduling (1997)
Leslie Ann Goldberg, Mike Paterson, Aravind Srinivasan, Elizabeth Sweedyk
Job-shop scheduling is a classical NP-hard problem. Shmoys, Stein &Wein presented the first polynomial-time approximation algorithm for this problem that has a good (polylogarithmic)...
Improved Algorithms via Approximations of Probability Distributions (1996)
Suresh Chari, Pankaj Rohatgi, Aravind Srinivasan
We present two techniques for approximating probability distributions. The first is a simple method for constructing the small-bias probability spaces introduced by Naor and Naor. We show how to...
Computing with Very Weak Random Sources (1996)
Aravind Srinivasan, David Zucherman
We study how to run randomized algorithms when the source of randomness is very defective (weak). For any fixed epsilon > 0, we show how to simulate RP algorithms in time n^{O(log n)} using the...
Computing with very weak random sources / (1996)
Srinivasan, Aravind., Zuckerman, David.
Abstract: "We study how to run randomized algorithms when the source of randomness is very defective (weak). For any fixed [epsilon]> 0, we show how to simulate RP algorithms in time n[superscript...
Improved algorithms via approximations of probability distributions / (1996)
Chari, Suresh., Rohatgi, Pankaj., Srinivasan, Aravind.
Abstract: "We present two techniques for approximating probability distributions. The first is a simple method for constructing the small-bias probability spaces introduced by Naor & Naor. We show...
An extension of the Lovasz Local Lemma, and its applications to integer programming (1996)
The Lov'asz Local Lemma (LLL) is a powerful tool in proving the existence of rare events. We present an extension of this lemma, which works well when the event to be shown to exist is a...
Better Approximation Guarantees for Job-Shop Scheduling (1996)
Leslie Ann Goldberg, Mike Paterson, Aravind Srinivasan, Elizabeth Sweedyk
Job-shop scheduling is a classical NP-hard problem. Shmoys, Stein & Wein presented the rst polynomial-time approximation algorithm for this problem that has a good (polylogarithmic) approximation...
An extension of the Lovasz Local Lemma, and its applications to integer programming (1996)
The Lovász Local Lemma due to Erdős and Lovász (in Infinite and Finite Sets, Colloq. Math. Soc. J. Bolyai 11, 1975, pp. 609–627) is a powerful tool in proving the existence of rare events. We...
Improved parallel approximation of a class of integer programming problems (1995)
We present a method to derandomize RNC algorithms, converting them to NC algorithms. Using it, we show how to approximate a class of NP-hard integer programming problems in NC, to within factors...
Improved Approximation Guarantees for Packing and Covering Integer Programs (1995)
Several important NP-hard combinatorial optimization problems can be posed as packing/covering integer programs; the randomized rounding technique of Raghavan and Thompson is a powerful tool to...
Contention resolution with bounded delay (1995)
Mike Paterson, Aravind Srinivasan
When distributed processes contend for a shared resource, we need a good distributed contention resolution protocol, e.g., for multiple-access channels (ALOHA, Ethernet), PRAM emulation, and optical...
Improved Approximation Guarantees for Packing and Covering Integer Programs (1995)
Several important NP-hard combinatorial optimization problems can be posed as packing/covering integer programs; the randomized rounding technique of Raghavan & Thompson is a powerful tool to...
Splitters and Near-Optimal Derandomization (1995)
Moni Naor, Leonard J. Schulman, Aravind Srinivasan
We present a fairly general method for finding deterministic constructions obeying what we call k- restrictions; this yields structures of size not much larger than the probabilistic bound. The...
Techniques for Probabilistic Analysis and Randomness-Efficient Computation (1993)
Randomness is well-recognized as an important computational resource in theoretical computer science. Not only are there classical problems for which the only known "efficient" solutions are...
Techniques for Probabilistic Analysis and Randomness-Efficient Computation (1993)
Randomness is well-recognized as an important computational resource in theoretical computer science. Not only are there classical problems for which the only known "efficient" solutions are...
Randomized Distributed Edge Coloring via an Extension of the Chernoff-Hoeffding Bounds (1993)
Panconesi, Alessandro, Srinivasan, Aravind
Certain types of routing, scheduling and resource allocation problems in a distributed setting can be modeled as edge coloring problems. We present fast and simple randomized algorithms for edge...
On the Complexity of Distributed Network Decomposition (1993)
Panconesi, Alessandro, Srinivasan, Aravind
In this paper, we improve the bounds for computing a network decomposition, which is a basic notion in distributed graph algorithms, distributively and deterministically. Our algorithm computes an...
Chari, Suresh, Rohatgi, Pankaj, Srinivasan, Aravind
In this paper, we precisely characterize the randomness complexity of the unique element isolation problem, a crucial step in the RNC algorithm for perfect matching due to Mulmuley, Vazirani and...
Randomized Distributed Edge Coloring via an Extension of the Chernoff-Hoeffding Bounds (1993)
Panconesi, Alessandro, Srinivasan, Aravind
Certain types of routing, scheduling and resource allocation problems in a distributed setting can be modeled as edge coloring problems. We present fast and simple randomized algorithms for edge...
On the Complexity of Distributed Network Decomposition (1993)
Panconesi, Alessandro, Srinivasan, Aravind
In this paper, we improve the bounds for computing a network decomposition, which is a basic notion in distributed graph algorithms, distributively and deterministically. Our algorithm computes an...
Chari, Suresh, Rohatgi, Pankaj, Srinivasan, Aravind
In this paper, we precisely characterize the randomness complexity of the unique element isolation problem, a crucial step in the RNC algorithm for perfect matching due to Mulmuley, Vazirani and...
"August 1993."
Chernoff-Hoeffding Bounds for Applications with Limited Independence (1992)
Schmidt, Jeanette P., Siegel, Alan, Srinivasan, Aravind
Chernoff-Hoeffding bounds are fundamental tools used in bounding the tail probabilities of the sums of bounded and independent random variables. We present a simple technique which gives slightly...
Chernoff-Hoeffding Bounds for Applications with Limited Independence (1992)
Schmidt, Jeanette P., Siegel, Alan, Srinivasan, Aravind
Chernoff-Hoeffding bounds are fundamental tools used in bounding the tail probabilities of the sums of bounded and independent random variables. We present a simple technique which gives slightly...
The Local Nature of $\Delta$-Coloring and Its Algorithmic Applications (1992)
Panconesi, Alessandro, Srinivasan, Aravind
Given a connected graph $G$ = ($V,E$) with $\mid$V$\mid$ = $n$ and maximum degree $\Delta$ such that $G$ is neither a complete graph nor an odd cycle, Brooks' theorem states that $G$ can be colored...
A Generalization of Brooks' Theorem (1992)
Given a connected graph $G = (V, E)$ with $n$ vertices and maximum degree $\Delta$ such that $\Delta \geq$ 3 and $G$ is not a complete graph, Brooks' theorem shows that $G$ is $\Delta$-colorable. We...
The Local Nature of $\Delta$-Coloring and Its Algorithmic Applications (1992)
Panconesi, Alessandro, Srinivasan, Aravind
Given a connected graph $G$ = ($V,E$) with $\mid$V$\mid$ = $n$ and maximum degree $\Delta$ such that $G$ is neither a complete graph nor an odd cycle, Brooks' theorem states that $G$ can be colored...
A Generalization of Brooks' Theorem (1992)
Given a connected graph $G = (V, E)$ with $n$ vertices and maximum degree $\Delta$ such that $\Delta \geq$ 3 and $G$ is not a complete graph, Brooks' theorem shows that $G$ is $\Delta$-colorable. We...
Srinivasan, Aravind, Viswanathan, Karthik, Raman, Rahul, Chandrasekaran, Aarthi, Raguram, S., Tumpey, Terrence M., ...
The human adaptation of influenza A viruses is critically governed by the binding specificity of the viral surface hemagglutinin (HA) to long (chain length) α2-6 sialylated glycan (α2-6) receptors...
Contention Resolution with Constant Expected Delay
Leslie Ann, Philip D. Mackenzie, Mike Paterson, Aravind Srinivasan
We study contention resolution in a multiple-access channel such as the Ethernet channel. In the model that we consider, n users generate messages for the channel according to a probability...
Nucleus management with irrigating vectis
The main objective in modern cataract surgery is to achieve a better unaided visual acuity with rapid post-surgical recovery and minimal surgery-related complications. Early visual rehabilitation and...