Search

We propose, develop, and compare new stochastic models for the daily arrival rate in a call center. Following standard practice, the day is divided into time periods of equal length (e.g., 15 or 30 minutes), the arrival rate is assumed random but constant in time in each period, and the arrivals are from a Poisson process, conditional on the rate. The random rate for each period is taken as a deterministic base rate (or expected rate) multiplied by a random busyness factor having mean 1. Models in which the busyness factors are independent across periods, or in which a common busyness factor applies to all periods, have been studied previously. But they are not sufficiently realistic. We examine alternative models for which the busyness factors have some form of dependence across periods. Maximum likelihood parameter estimation for these models is not easy, mainly because the arrival rates themselves are never observed. We develop specialized techniques to perform this estimation. We compare the goodness-of-fit of these models on arrival data from three call centers, both in-sample and out-of-sample. Our models can represent arrivals in many other types of systems as well. Estimating a model for the vector of counts (the number of arrivals in each period) is generally easier than for the vector of rates, because the counts can be observed, but a model for the rates is often more convenient and natural, e.g., for simulation. We examine and provide insight on the relationship between these two types of modeling. In particular, we give explicit formulas for the relationship between the correlation between rates and that between counts in two given periods, and for the variance and dispersion index in a given period. These formulas imply that for a given correlation between the rates, the correlation between the counts is much smaller in low traffic than in high traffic. [ABSTRACT FROM AUTHOR]

This paper presents a novel probabilistic voxel selection strategy for medical image registration in time-sensitive contexts, where the goal is aggressive voxel sampling (e.g., using less than 1% of the total number) while maintaining registration accuracy and low failure rate. We develop a Bayesian framework whereby, first, a voxel sampling probability field (VSPF) is built based on the uncertainty on the transformation parameters. We then describe a practical, multi-scale registration algorithm, where, at each optimization iteration, different voxel subsets are sampled based on the VSPF. The approach maximizes accuracy without committing to a particular fixed subset of voxels. The probabilistic sampling scheme developed is shown to manage the tradeoff between the robustness of traditional random voxel selection (by permitting more exploration) and the accuracy of fixed voxel selection (by permitting a greater proportion of informative voxels). [ABSTRACT FROM AUTHOR]

This paper proposes a novel framework for delay-tolerant particle filtering that is computationally efficient and has limited memory requirements. Within this framework the informativeness of a delayed (out-of-sequence) measurement (OOSM) is estimated using a lightweight procedure and uninformative measurements are immediately discarded. The framework requires the identification of a threshold that separates informative from uninformative; this threshold selection task is formulated as a constrained optimization problem, where the goal is to minimize state estimation error whilst controlling the computational requirements. We develop an algorithm that provides an approximate solution for the optimization problem. Simulation experiments provide an example where the proposed framework processes less than 40% of all OOSMs with only a small reduction in state estimation accuracy. [ABSTRACT FROM PUBLISHER]

This paper presents greedy gossip with eavesdropping (GGE), a novel randomized gossip algorithm for distributed computation of the average consensus problem. In gossip algorithms, nodes in the network randomly communicate with their neighbors and exchange information iteratively. The algorithms are simple and decentralized, making them attractive for wireless network applications. In general, gossip algorithms are robust to unreliable wireless conditions and time varying network topologies. In this paper, we introduce GGE and demonstrate that greedy updates lead to rapid convergence. We do not require nodes to have any location information. Instead, greedy updates are made possible by exploiting the broadcast nature of wireless communications. During the operation of GGE, when a node decides to gossip, instead of choosing one of its neighbors at random, it makes a greedy selection, choosing the node which has the value most different from its own. In order to make this selection, nodes need to know their neighbors' values. Therefore, we assume that all transmissions are wireless broadcasts and nodes keep track of their neighbors' values by eavesdropping on their communications. We show that the convergence of GGE is guaranteed for connected network topologies. We also study the rates of convergence and illustrate, through theoretical bounds and numerical simulations, that GGE consistently outperforms randomized gossip and performs comparably to geographic gossip on moderate-sized random geometric graph topologies. [ABSTRACT FROM AUTHOR]

Distributed averaging describes a class of network algorithms for the decentralized computation of aggregate statistics. Initially, each node has a scalar data value, and the goal is to compute the average of these values at every node (the so-called average consensus problem). Nodes iteratively exchange information with their neighbors and perform local updates until the value at every node converges to the initial network average. Much previous work has focused on algorithms where each node maintains and updates a single value; every time an update is performed, the previous value is forgotten. Convergence to the average consensus is achieved asymptotically. The convergence rate is fundamentally limited by network connectivity, and it can be prohibitively slow on topologies such as grids and random geometric graphs, even if the update rules are optimized. In this paper, we provide the first theoretical demonstration that adding a local prediction component to the update rule can significantly improve the convergence rate of distributed averaging algorithms. We focus on the case where the local predictor is a linear combination of the node's current and previous values (i.e., two memory taps), and our update rule computes a combination of the predictor and the usual weighted linear combination of values received from neighboring nodes. We derive the optimal mixing parameter for combining the predictor with the neighbors' values, and conduct a theoretical analysis of the improvement in convergence rate that can be achieved using this acceleration methodology. For a chain topology on N nodes, this leads to a factor of improvement over standard consensus, and for a two-dimensional grid, our approach achieves a factor of √N improvement. [ABSTRACT FROM AUTHOR]

This paper proposes an approach to accelerate local, linear iterative network algorithms asymptotically achieving distributed average consensus. We focus on the class of algorithms in which each node initializes its "state value" to the local measurement and then at each iteration of the algorithm, updates this state value by adding a weighted sum of its own and its neighbors' state values. Provided the weight matrix satisfies certain convergence conditions, the state values asymptotically converge to the average of the measurements, but the convergence is generally slow, impeding the practical application of these algorithms. In order to improve the rate of convergence, we propose a novel method where each node employs a linear predictor to predict future node values. The local update then becomes a convex (weighted) sum of the original consensus update and the prediction; convergence is faster because redundant states are bypassed. The method is linear and poses a small computational burden. For a concrete theoretical analysis, we prove the existence of a convergent solution in the general case and then focus on one-step prediction based on the current state, and derive the optimal mixing parameter in the convex sum for this case. Evaluation of the optimal mixing parameter requires knowledge of the eigenvalues of the weight matrix, so we present a bound on the optimal parameter. Calculation of this bound requires only local information. We provide simulation results that demonstrate the validity and effectiveness of the proposed scheme. The results indicate that the incorporation of a multistep predictor can lead to convergence rates that are much faster than those achieved by an optimum weight matrix in the standard consensus framework. [ABSTRACT FROM AUTHOR]