Explore the vast range of titles available.

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 a barrier coverage problem in the distributed and discrete setting. We assume that we have n identical sensors located at grid positions on the barrier, and that 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 Θ ( n 2 ) 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 in which a sensor can only move a constant distance in one step requires Ω ( n ) steps on some inputs, our second algorithm is asymptotically optimal.

Low-cost, high-throughput in vitro bioassays have potential as alternatives to animal models for toxicity testing. However, incorporating in vitro bioassays into chemical toxicity evaluations such as read-across requires significant data curation and analysis based on knowledge of relevant toxicity mechanisms, lowering the enthusiasm of using the massive amount of unstructured public data. We aimed to develop a computational method to automatically extract useful bioassay data from a public repository (i.e., PubChem) and assess its ability to predict animal toxicity using a novel bioprofile-based read-across approach. A training database containing 7,385 compounds with diverse rat acute oral toxicity data was searched against PubChem to establish in vitro bioprofiles. Using a novel subspace clustering algorithm, bioassay groups that may inform on relevant toxicity mechanisms underlying acute oral toxicity were identified. These bioassays groups were used to predict animal acute oral toxicity using read-across through a cross-validation process. Finally, an external test set of over 600 new compounds was used to validate the resulting model predictivity. Several bioassay clusters showed high predictivity for acute oral toxicity (positive prediction rates range from 62-100%) through cross-validation. After incorporating individual clusters into an ensemble model, chemical toxicants in the external test set were evaluated for putative acute toxicity (positive prediction rate equal to 76%). Additionally, chemical fragment -in vitro-in vivo relationships were identified to illustrate new animal toxicity mechanisms. The in vitro bioassay data-driven profiling strategy developed in this study meets the urgent needs of computational toxicology in the current big data era and can be extended to develop predictive models for other complex toxicity end points. https://doi.org/10.1289/EHP3614.

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].

We study a problem of online targets coverage by a drone or a sensor that is equipped with a camera or an antenna of fixed half-angle of view \\(\\). The targets to be monitored appear at arbitrary positions on a line barrier in an online manner. When a new target appears, the drone has to move to a location that covers the newly arrived target, as well as already existing targets. The objective is to design a coverage algorithm that optimizes the total length of the drone's trajectory. Our results are reported in terms of an algorithm's competitive ratio, i.e., the worst-case ratio (over all inputs) of its cost to that of an optimal offline algorithm. In terms of upper bounds, we present three online algorithms and prove bounds on their competitive ratios for every \\( ın [0, /2]\\). The best of them, called is significantly better than the other two for \\(/6 < < /3\\). In particular, for \\(=/4\\), its worst case, has competitive ratio \\(1.25\\), while the other two have competitive ratio \\(2\\). Finally, we prove a lower bound on the competitive ratio of online algorithms for a drone with half-angle \\( ın [0, /4]\\); this bound is a function of \\(\\) that achieves its maximum value at \\( = /4\\) equal to \\((1+2)/2 1.207\\).

Two robots stand at the origin of the infinite line and are tasked with searching collaboratively for an exit at an unknown location on the line. They can travel at maximum speed \\(b\\) and can change speed or direction at any time. The two robots can communicate with each other at any distance and at any time. The task is completed when the last robot arrives at the exit and evacuates. We study time-energy tradeoffs for the above evacuation problem. The evacuation time is the time it takes the last robot to reach the exit. The energy it takes for a robot to travel a distance \\(x\\) at speed \\(s\\) is measured as \\(xs^2\\). The total and makespan evacuation energies are respectively the sum and maximum of the energy consumption of the two robots while executing the evacuation algorithm. Assuming that the maximum speed is \\(b\\), and the evacuation time is at most \\(cd\\), where \\(d\\) is the distance of the exit from the origin, we study the problem of minimizing the total energy consumption of the robots. We prove that the problem is solvable only for \\(bc 3\\). For the case \\(bc=3\\), we give an optimal algorithm, and give upper bounds on the energy for the case \\(bc>3\\). We also consider the problem of minimizing the evacuation time when the available energy is bounded by \\(\\). Surprisingly, when \\(\\) is a constant, independent of the distance \\(d\\) of the exit from the origin, we prove that evacuation is possible in time \\(O(d^3/2 d)\\), and this is optimal up to a logarithmic factor. When \\(\\) is linear in \\(d\\), we give upper bounds on the evacuation time.

Queen Daniela of Sardinia is asleep at the center of a round room at the top of the tower in her castle. She is accompanied by her faithful servant, Eva. Suddenly, they are awakened by cries of \"Fire\". The room is pitch black and they are disoriented. There is exactly one exit from the room somewhere along its boundary. They must find it as quickly as possible in order to save the life of the queen. It is known that with two people searching while moving at maximum speed 1 anywhere in the room, the room can be evacuated (i.e., with both people exiting) in \\(1 + 23 + 3 4.8264\\) time units and this is optimal~[Czyzowicz et al., DISC'14], assuming that the first person to find the exit can directly guide the other person to the exit using her voice. Somewhat surprisingly, in this paper we show that if the goal is to save the queen (possibly leaving Eva behind to die in the fire) there is a slightly better strategy. We prove that this \"priority\" version of evacuation can be solved in time at most \\(4.81854\\). Furthermore, we show that any strategy for saving the queen requires time at least \\(3 + /6 + 3/2 4.3896\\) in the worst case. If one or both of the queen's other servants (Biddy and/or Lili) are with her, we show that the time bounds can be improved to \\(3.8327\\) for two servants, and \\(3.3738\\) for three servants. Finally we show lower bounds for these cases of \\(3.6307\\) (two servants) and \\(3.2017\\) (three servants). The case of \\(n 4\\) is the subject of an independent study by Queen Daniela's Royal Scientific Team.

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 \\(k2\\) 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.

We revisit the linear search problem where a robot, initially placed at the origin on an infinite line, tries to locate a stationary target placed at an unknown position on the line. Unlike previous studies, in which the robot travels along the line at a constant speed, we consider settings where the robot's speed can depend on the direction of travel along the line, or on the profile of the terrain, e.g. when the line is inclined, and the robot can accelerate. Our objective is to design search algorithms that achieve good competitive ratios for the time spent by the robot to complete its search versus the time spent by an omniscient robot that knows the location of the target. We consider several new robot mobility models in which the speed of the robot depends on the terrain.These include 1) different constant speeds for different directions, 2) speed with constant acceleration and/or variability depending on whether a certain segment has already been searched, 3) speed dependent on the incline of the terrain. We provide both upper and lower bounds on the competitive ratios of search algorithms for these models, and in many cases, we derive optimal algorithms for the search time.

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.