Search

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 \geq 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 $\Delta$. Surprisingly, when $\Delta$ 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}\log d)$, and this is optimal up to a logarithmic factor. When $\Delta$ is linear in $d$, we give upper bounds on the evacuation time., Comment: This is the full version of the paper with the same title which will appear in the proceedings of the 26th International Colloquium on Structural Information and Communication Complexity (SIROCCO'19) L'Aquila, Italy during July 1-4, 2019

An exit (or target) is at an unknown location on the perimeter of a unit disk. A group of n + 1 robots (in our case, n = 1 , 2 , 3 ), initially located at the centre of the disk, are tasked with finding the exit. The robots have unique identities, share the same coordinate system, move at maximum speed 1 and are able to communicate wirelessly the position of the exit once found. Among them there is a distinguished robot called the queen and the remainder of the robots are referred to as servants. It is known that with two robots searching, the room can be evacuated (i.e., with both robots reaching the exit) in 1 + 2 π 3 + 3 ≈ 4.8264 time units and this is optimal [11] . Somewhat surprisingly, in this paper we show that if the goal is to have the queen reach the exit, not caring if her servants make it, there is a slightly better strategy for the case of one servant. 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 with one servant requires time at least 3 + π / 6 + 3 / 2 ≈ 4.3896 in the worst case. If more servants are available, we show that the time bounds can be improved to 3.8327 for two servants, and 3.3738 for three servants which are better than the known lower bound for the corresponding problems of evacuating three or four robots. Finally, we show lower bounds for these cases of 3.6307 (two servants) and 3.2017 (three servants). The case of more than three servants uses substantially different techniques and is discussed in a separate paper [13] .

We consider the problem of collective exploration of a known n-node edge-weighted graph by k mobile agents that have limited energy but are capable of energy transfers. The agents are initially placed at an arbitrary subset of nodes in the graph, and each agent has an initial, possibly different, amount of energy. The goal of the exploration problem is for every edge in the graph to be traversed by at least one agent. The amount of energy used by an agent to travel distance x is proportional to x. In our model, the agents can share energy when co-located: when two agents meet, one can transfer part of its energy to the other.

We introduce a new problem which we call the Pony Express problem. n robots with differing speeds are situated over some domain. A message is placed at some commonly known point. Robots can acquire the message either by visiting its initial position, or by encountering another robot that has already acquired it. The robots must collaborate to deliver the message to a given destination (We restrict our attention to message transmission rather than package delivery, which differs from message transmission in that packages cannot be replicated.). The objective is to deliver the message in minimum time. In this paper we study the Pony Express problem on the line where n robots are arbitrarily deployed along a finite segment. We are interested in both offline centralized and online distributed algorithms. In the online case, we assume the robots have limited knowledge of the initial configuration. In particular, the robots do not know the initial positions and speeds of the other robots nor even their own position and speed. They do, however, know the direction on the line in which to find the message and have the ability to compare speeds when they meet.

SummaryEfforts to describe the diversity of viruses have largely focused on classifying viruses at the species level. However, substantial ecological diversity, both in virulence level and host range, is known within virus species. Here we demonstrate a proof of concept for easily discovering ecological diversity within a virus species taxon. We have focused on the West Nile Virus to take advantage of its broad host range in nature. We produced a genome-based phylogeny of world diversity of WNV and then used Ecotype Simulation 2 to hypothesize demarcation of genomes into 69 putative ecotypes (ecologically distinct populations), based only on clustering of genome sequences. Then we looked for evidence of ecological divergence among ecotypes based on differences in host bird associations within the Connecticut-New York region. Our results indicated significant heterogeneity among ecotypes for their associations with different bird hosts. Ecological diversity within other zoonotic viruses could be easily discovered using this approach. Opportunities for extending this line of research to human associations of virus ecotypes are limited by missing geographic metadata on human samples.

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.

Consider a theatre consisting of $m$ rows each containing $n$ seats. Theatregoers enter the theatre along aisles and pick a row which they enter along one of its two entrances so as to occupy a seat. Assume they select their seats uniformly and independently at random among the empty ones. A row of seats is narrow and an occupant who is already occupying a seat is blocking passage to new incoming theatregoers. As a consequence, occupying a specific seat depends on the courtesy of theatregoers and their willingness to get up so as to create free space that will allow passage to others. Thus, courtesy facilitates and may well increase the overall seat occupancy of the theatre. We say a theatregoer is courteous if (s)he will get up to let others pass. Otherwise, the theatregoer is selfish. A set of theatregoers is $p$-courteous if each theatregoer in the set is courteous with probability $p$, randomly and independently. It is assumed that the behaviour of a theatregoer does not change during the occupancy of the row. In this paper, we are interested in the following question: what is the expected number of occupied seats as a function of the total number of seats in a theatre, $n$, and the probability that a theatregoer is courteous, $p$? We study and analyze interesting variants of this problem reflecting behaviour of the theatregoers as entirely selfish, and $p$-courteous for a row of seats with one or two entrances and as a consequence for a theatre with $m$ rows of seats with multiple aisles. We also consider the case where seats in a row are chosen according to the geometric distribution and the Zipf distibrution (as opposed to the uniform distribution) and provide bounds on the occupancy of a row (and thus the theatre) in each case., Comment: 21 pages, 5 figures. An extended abstract of this paper appears in the Proceedings of Seventh International Conference on Fun with Algorithms, July 1--3, 2014, Lipari Island, Sicily, Italy, Springer LNCS

We consider several variations of the problems of covering a set of barriers (modeled as line segments) using sensors that can detect any intruder crossing any of the barriers. Sensors are initially located in the plane and they can relocate to the barriers. We assume that each sensor can detect any intruder in a circular area of fixed range centered at the sensor. Given a set of barriers and a set of sensors located in the plane, we study three problems: (i) the feasibility of barrier coverage, (ii) the problem of minimizing the largest relocation distance of a sensor (MinMax), and (iii) the problem of minimizing the sum of relocation distances of sensors (MinSum). When sensors are permitted to move to arbitrary positions on the barrier, the MinMax problem is shown to be strongly NP-complete for sensors with arbitrary ranges. We also study the case when sensors are restricted to use perpendicular movement to one of the barriers. We show that when the barriers are parallel, both the MinMax and MinSum problems can be solved in polynomial time. In contrast, we show that even the feasibility problem is strongly NP-complete if two perpendicular barriers are to be covered, even if the sensors are located at integer positions, and have only two possible sensing ranges. On the other hand, we give an O ( n 3 / 2 ) algorithm for a natural special case of this last problem.

We introduce and study a new search-type problem with (\(n+1\))-robots on a disk. The searchers (robots) all start from the center of the disk, have unit speed, and can communicate wirelessly. The goal is for a distinguished robot (the queen) to reach and evacuate from an exit that is hidden on the perimeter of the disk in as little time as possible. The remaining n robots (servants) are there to facilitate the queen’s objective and are not required to reach the hidden exit. We provide upper and lower bounds for the time required to evacuate the queen. Namely, we propose an algorithm specifying the trajectories of the robots which guarantees evacuation of the queen in time always better than \(2 + 4(\sqrt{2}-1) \frac{\pi }{n}\) for \(n \ge 4\) servants. We also demonstrate that for \(n \ge 4\) servants the queen cannot be evacuated in time less than \(2+\frac{\pi }{n}+\frac{2}{n^2}\).

A set of mobile robots (represented as points) is distributed in the Cartesian plane. The collection contains an unknown subset of byzantine robots which are indistinguishable from the reliable ones. The reliable robots need to gather, i.e., arrive to a configuration in which at the same time, all of them occupy the same point on the plane. The robots are equipped with GPS devices and at the beginning of the gathering process they communicate the Cartesian coordinates of their respective positions to the central authority. On the basis of this information, without the knowledge of which robots are faulty, the central authority designs a trajectory for every robot. The central authority aims to provide the trajectories which result in the shortest possible gathering time of the healthy robots. The efficiency of a gathering strategy is measured by its competitive ratio, i.e., the maximal ratio between the time required for gathering achieved by the given trajectories and the optimal time required for gathering in the offline case, i.e., when the faulty robots are known to the central authority in advance. The role of the byzantine robots, controlled by the adversary, is to act so that the gathering is delayed and the resulting competitive ratio is maximized.

Peptide mass spectrometry relies crucially on algorithms that match peptides to spectra. We describe a method to evaluate the accuracy of these algorithms based on the masses of parent proteins before trypsin endoprotease digestion. Measurement of conformance to parent proteins provides a score for comparison of the performances of different algorithms as well as alternative parameter settings for a given algorithm. Tracking of conformance scores for spectrum matches to proteins with progressively lower expression levels revealed that conformance scores are not uniform within data sets but are significantly lower for less abundant proteins. Similarly peptides with lower algorithm peptide-spectrum match scores have lower conformance. Although peptide mass spectrometry data is typically filtered through decoy analysis to ensure a low false discovery rate, this analysis confirms that the filtered data should not be considered as having a uniform confidence. The analysis suggests that use of different algorithms and multiple standardized parameter settings of these algorithms can increase significantly the numbers of peptides identified. This data set can be used as a resource for future algorithm assessment.

To address users' security concerns, cloud service providers must implement strategies that enhance data integrity and privacy. New data auditing and encryption methods open a path toward these goals.

A set of mobile robots (represented as points) is distributed in the Cartesian plane. The collection contains an unknown subset of byzantine robots which are indistinguishable from the reliable ones. The reliable robots need to gather, i.e., arrive to a configuration in which at the same time, all of them occupy the same point on the plane. The robots are equipped with GPS devices and at the beginning of the gathering process they communicate the Cartesian coordinates of their respective positions to the central authority. On the basis of this information, without the knowledge of which robots are faulty, the central authority designs a trajectory for every robot. The central authority aims to provide the trajectories which result in the shortest possible gathering time of the healthy robots. The efficiency of a gathering strategy is measured by its competitive ratio, i.e., the maximal ratio between the time required for gathering achieved by the given trajectories and the optimal time required for gathering in the offline case, i.e., when the faulty robots are known to the central authority in advance. The role of the byzantine robots, controlled by the adversary, is to act so that the gathering is delayed and the resulting competitive ratio is maximized. The objective of our paper is to propose efficient algorithms when the central authority is aware of an upper bound on the number of byzantine robots. We give optimal algorithms for collections of robots known to contain at most one faulty robot. When the proportion of byzantine robots is known to be less than one half or one third, we provide algorithms with small constant competitive ratios. We also propose algorithms with bounded competitive ratio in the case where the proportion of faulty robots is arbitrary., Comment: 14 pages, 6 figures

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.

Assume n wireless mobile sensors are initially dispersed in an ad hoc manner in a rectangular region. They are required to move to final locations so that they can detect any intruder crossing the region in a direction parallel to the sides of the rectangle, and thus provide weak barrier coverage of the region. We study three optimization problems related to the movement of sensors to achieve weak barrier coverage: minimizing the number of sensors moved (MinNum), minimizing the average distance moved by the sensors (MinSum), and minimizing the maximum distance moved by the sensors (MinMax). We give an \(O(n^{3/2})\) time algorithm for the MinNum problem for sensors of diameter 1 that are initially placed at integer positions; in contrast we show that the problem is NP-hard even for sensors of diameter 2 that are initially placed at integer positions. We show that the MinSum problem is solvable in \(O(n \log n)\) time for homogeneous range sensors in arbitrary initial positions for the Manhattan metric, while it is NP-hard for heterogeneous sensor ranges for both Manhattan and Euclidean metrics. Finally, we prove that even very restricted homogeneous versions of the MinMax problem are NP-hard.

Assume n wireless mobile sensors are initially dispersed in an ad hoc manner in a rectangular region. They are required to move to final locations so that they can detect any intruder crossing the region in a direction parallel to the sides of the rectangle, and thus provide weak barrier coverage of the region. We study three optimization problems related to the movement of sensors to achieve weak barrier coverage: minimizing the number of sensors moved (MinNum), minimizing the average distance moved by the sensors (MinSum), and minimizing the maximum distance moved by the sensors (MinMax). We give an O(n^{3/2}) time algorithm for the MinNum problem for sensors of diameter 1 that are initially placed at integer positions; in contrast we show that the problem is NP-hard even for sensors of diameter 2 that are initially placed at integer positions. We show that the MinSum problem is solvable in O(n log n) time for homogeneous range sensors in arbitrary initial positions, while it is NP-hard for heterogeneous sensor ranges. Finally, we prove that even very restricted homogeneous versions of the MinMax problem are NP-hard.

Microbiologists are challenged to explain the origins of enormous numbers of bacterial species worldwide. Contributing to this extreme diversity may be a simpler process of speciation in bacteria than in animals and plants, requiring neither sexual nor geographical isolation between nascent species. Here, we propose and test a novel hypothesis for the extreme diversity of bacterial species-that splitting of one population into multiple ecologically distinct populations (cladogenesis) may be as frequent as adaptive improvements within a single population's lineage (anagenesis). We employed a set of experimental microcosms to address the relative rates of adaptive cladogenesis and anagenesis among the descendants of a Bacillus subtilis clone, in the absence of competing species. Analysis of the evolutionary trajectories of genetic markers indicated that in at least 7 of 10 replicate microcosm communities, the original population founded one or more new, ecologically distinct populations (ecotypes) before a single anagenetic event occurred within the original population. We were able to support this inference by identifying putative ecotypes formed in these communities through differences in genetic marker association, colony morphology and microhabitat association; we then confirmed the ecological distinctness of these putative ecotypes in competition experiments. Adaptive mutations leading to new ecotypes appeared to be about as common as those improving fitness within an existing ecotype. These results suggest near parity of anagenesis and cladogenesis rates in natural populations that are depauperate of bacterial diversity.

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 {\em 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., 14 pages

We consider \textsc{Persistence}, a new online problem concerning optimizing weighted observations in a stream of data when the observer has limited buffer capacity. A stream of weighted items arrive one at a time at the entrance of a buffer with two holding locations. A processor (or observer) can process (observe) an item at the buffer location it chooses, deriving this way the weight of the observed item as profit. The main constraint is that the processor can only move {\em synchronously} with the item stream; as a result, moving from the end of the buffer to the entrance, it crosses paths with the item already there, and will never have the chance to process or even identify it. \textsc{Persistence}\ is the online problem of scheduling the processor movements through the buffer so that its total derived value is maximized under this constraint. We study the performance of the straight-forward heuristic {\em Threshold}, i.e., forcing the processor to "follow" an item through the whole buffer only if its value is above a threshold. We analyze both the optimal offline and Threshold algorithms in case the input stream is a random permutation, or its items are iid valued. We show that in both cases the competitive ratio achieved by the Threshold algorithm is at least $2/3$ when the only statistical knowledge of the items is the median of all possible values. We generalize our results by showing that Threshold, equipped with some minimal statistical advice about the input, achieves competitive ratios in the whole spectrum between $2/3$ and $1$, following the variation of a newly defined density-like measure of the input. This result is a significant improvement over the case of arbitrary input streams, since in this case we show that no online algorithm can achieve a competitive ratio better than $1/2$., 17 pages, 1 figure

Tor is currently one of the more popular systems for anonymizing near real-time communications on the Internet. Recently, Borisov et al. proposed a denial of service based attack on Tor (and related systems) that significantly increases the probability of compromising the anonymity provided. In this paper, we analyze the effectiveness of the attack using both an analytic model and simulation. We also describe two algorithms for detecting such attacks, one deterministic and proved correct, the other probabilistic and verified in simulation., Comment: Author-prepared journal version

We present a trade-off between the expected time for two identical agents to rendezvous on a synchronous, anonymous, oriented ring and the memory requirements of the agents. In particular, we show there exists a 2 t state agent which can achieve rendezvous on an n -node ring in expected time O ( n 2 /2 t + 2 t ) and that any t /2 state agent requires expected time Ω( n 2 /2 t ). As a corollary we observe that Θ(log log n ) bits of memory are necessary and sufficient to achieve rendezvous in linear time.

Consider a situation where people have to choose among a sequence of n linearly ordered positions to perform some task requiring a certain amount of privacy. Which position should one choose so as to maximize one's privacy, i.e., minimize the chances that one of your neighboring positions becomes occupied by a later arrival? In this paper, we attempt to answer this question under a variety of models for the behavior of the later arrivals. Our results suggest that for the most part one should probably choose one of the extreme positions (with some interesting exceptions). We also suggest a number of variations on the problem that lead to many open problems.

In the rendezvous problem, the goal for two mobile agents is to meet whenever this is possible. In the rendezvous with detection problem, an additional goal for the agents is to detect the impossibility of a rendezvous (e.g., due to symmetrical initial positions of the agents) and stop. We consider the rendezvous problem with and without detection for identical anonymous mobile agents (i.e., running the same deterministic algorithm) with tokens in an anonymous synchronous torus with a sense of direction, and show that there is a striking computational difference between one and more tokens. Specifically, we show that (1) two agents with a constant number of unmovable tokens, or with one movable token each, cannot rendezvous in an n×n torus if they have o(logn) memory, while they can solve the rendezvous with detection problem in an n×m torus as long as they have one unmovable token and O(logn+logm) memory; in contrast, (2) when two agents have two movable tokens each then the rendezvous problem (respectively, rendezvous with detection problem) is solvable with constant memory in an arbitrary n×m (respectively, n×n) torus; and finally, (3) two agents with three movable tokens each and constant memory can solve the rendezvous with detection problem in an n×m torus. This is the first publication in the literature that studies tradeoffs between the number of tokens, memory and knowledge the agents need in order to meet in a torus.

The humanitarian focus of socially useful projects promises to motivate community-minded undergrads in and out of CS.

Motivated by computer experiments, we study asymptotics of the expected maximum number of base pairs in secondary structures for random RNA sequences of length n. After proving a general limit result, we provide estimates of the limit for the binary alphabet {G,C} with thresholds k⩾0. We prove a general theorem entailing the existence of an asymptotic limit for the mean and standard deviation of free energy per nucleotide, as computed by mfold, for random RNA of any fixed compositional frequency; higher order moment limits are additionally shown to exist.

A team of k mobile robots is deployed on a weighted graph whose edge weights represent distances. The robots move perpetually along the domain, represented by all points belonging to the graph edges, without exceeding their maximum speed. The robots need to patrol the graph by regularly visiting all points of the domain. In this paper, we consider a team of robots (patrolmen), at most f of which may be unreliable, i.e., they fail to comply with their patrolling duties. What algorithm should be followed so as to minimize the maximum time between successive visits of every edge point by a reliable patrolman? The corresponding measure of efficiency of patrolling called idleness has been widely accepted in the robotics literature. We extend it to the case of untrusted patrolmen; we denote by $${\mathfrak {I}}_k^f (G)$$ the maximum time that a point of the domain may remain unvisited by reliable patrolmen. The objective is to find patrolling strategies minimizing $${\mathfrak {I}}_k^f (G)$$ . We investigate this problem for various classes of graphs. We design optimal algorithms for line segments, which turn out to be surprisingly different from strategies for related patrolling problems proposed in the literature. We then use these results to study general graphs. For Eulerian graphs G, we give an optimal patrolling strategy with idleness $${\mathfrak {I}}^f_k(G) = (f+1) |E|{/}k$$ , where |E| is the sum of the lengths of the edges of G. Further, we show the hardness of the problem of computing the idle time for three robots, at most one of which is faulty, by reduction from 3-edge-coloring of cubic graphs—a known NP-hard problem. A byproduct of our proof is the investigation of classes of graphs minimizing idle time (with respect to the total length of edges); an example of such a class is known in the literature under the name of Kotzig graphs.

In this paper, we present a reservation-based medium access control (MAC) protocol with multicast support for wavelength-division multiplexing networks. Our system is based on the single-hop, passive optical star architecture. Of the available wavelengths (channels), one channel is designated as a control channel, and the remaining channels are used for data transmission. Each node is equipped with a pair of fixed transceiver to access the control channel, and a fixed transmitter and a tunable receiver to access data channels. For easy implementation of the protocol in hardware and for precisely computing the protocol's processing overhead, we give a register-transfer model of the protocol. We simulate the protocol to study its throughput behavior, and present its analytic model. For a node to be able to send data packets in successive data slots with no time gap between them, in spite of the situation that the protocol's execution time may be longer than data transmission time, we propose the idea of multiple MAC units at each node. Unicast throughput of our protocol reaches the theoretically possible maximum throughput for MAC protocols with distributed control, and the multicast throughput is at least as good as, and even better than, those delivered by existing MAC protocols with distributed control.

We present deterministic algorithms to search for an item s contained in a node of a network, without prior knowledge of its exact location. Each node of the network has a database that will answer queries of the form “how do I get to s ?” by responding with the first edge on a shortest path to the node containing s . It may happen that some nodes, called liars , give bad advice. If the number of liars k is bounded, we show different strategies to find the item depending on the topology of the network. In particular we consider the complete graph, ring, torus, hypercube and bounded degree trees.

In an anonymous ring of n processors, all processors are totally indistinguishable except for their input values. These values are not necessarily distinct, i.e., they form a multiset, and this makes many problems particularly difficult. We consider the problem of distributively sorting such a multiset on the ring, and we give a complete characterization of the relationship with the problems of leader election for vertices and edges. For Boolean input values and prime n, we also establish a lower bound, and a reasonably close upper bound on the message complexity valid for sorting and leader election.

In order to detect intruders that attempt to pass through a rectangular domain, sensors are placed at nodes of a regular spaced grid laid out over the rectangle. An intruder that steps within the sensing range of a sensor will be detected. It is desired that we prevent potential attacks in either one dimension or two dimensions. A one-dimensional attack succeeds when an intruder enters from the top North side and exits out the bottom South side of the domain without being detected. Preventing attacks in two dimensions requires that we simultaneously prevent the intruder from either entering North and exiting South or entering East left side and exiting West right side undetected. Initially, all of the sensors are working properly and the domain is fully protected, i.e., attacks will be detected, in both dimensions assuming the grid points are such that neighboring sensors have overlapping sensing ranges and include all four boundaries of the domain. Over time, the sensors may fail and we are left with a subset of working sensors. Under these conditions we wish to 1 determine if one or two-dimensional attack detection still persists and 2 if not, restore protection by adding the least number of sensors required to ensure detection in either one or two dimensions. Ideally, the set of currently working sensors would provide some amount of fault-tolerance. In particular, it would be advantageous if for a given k, the set of sensors maintains protection in one or two dimensions even if upi¾źto k of the sensors fail. This leads to the problems of 1 deciding if a subset of the sensors provides protection with upi¾źto k faults and 2 if not, finding the minimum number of grid points to add sensors to in order to achieve k fault-tolerance. In this paper, we provide algorithms for deciding if a set sensors provides k-fault tolerant protection against attacks in both one and two dimensions, for optimally restoring k-fault tolerant protection in one dimension and for restoring protection in two dimensions optimally for $$k=0$$ and approximately otherwise.

Cooperation between mobile robots and wireless sensor networks is a line of research that is currently attracting a lot of attention. In this context, we study the following problem of barrier coverage by stationary wireless sensors that are assisted by a mobile robot with the capacity to move sensors. Assume that \(n\) sensors are initially arbitrarily distributed on a line segment barrier. Each sensor is said to cover the portion of the barrier that intersects with its sensing area. Owing to incorrect initial position, or the death of some of the sensors, the barrier is not completely covered by the sensors. We employ a mobile robot to move the sensors to final positions on the barrier such that barrier coverage is guaranteed. We seek algorithms that minimize the length of the robot’s trajectory, since this allows the restoration of barrier coverage as soon as possible. We give an optimal linear-time offline algorithm that gives a minimum-length trajectory for a robot that starts at one end of the barrier and achieves the restoration of barrier coverage. We also study two different online models: one in which the online robot does not know the length of the barrier in advance, and the other in which the online robot knows it in advance. For the case when the online robot does not know the length of the barrier, we prove a tight bound of \(3/2\) on the competitive ratio, and we give a tight lower bound of \(5/4\) on the competitive ratio in the other case. Thus for each case we give an optimal online algorithm.

In wireless communication, the signal of a typical broadcast station is transmitted from a broadcast center p and reaches objects at a distance, say, r from it. In addition there is a radius r0, r0 < r, such that the signal originating from the center of the station is so strong that human habitation within distance r0 from the center p should be avoided. In other words, points within distance r0 from the station comprise a hazardous zone. We consider the following station layout proble: Cover a given planar region that includes a collection of buildings with a minimum number of stations so that every point in the region is within the reach of a station, while at the same time no interior point of any building is within the hazardous zone of a station. We give algorithms for computing such station layouts in both the one- and two-dimensional cases.

Cooperation between mobile robots and wireless sensor networks is a line of research that is currently attracting a lot of attention. In this context, we study the following problem of barrier coverage by stationary wireless sensors that are assisted by a mobile robot with the capacity to move sensors. Assume that $n$ sensors are initially arbitrarily distributed on a line segment barrier. Each sensor is said to cover the portion of the barrier that intersects with its sensing area. Owing to incorrect initial position, or the death of some of the sensors, the barrier is not completely covered by the sensors. We employ a mobile robot to move the sensors to final positions on the barrier such that barrier coverage is guaranteed. We seek algorithms that minimize the length of the robot's trajectory, since this allows the restoration of barrier coverage as soon as possible. We give an optimal linear-time offline algorithm that gives a minimum-length trajectory for a robot that starts at one end of the barrier and achieves the restoration of barrier coverage. We also study two different online models: one in which the online robot does not know the length of the barrier in advance, and the other in which the online robot knows the length of the barrier. For the case when the online robot does not know the length of the barrier, we prove a tight bound of $3/2$ on the competitive ratio, and we give a tight lower bound of $5/4$ on the competitive ratio in the other case. Thus for each case we give an optimal online algorithm., 20 pages

In recent years there has been significant interest in the study of random k-SAT formulae. For a given set of n Boolean variables, let Bk denote the set of all possible disjunctions of k distinct, non-complementary literals from its variables (k-clauses). A random k-SAT formula Fk (n;m) is formed by selectinguniformly and independently m clauses from Bk and takingtheir conjunction. Motivated by insights from statistical mechanics that suggest a possible relationship between the "order" of phase transitions and computational complexity, Monasson and Zecchina (Phys. Rev. E 56(2) (1997) 1357) proposed the random (2+p)-SAT model: for a given p . [0; 1], a random (2 + p)-SAT formula, F2+p(n;m), has m randomly chosen clauses over n variables, where pm clauses are chosen from B3 and (1 - p)m from B2. Usingthe heuristic "replica method" of statistical mechanics, Monasson and Zecchina gave a number of non-rigorous predictions on the behavior of random (2 + p)-SAT formulae. In this paper we give the 1rst rigorous results for random (2 + p)-SAT, including the following surprising fact: for p ≤ 2/5, with probability 1 - o(1), a random (2 + p)-SAT formula is satisfiable if its 2-SAT subformula is satisfiable. That is, for p 6 2=5, random (2 + p)-SAT behaves like random 2-SAT.

Consider a set X of n-points in space, each with positive z-coordinate, and a compact plane convex set S. We define a graph G(X,S), called the ray-shooting graph, on X as follows: The points of X are the vertices and {p i ,p j }, p i ,p j ∈X , is an edge if and only if the infinite line joining pi to pj intersects S. In this paper we provide a characterization of shooting graphs; they are exactly the set of comparability graphs of containment orders arising from families of plane homothetic convex sets. We also prove that the crossing number of these ordered sets is at most 2, and that not all comparability graphs are three-dimensional ray-shooting graphs.

In the last few years there has been a great amount of interest in Random Constraint Satisfaction Problems, both from an experimental and a theoretical point of view. Quite intriguingly, experimental results with various models for generating random CSP instances suggest that the probability of such problems having a solution exhibits a “threshold-like” behavior. In this spirit, some preliminary theoretical work has been done in analyzing these models asymptotically, i.e., as the number of variables grows. In this paper we prove that, contrary to beliefs based on experimental evidence, the models commonly used for generating random CSP instances i>do not have an asymptotic threshold. In particular, we prove that asymptotically i>almost all instances they generate are overconstrained, suffering from trivial, local inconsistencies. To complement this result we present an alternative, single-parameter model for generating random CSP instances and prove that, unlike current models, it exhibits non-trivial asymptotic behavior. Moreover, for this new model we derive explicit bounds for the narrow region within which the probability of having a solution changes dramatically.

A function is distributed among nodes of a graph in a “continuous” (or “slowly changing”) way, i.e., such that the difference between values stored at adjacent nodes is small. The goal is to find a node of maximum value by probing some nodes under a restricted budget. Every node has an associated cost which has to be paid for probing it and a probe reveals the value of the node. If the total budget is too small to allow probing every node, it is impossible to find the maximum value in the worst case. Hence we seek an Approximate Maxima Finding (AMF) algorithm that offers the best worst-case guarantee g , i.e., for any continuous distribution of values it finds a node whose value differs from the maximum value by at most g . AMF in graphs is related to a generalization of the multicenter problem and we get new results for this problem as well. For example, we give a polynomial algorithm to find a minimum cost solution for the multicenter problem on a tree, with arbitrary node costs. — Authors' Abstract

Consider a theatre consisting of m rows each containing n seats. Theatregoers enter the theatre along aisles and pick a row which they enter along one of its two entrances so as to occupy a seat. Assume they select their seats uniformly and independently at random among the empty ones. A row of seats is narrow and an occupant who is already occupying a seat is blocking passage to new incoming theatregoers. As a consequence, occupying a specific seat depends on the courtesy of theatregoers and their willingness to get up so as to create free space that will allow passage to others. Thus, courtesy facilitates and may well increase the overall seat occupancy of the theatre. We say a theatregoer is courteous if (s)he will get up to let others pass. Otherwise, the theatregoer is selfish. A set of theatregoers is courteous with probability p (or p-courteous, for short) if each theatregoer in the set is courteous with probability p, randomly and independently. It is assumed that the behaviour of a theatregoer does not change during the occupancy of the row. Thus, p = 1 represents the case where all theatregoers are courteous and p = 0 when they are all selfish.

We consider the Dynamic Map Visitation Problem (DMVP), in which a team of agents must visit a collection of critical locations as quickly as possible, in an environment that may change rapidly and unpredictably during the agents’ navigation. We apply recent formulations of time-varying graphs (TVGs) to DMVP, shedding new light on the computational hierarchy \(\mathcal {R} \supset \mathcal {B} \supset \mathcal {P}\) of TVG classes by analyzing them in the context of graph navigation. We provide hardness results for all three classes, and for several restricted topologies, we show a separation between the classes by showing severe inapproximability in \(\mathcal {R}\), limited approximability in \(\mathcal {B}\), and tractability in \(\mathcal {P}\). We also give topologies in which DMVP in \(\mathcal {R}\) is fixed parameter tractable, which may serve as a first step toward fully characterizing the features that make DMVP difficult.

We consider combinatorial and algorithmic aspects of the well-known paradigm “killing two birds with one stone”. We define a stage graph as follows: vertices are points from a planar point set, and {u, v} is an edge if and only if the (infinite, straight) line segment joining u to v intersects a given line segment, called a stage. We show that a graph is a stage graph if and only if it is a permutation graph. The characterization results in a compact linear space representation of stage graphs. This has been exploited for designing improved algorithms for maximum matching in permutation graphs, two processor task scheduling for dependency graphs known to be permutation graphs, and dominance-related problems for planar point sets. We show that a maximum matching in permutation graphs can be computed in Ω(n log2 n) time, where n is the number of vertices. We provide simple optimal sequential and parallel algorithms for several dominance related problems for planar point sets.

International audience; A set of mobile robots is deployed on a simple curve of finite length, composed of a finite set of vital segments separated by neutral segments. The robots have to patrol the vital segments by perpetually moving on the curve, without exceeding their maximum speed. The quality of patrolling is measured by the idleness, i.e., the longest time period during which any vital point on the curve is not visited by any robot. Given a configuration of vital segments, our goal is to provide algorithms describing the movement of the robots along the curve so as to minimize the idleness. Our main contribution is a proof that the optimal solution to the patrolling problem is attained either by the cyclic strategy, in which all the robots move in one direction around the curve, or by the partition strategy, in which the curve is partitioned into sections which are patrolled separately by individual robots. These two fundamental types of strategies were studied in the past in the robotics community in different theoretical and experimental settings. However, to our knowledge, this is the first theoretical analysis proving optimality in such a general scenario. Throughout the paper we assume that all robots have the same maximum speed. In fact, the claim is known to be invalid when this assumption does not hold, cf. [Czyzowicz et al., Proc. ESA 2011].

We consider labelings (i.e. assignments of labels to the links that give the network a globally consistent orientation) on anonymous Cayley networks NG constructed from a set G of generators of a group G. Such networks can be endowed with a natural labeling LG to form the oriented Cayley network, denoted by NG[LG]. We show that in general oriented Cayley networks are more powerful than unoriented Cayley networks, in the sense that the former can compute more Boolean functions than the latter. We also give a characterization of those Abelian groups G which have a canonical set of generators G such that the network NG computes more Boolean functions than the network NG[LG].

Comprehensive knowledge of proteome complexity is crucial to understanding cell function. Amino termini of yeast proteins were identified through peptide mass spectrometry on glutaraldehyde-treated cell lysates as well as a parallel assessment of publicly deposited spectra. An unexpectedly large fraction of detected amino-terminal peptides (35%) mapped to translation initiation at AUG codons downstream of the annotated start codon. Many of the implicated genes have suboptimal sequence contexts for translation initiation near their annotated AUG, and their ribosome profiles show elevated tag densities consistent with translation initiation at downstream AUGs as well as their annotated AUGs. These data suggest that a significant fraction of the yeast proteome derives from initiation at downstream AUGs, increasing significantly the repertoire of encoded proteins and their potential functions and cellular localizations.

Given a set P of n points in the plane, we solve the problems of constructing a geometric planar graph spanning P 1) of minimum degree 2, and 2) which is 2-edge connected, respectively, and has max edge length bounded by a factor of 2 times the optimal; we also show that the factor 2 is best possible given appropriate connectivity conditions on the set P, respectively. First, we construct in O(nlogn) time a geometric planar graph of minimum degree 2 and max edge length bounded by 2 times the optimal. This is then used to construct in O(nlogn) time a 2-edge connected geometric planar graph spanning P with max edge length bounded by √5 times the optimal, assuming that the set P forms a connected Unit Disk Graph. Second, we prove that 2 times the optimal is always sufficient if the set of points forms a 2 edge connected Unit Disk Graph and give an algorithm that runs in O(n2) time. We also show that for k ∈ O(√n), there exists a set P of n points in the plane such that even though the Unit Disk Graph spanning P is k-vertex connected, there is no 2-edge connected geometric planar graph spanning P even if the length of its edges is allowed to be up to 17/16.