# D. Manjunath

## Contact Details

NameD. Manjunath |
||

Affiliation |
||

Location |
||

## Pubs By Year |
||

## Pub CategoriesComputer Science - Information Theory (5) Computer Science - Distributed; Parallel; and Cluster Computing (5) Mathematics - Information Theory (5) Computer Science - Computer Science and Game Theory (4) Mathematics - Probability (4) Computer Science - Networking and Internet Architecture (4) Computer Science - Performance (2) Mathematics - Optimization and Control (1) Computer Science - Data Structures and Algorithms (1) Computer Science - Learning (1) Computer Science - Computational Complexity (1) Mathematics - Combinatorics (1) |

## Publications Authored By D. Manjunath

We consider strategic arrivals to a FCFS service system that starts service at a fixed time and has to serve a fixed number of customers, e.g., an airplane boarding system. Read More

We consider a restless multi-armed bandit (RMAB) in which there are two types of arms, say A and B. Each arm can be in one of two states, say $0$ or $1.$ Playing a type A arm brings it to state $0$ with probability one and not playing it induces state transitions with arm-dependent probabilities. Read More

In this paper, we consider a two server system serving heterogeneous customers. One of the server has a FIFO scheduling policy and charges a fixed admission price to each customer. The second queue follows the highest-bidder-first (HBF) policy where an arriving customer bids for its position in the queue. Read More

In this paper, we consider revenue maximization problem for a two server system in the presence of heterogeneous customers. We assume that the customers differ in their cost for unit delay and this is modeled as a continuous random variable with a distribution $F.$ We also assume that each server charges an admission price to each customer that decide to join its queue. Read More

We describe and study a model for an Automated Online Recommendation System (AORS) in which a user's preferences can be time-dependent and can also depend on the history of past recommendations and play-outs. The three key features of the model that makes it more realistic compared to existing models for recommendation systems are (1) user preference is inherently latent, (2) current recommendations can affect future preferences, and (3) it allows for the development of learning algorithms with provable performance guarantees. The problem is cast as an average-cost restless multi-armed bandit for a given user, with an independent partially observable Markov decision process (POMDP) for each item of content. Read More

We consider a restless multi-armed bandit in which each arm can be in one of two states. When an arm is sampled, the state of the arm is not available to the sampler. Instead, a binary signal with a known randomness that depends on the state of the arm is made available. Read More

In this paper, a new model for traffic on roads with multiple lanes is developed, where the vehicles do not adhere to a lane discipline. Assuming identical vehicles, the dynamics is split along two independent directions: the Y-axis representing the direction of motion and the X-axis representing the lateral or the direction perpendicular to the direction of motion. Different influence graphs are used to model the interaction between the vehicles in these two directions. Read More

Given a capacitated communication network $\mathcal{N}$ and a function f that needs to be computed on $\mathcal{N},$ we study the problem of generating a computation and communication schedule in $\mathcal{N}$ to maximize the rate of computation of f. Shah et. al. Read More

We show a tight lower bound of $\Omega(N \log\log N)$ on the number of transmissions required to compute the parity of $N$ input bits with constant error in a noisy communication network of $N$ randomly placed sensors, each having one input bit and communicating with others using local transmissions with power near the connectivity threshold. This result settles the lower bound question left open by Ying, Srikant and Dullerud (WiOpt 06), who showed how the sum of all the $N$ bits can be computed using $O(N \log\log N)$ transmissions. The same lower bound has been shown to hold for a host of other functions including majority by Dutta and Radhakrishnan (FOCS 2008). Read More

We consider a queueing system with multiple heterogeneous servers serving a multiclass population. The classes are distinguished by the time costs. All customers have i. Read More

We consider optimal distributed computation of a given function of distributed data. The input (data) nodes and the sink node that receives the function form a connected network that is described by an undirected weighted network graph. The algorithm to compute the given function is described by a weighted directed acyclic graph and is called the computation graph. Read More

In a random key graph (RKG) of $n$ nodes each node is randomly assigned a key ring of $K_n$ cryptographic keys from a pool of $P_n$ keys. Two nodes can communicate directly if they have at least one common key in their key rings. We assume that the $n$ nodes are distributed uniformly in $[0,1]^2. Read More

We develop a stochastic approximation version of the classical Kaczmarz algorithm that is incremental in nature and takes as input noisy real time data. Our analysis shows that with probability one it mimics the behavior of the original scheme: starting from the same initial point, our algorithm and the corresponding deterministic Kaczmarz algorithm converge to precisely the same point. The motivation for this work comes from network tomography where network parameters are to be estimated based upon end-to-end measurements. Read More

We consider the problem where a network of sensors has to detect the presence of targets at any of $n$ possible locations in a finite region. All such locations may not be occupied by a target. The data from sensors is fused to determine the set of locations that have targets. Read More

We consider the problem of estimating functions of distributed data using a distributed algorithm over a network. The extant literature on computing functions in distributed networks such as wired and wireless sensor networks and peer-to-peer networks deals with computing linear functions of the distributed data when the alphabet size of the data values is small, O(1). We describe a distributed randomized algorithm to estimate a class of non-linear functions of the distributed data which is over a large alphabet. Read More

We consider in-network computation of an arbitrary function over an arbitrary communication network. A network with capacity constraints on the links is given. Some nodes in the network generate data, e. Read More

In this paper, we analyze the performance of random load resampling and migration strategies in parallel server systems. Clients initially attach to an arbitrary server, but may switch server independently at random instants of time in an attempt to improve their service rate. This approach to load balancing contrasts with traditional approaches where clients make smart server selections upon arrival (e. Read More

Packet-dispersion based measurement tools insert pairs of probe packets with a known separation into the network for transmission over a unicast path or a multicast tree. Samples of the separation between the probe pairs at the destination(s) are observed. Heuristic techniques are then used by these tools to estimate the path characteristics from the observations. Read More

We consider in-network computation of MAX in a structure-free random multihop wireless network. Nodes do not know their relative or absolute locations and use the Aloha MAC protocol. For one-shot computation, we describe a protocol in which the MAX value becomes available at the origin in $O(\sqrt{n/\log n})$ slots with high probability. Read More

We consider distributed computation of functions of distributed data in random planar networks with noisy wireless links. We present a new algorithm for computation of the maximum value which is order optimal in the number of transmissions and computation time.We also adapt the histogram computation algorithm of Ying et al to make the histogram computation time optimal. Read More

Let P := {X_i,i >= 1} be a stationary Poisson point process in R^d, {C_i,i >= 1} be a sequence of i.i.d. Read More

E-commerce Web-servers often face overload conditions during which revenue-generating requests may be dropped or abandoned due to an increase in the browsing requests. In this paper we present a simple, yet effective, mechanism for overload control of E-commerce Web-servers. We develop an E-commerce workload model that separates the browsing requests from revenue-generating transaction requests. Read More

In this paper we study the one dimensional random geometric graph when the location of the nodes are independent and exponentially distributed. We derive exact results and the limit theorems for the connectivity and other properties associated with this random graph. We show that the asymptotic properties of a graph with a truncated exponential distribution can be obtained using the exponential random geometric graph. Read More