We consider evacuation of a group of $n \geq 2$ autonomous mobile agents (or robots) from an unknown exit on an infinite line. The agents are initially placed at the origin of the line and can move with any speed up to the maximum speed $1$ in any direction they wish and they all can communicate when they are co-located. However, the agents have different wireless communication abilities: while some are fully wireless and can send and receive messages at any distance, a subset of the agents are senders, they can only transmit messages wirelessly, and the rest are receivers, they can only receive messages wirelessly. The agents start at the same time and their communication abilities are known to each other from the start. Starting at the origin of the line, the goal of the agents is to collectively find a target/exit at an unknown location on the line while minimizing the evacuation time, defined as the time when the last agent reaches the target. We investigate the impact of such a mixed communication model on evacuation time on an infinite line for a group of cooperating agents. In particular, we provide evacuation algorithms and analyze the resulting competitive ratio ($CR$) of the evacuation time for such a group of agents. If the group has two agents of two different types, we give an optimal evacuation algorithm with competitive ratio $CR=3+2 \sqrt{2}$. If there is a single sender or fully wireless agent, and multiple receivers we prove that $CR \in [2+\sqrt{5},5]$, and if there are multiple senders and a single receiver or fully wireless agent, we show that $CR \in [3,5.681319]$. Any group consisting of only senders or only receivers requires competitive ratio 9, and any other combination of agents has competitive ratio 3.

Consider two robots that start at the origin of the infinite line in search of an exit at an unknown location on the line. The robots can only communicate if they arrive at the same location at exactly the same time, i.e. they use the so-called face-to-face communication model. The group search time is defined as the worst-case time as a function of $d$, the distance of the exit from the origin, when both robots can reach the exit. It has long been known that for a single robot traveling at unit speed, the search time is at least $9d-o(d)$. It was shown recently that $k\geq2$ robots traveling at unit speed also require at least $9d$ group search time. We investigate energy-time trade-offs in group search by two robots, where the energy loss experienced by a robot traveling a distance $x$ at constant speed $s$ is given by $s^2 x$. Specifically, we consider the problem of minimizing the total energy used by the robots, under the constraints that the search time is at most a multiple $c$ of the distance $d$ and the speed of the robots is bounded by $b$. Motivation for this study is that for the case when robots must complete the search in $9d$ time with maximum speed one, a single robot requires at least $9d$ energy, while for two robots, all previously proposed algorithms consume at least $28d/3$ energy. When the robots have bounded memory, we generalize existing algorithms to obtain a family of optimal (and in some cases nearly optimal) algorithms parametrized by pairs of $b,c$ values that can solve the problem for the entire spectrum of these pairs for which the problem is solvable. We also propose a novel search algorithm, with unbounded memory, that simultaneously achieves search time $9d$ and consumes energy $8.42588d$. Our result shows that two robots can search on the line in optimal time $9d$ while consuming less total energy than a single robot within the same search time.

Summary: We have developed a public Chemical In vitro–In vivo Profiling (CIIPro) portal, which can automatically extract in vitro biological data from public resources (i.e. PubChem) for user-supplied compounds. For compounds with in vivo target activity data (e.g. animal toxicity testing results), the integrated cheminformatics algorithm will optimize the extracted biological data using in vitro–in vivo correlations. The resulting in vitro biological data for target compounds can be used for read-across risk assessment of target compounds. Additionally, the CIIPro portal can identify the most similar compounds based on their optimized bioprofiles. The CIIPro portal provides new powerful assessment capabilities to the scientific community and can be easily integrated with other cheminformatics tools. Availability and Implementation: ciipro.rutgers.edu. Contact: [email protected] or [email protected]

We consider the problem of fault-tolerant parallel search on an infinite line by n robots. Starting from the origin, the robots are required to find a target at an unknown location. The robots can move with maximum speed 1 and can communicate in wireless mode among themselves. However, among the n robots, there are f robots that exhibit byzantine faults. A faulty robot can fail to report the target even after reaching it, or it can make malicious claims about having found the target when in fact it has not. Given the presence of such faulty robots, the search for the target can only be concluded when the non-faulty robots have sufficient verification that the target has been found. We aim to design algorithms that minimize the value of S_d (n, f), the time to find a target at a distance d from the origin by n robots among which f are faulty. We give several different algorithms whose running time depends on the ratio f/n, the density of faulty robots, and also prove lower bounds. Our algorithms are optimal for some densities of faulty robots.

We study the barrier coverage problem using relocatable sensor nodes. We assume each sensor can sense an intruder or event inside its sensing range. Sensors are initially located at arbitrary positions on the barrier and can move along the barrier. The goal is to find final positions for sensors so that the entire barrier is covered. In recent years, the problem has been studied extensively in the centralized setting. In this paper, we study the problem in the distributed setting. We assume each sensor repeatedly executes a Look-Compute-Move cycle: based on what it sees in its vicinity, it makes a decision on where to move, and moves to its next position. We make two strong but realistic restrictions on the capabilities of sensors: they have a constant visibility range and can move only a constant distance in every cycle. In this model, we give the first two distributed algorithms that achieve barrier coverage for a line segment barrier when there are enough nodes in the network to cover the entire barrier. Our algorithms are synchronous, and local in the sense that sensors make their decisions independently based only on what they see within their constant visibility range. One of our algorithms is oblivious whereas the other uses two bits of memory at each sensor to store the type of move made in the previous step. We show that our oblivious algorithm terminates within Θ(n2) steps with the barrier fully covered, while the constant-memory algorithm is shown to take Θ(n) steps to terminate in the worst case. Since any algorithm that can only move a constant distance in one step requires Ω(n) steps on some inputs, our second algorithm is asymptotically optimal. Finally, both our algorithms are self-stabilizing, and can be easily extended to the case of non-homogeneous sensors, and for the case when the barrier is a circle.

Assume that n sensors with identical range r = f(n)⁄2n, for some f(n) ≥ 1 for all n, are thrown randomly and independently with the uniform distribution in the unit interval [0, 1]. They are required to move to new positions so as to cover the entire unit interval in the sense that every point in the interval is within the range of a sensor. We obtain tradeoffs between the expected sum and maximum of displacements of the sensors and their range required to accomplish this task. In particular, when f(n) -- 1 the expected total displacement is shown to be Θ(√n). For senors with larger ranges we present two algorithms that prove the upper bound for the sum drops sharply as f(n) increases. The first of these holds for f(n) ≥ 6 and shows the total movement of the sensors is O(√ ln n/f(n)) while the second holds for 12 ≤ f(n) ≤ ln n -- 2 ln ln n and gives an upper bound of O(lnn⁄ f(n)ef(n)/2). Note that the second algorithm improves upon the first for f(n) > ln ln n -- ln ln ln n. Further we show a lower bound, for any 1 < f(n) < √n of Ω(εf(n)ε--(1+ε)f(n)), ε > 0.

The achromatic number of a graph $G = (V,E)$ with $|V| = n$ vertices is the largest number k with the following property: the vertices of G can be partitioned into k independent subsets $\{V_i\}_{1 \leq i \leq k}$ such that for every distinct pair of subsets $V_i,V_j$ in the partition, there is at least one edge in E that connects these subsets. We describe a greedy algorithm that computes the achromatic number of a bipartite graph within a factor of $O(n^{4/5})$ of the optimal. Prior to our work, the best known approximation factor for this problem was $n \log\log n /\log n$ as shown by Kortsarz and Krauthgamer [SIAM J. Discrete Math., 14 (2001), pp. 408–422].

Position-based routing algorithms for mobile ad hoc networks utilize the position or location of the destination node to inform routing decisions. We consider the problem of routing in an ad hoc network where the source node knows the approximate position of the destination node, but is uncertain about its exact current location. We investigate two approaches to this problem: one, based on a traversal of the faces of a planar sub-graph of the graph representing the network, and the second, based on flooding a limited area of the graph that represents the region the destination is likely to be found. We propose several variants of both approaches, and do extensive simulations to analyze the performance of the algorithms. Our results indicate that a simple modification of the basic flooding approach yields the best trade-off for optimizing delivery rate, stretch factor, as well as transmission cost. If however, delivery is required to be guaranteed, then a variant of the face tree approach in P. Bose et al. (2002) that we propose has the best performance

Though most lossless image coding techniques use a raster scan to order the pixels for context-based predictive coding, other scans, such as the Hilbert or Peano scan, have been proposed as alternatives with potentially better performance. However, a general understanding of the merits of different scans has been lacking. In previous work, the authors had presented a framework in which the effect of pixel scan order on lossless compression can be quantitatively analyzed, so that comparisons of different scans can be made. Assuming a quantized-Gaussian and isotropic image model with contexts consisting of previously scanned adjacent pixels in a distance constrained neighborhood, it was found that the raster scan is better than the Hilbert scan. In this paper we further develop our arguments and show that for a large class of scans, which we call axial symmetric scans, the raster scan is indeed optimal. We would like to note that many common scans including the Hilbert scan fall under the class of axial symmetric scans.

Though most image coding techniques use a raster scan to order pixels prior to coding, Hilbert and other scans have been proposed as having better performance due to their superior locality preserving properties. However, a general understanding of the merits of various scans has been lacking. This paper develops an approach for quantitatively analyzing the effect of pixel scan order for context-based, predictive lossless image compression and uses it to compare raster, Hilbert, random and hierarchical scans. Specifically, for a quantized-Gaussian image model and a given scan order, it shows how the encoding rate can be estimated from the frequencies with which various pixel configurations are available as previously scanned contexts, and from the corresponding conditional differential entropies. Formulas are derived for such context frequencies and entropies. Assuming an isotropic image model and contexts consisting of previously scanned adjacent pixels, it is found that the raster scan is better than the Hilbert scan which is often used in compression applications due to its locality preserving properties. The hierarchical scan is better still, though it is based on nonadjacent contexts. The random scan is the worst of the four considered. Extensions and implications of the results to lossy coding are also discussed.

The authors have previously analyzed the performance of context-based lossless image coding techniques in conjunction with the Hilbert and raster scans. The analysis revealed that, under certain reasonable assumptions, the raster scan is indeed better than the Hilbert scan, thereby dispelling the popular notion that using a Hilbert scan would always lead to improved performance. In this paper they apply similar techniques to analyze a random scan as well as a progressive scan (closely based on the commonly used HINT scan). They demonstrate that the progressive scan outperforms the raster scan, but that the expected performance of a random scan is inferior to the other three systematic scans considered so far.

In this paper, we consider the problem of shortest path interval routing, a space-efficient strategy for routing in distributed networks. In this scheme, an ordering of the vertices is chosen so that the edges of the network can be labeled with one or more subintervals of the vertex ordering: The resulting routing tables must be deterministic and route along shortest paths between all pairs of vertices. We first show constructively that any interval graph can be labeled with one circular subinterval on each edge; this extends a known result for proper interval graphs. We also provide a partial characterization for networks that admit linear interval routing when edges are labeled with exactly one interval, in terms of the biconnected components of any such network. This is the first such characterization when the paths are required to be shortest paths under the distance metric. Finally, we show that the class of networks that can be labeled with k ≥ 1 subintervals per edge is closed under composition with a certain class of graphs. © 1998 John Wiley & Sons, Inc. Networks 32: 103–113, 1998

We study the problem of placing erasure nodes among passive stations in a slotted dual bus network. Erasure nodes are known to improve throughput by allowing slot reuse. It is also known that choices made in locating erasure nodes significantly impact network congestion and overall throughput-especially when traffic patterns exhibit a high degree of locality. We present algorithms to determine optimal placements of erasure nodes that improve upon prior work on this problem: we present simpler and faster polynomial-time algorithms and also consider various useful cost measures. These algorithms can be used to solve related placement problems in which limits on congestion and existing placements are given as input, and the goal is to find the minimum number of erasure nodes required to meet the congestion bound.

Proposes a novel approach that combines the space covering property of high rate lattice VQ with the pattern matching ability of clustering VQ. The proposed scheme encompasses a broad range of online algorithms that use suitable VQ encodings and fixed-size, adaptive codebooks. The generic baseline algorithm for the scheme has the following desirable characteristics: the distortion per individual vector is guaranteed to be less than a user specified threshold. Secondly, the algorithm is amenable to fast realtime implementation and requires minimal statistical assumptions for analysis. Finally, with careful analysis, the coding rate can be bounded with respect to some theoretical benchmark.>

Control grammars, a generalization of context-free grammars recently introduced for use in natural language recognition, are investigated. In particular, it is shown that a hierarchy of non-context-free languages, called control language hierarchy (CLH), generated by control grammars can be recognized in polynomial time. Previously, the best-known upper bound was exponential time. It is also shown that CLH is in NC(2), the class of languages recognizable by uniform boolean circuits of polynomial size and O(log2 n) depth.

An optimal parallel recognition/parsing algorithm is presented for languages generated by tree adjoining grammars (TAGs), a grammatical system for natural language. TAGs are strictly more powerful than context-free grammars (CFGs), e.g., they can generate $\{a'' b'' c'' | n \geqq 0\}$, which is not context-free. However, serial parsing of TAGs is also slower, having time complexity $O(n^{6})$ for inputs of length n (as opposed to $O(n^{3})$ for CFGs). The parallel algorithm achieves optimal speedup: it runs in linear time on a five-dimensional array of $n^5$ processors. Moreover, the processors are finite-state; i.e., their function and size depends only on the underlying grammar and not on the length of the input.