Search

Mobile sensors are located on a barrier represented by a line segment. Each sensor has a single energy source that can be used for both moving and sensing. A sensor consumes energy in movement in proportion to distance traveled, and it expends energy per time unit for sensing in direct proportion to its radius raised to a constant exponent. We address the problem of energy efficient coverage. The input consists of the initial locations of the sensors and a coverage time requirement t. A feasible solution consists of an assignment of destinations and coverage radii to all sensors such that the barrier is covered. We consider two variants of the problem that are distinguished by whether the radii are given as part of the input. In the fixed radii case, we are also given a radii vector ρ, and the radii assignment r must satisfy r i ∈ { 0 , ρ i } , for every i, while in the variable radii case the radii assignment is unrestricted. The goal is to cover the barrier for t time in an energy efficient manner. More specifically, we consider two objective functions. In the first the goal is to minimize the sum of the energy spent by all sensors and in the second the goal is to minimize the maximum energy used by any sensor. We present fully polynomial time approximation schemes for the problem of minimizing the energy sum with variable radii and for the problem of minimizing the maximum energy with variable radii. We also show that the latter can be approximated within any additive constant e > 0 . We present a 2-approximation algorithm for the problem of minimizing the maximum energy with fixed radii which also is shown to be strongly NP-hard. We show that the problem of minimizing the energy sum with fixed radii cannot be approximated within a factor of O ( n c ) , for any constant c, unless P = NP. Additional results are given for three special cases: (i) sensors are stationary, (ii) free movement, and (iii) uniform fixed radii.

We study two problems where k autonomous mobile agents are initially located on distinct nodes of a weighted graph with n nodes and m edges. Each agent has a predefined velocity and can only move along the edges of the graph. The first problem is to deliver one package from a source node to a destination node. The second is to simultaneously deliver two packages, each from its source node to its destination node. These deliveries are achieved by the collective effort of the agents, which can carry and exchange a package among them. For one package, we propose an O ( k n log ⁡ n + k m ) time algorithm for computing a delivery schedule that minimizes the delivery time. For two packages, we show that the problem of minimizing the maximum or the sum of the delivery times is NP-hard for arbitrary agent velocities, but polynomial-time solvable for agents with equal velocity.

Considering the model of computing under uncertainty where element weights are uncertain but can be obtained at a cost by query operations, we study the problem of identifying a cheapest (minimum-weight) set among a given collection of feasible sets using a minimum number of queries of element weights. For the general case we present an algorithm that makes at most d ? OPT + d queries, where d is the maximum cardinality of any given set and OPT is the optimal number of queries needed to identify a cheapest set. For the minimum multi-cut problem in trees with d terminal pairs, we give an algorithm that makes at most d ? OPT + 1 queries. For the problem of computing a minimum-weight base of a given matroid, we give an algorithm that makes at most 2 ? OPT queries, generalizing a known result for the minimum spanning tree problem. For each of the above algorithms we give matching lower bounds. We also settle the complexity of the verification version of the general cheapest set problem and the minimum multi-cut problem in trees under uncertainty.

We study the problem of maximising the lifetime of a sensor network for fault-tolerant target coverage in a setting with composite events. Here, a composite event is the simultaneous occurrence of a combination of atomic events, such as the detection of smoke and high temperature. We are given sensor nodes that have an initial battery level and can monitor certain event types, and a set of points at which composite events need to be detected. The points and sensor nodes are located in the Euclidean plane, and all nodes have the same sensing radius. The goal is to compute a longest activity schedule with the property that at any point in time, each event point is monitored by at least two active sensor nodes. We present a (6+e)-approximation algorithm for this problem by devising an approximation algorithm with the same ratio for the dual problem of minimising the weight of a fault-tolerant sensor cover and applying the Garg-Konemann algorithm. Our algorithm for the minimum-weight fault-tolerant sensor cover problem generalises previous approximation algorithms for geometric set cover with weighted unit disks and is obtained by enumerating properties of the optimal solution that guide a dynamic programming approach.

Given a set of connection requests (calls) in a communication network, the call control problem is to accept a subset of the requests and route them along paths in the network such that no edge capacity is violated, with the goal of rejecting as few requests as possible. We investigate the complexity of parameterized versions of this problem, where the number of rejected requests is taken as the parameter. For the variant with pre-determined paths, the problem is fixed-parameter tractable in arbitrary graphs if the link capacities are bounded by a constant, but W[2]-hard if the link capacities are arbitrary. If the paths are not pre-determined, no FPT algorithm can exist even in series–parallel graphs unless P=NP. Our main results are new FPT algorithms for call control in tree networks with arbitrary edge capacities and in trees of rings with unit edge capacities in the case that the paths are not pre-determined.

Given a set of jobs, each consisting of a number of weighted intervals on the real line, and a positive integer m, we study the problem of selecting a maximum weight subset of the intervals such that at most one interval is selected from each job and, for any point p on the real line, at most m intervals containing p are selected. We give a parameterized algorithm GREEDYα that belongs to the class of "myopic" algorithms, which are deterministic algorithms that process the given intervals in order of non-decreasing right endpoint and can either reject or select each interval (rejections are irrevocable). We show that there are values of the parameter α so that GREEDYα produces a 2-approximation in the case of unit weights, an 8-approximation in the case of arbitrary weights, and a (3 + 2√2)- approximation in the case where the weights of all intervals corresponding to the same job are equal. We also show that no deterministic myopic algorithm can achieve ratio better than 2 in the case of unit weights, better than ≈ 7.103 in the case of arbitrary weights, and better than 3 + 2√2 in the case where the weights of all intervals corresponding to the same job are equal. Furthermore, we give additional results for the case where all intervals have the same length as well as a lower bound of e/e-1≈ 1.582 on the approximation ratio of randomized myopic algorithms in the case of unit weights.

This paper studies on-line coloring of geometric intersection graphs. It is shown that no deterministic on-line algorithm can achieve competitive ratio better than Ω(logn) for disk graphs and for square graphs with n vertices, even if the geometric representation is given as part of the input. Furthermore, it is proved that the standard First-fit heuristic achieves competitive ratio O(logn) for disk graphs and for square graphs and is thus best possible.

A pattern is a finite string of constant and variable symbols. The language generated by a pattern is the set of all strings of constant symbols which can be obtained from the pattern by substituting non-empty strings for variables. We study the learnability of one-variable pattern languages in the limit with respect to the update time needed for computing a new single hypothesis and the expected total learning time taken until convergence to a correct hypothesis. Our results are as follows. First, we design a consistent and set-driven learner that, using the concept of descriptive patterns, achieves update time O(n2logn), where n is the size of the input sample. The best previously known algorithm for computing descriptive one-variable patterns requires time O(n4logn) (cf. Angluin, J. Comput. Systems Sci. 21(1) (1980) 46–62). Second, we give a parallel version of this algorithm that requires time O(logn) and O(n3/logn) processors on an EREW-PRAM. Third, using a modified version of the sequential algorithm as a subroutine, we devise a learning algorithm for one-variable patterns whose expected total learning time is O(ℓ2logℓ) provided the sample strings are drawn from the target language according to a probability distribution with expected string length ℓ. The probability distribution must be such that strings of equal length have equal probability, but can be arbitrary otherwise. Thus, we establish the first algorithm for learning one-variable pattern languages having an expected total learning time that provably differs from the update time by a constant factor only. Finally, we show how the algorithm for descriptive one-variable patterns can be used for learning one-variable patterns with a polynomial number of superset queries with respect to the one-variable patterns as query language.

Parallel load balancing is studied for problems with certain bisection properties. A class of problems has /spl alpha/-bisectors if every problem p of weight w(p) in the class can be subdivided into two subproblems whose weight (load) is at least an a-fraction of the original problem. A problem p is to be split into N subproblems such that the maximum weight among them is as close to w(p)/N as possible. It was previously known that good load balancing can be achieved for such classes of problems using Algorithm HF, a sequential algorithm that repeatedly bisects the subproblem with maximum weight. Several parallel variants of Algorithm HF are introduced and analyzed with respect to worst-case load imbalance, running-time, and communication overhead. For fixed /spl alpha/, all variants have running-time O(log N) and provide constant upper bounds on the worst-case load imbalance. Results of simulation experiments regarding the load balance achieved in the average case are presented.

We present a polynomial-time greedy algorithm that assigns proper wavelengths to a set of requests of maximum load L per directed fiber link on a directed fiber tree using at most 5/3 L wavelengths. This improves previous results of Raghavan and Upfal (Proc. Ann. ACM Symp. on theory of computing STOC, 1994, pp. 134–143), Mihail et al. (Proc. 36th IEEE Symp. on Foundations of Computer Science, 1995, pp. 548–557), Kaklamanis and Persiano (Proc. Algorithms — ESA 96, Lecture Notes in Computer Science, 1136, pp. 460–470), Kumar and Schwabe (Proc. 8th Ann. ACM-SIAM Symp. on Discrete Algorithms SODA, 1997, pp. 437–444). We also prove that no greedy algorithm can in general use less than 5/3 L wavelengths for a set of requests of load L in a directed fiber tree, and thus our algorithm is optimal in the class of greedy algorithms which includes the algorithms presented in [8–10, 12].

The topology of the Internet has initially been modelled as an undirected graph, where vertices correspond to so-called Autonomous Systems (ASs), and edges correspond to physical links between pairs of ASs. However, in order to capture the impact of routing policies, it has recently become apparent that one needs to classify the edges according to the existing economic relationships (customer-provider, peer-to-peer or siblings) between the ASs. This leads to a directed graph model in which traffic can be sent only along so-called valley-free paths. Four different algorithms have been proposed in the literature for inferring AS relationships using publicly available data from routing tables. We investigate the differences in the graph models produced by these algorithms, focussing on connectivity measures. To this aim, we compute the maximum number of vertex-disjoint valley-free paths between ASs as well as the size of a minimum cut separating a pair of ASs. Although these problems are solvable in polynomial time for ordinary graphs, they are NP-hard in our setting. We formulate the two problems as integer programs, and we propose a number of exact algorithms for solving them. For the problem of finding the maximum number of vertex-disjoint paths, we discuss two algorithms; the first one is a branch-and-price algorithm based on the IP formulation, and the second algorithm is a non LP based branch-and-bound algorithm. For the problem of finding minimum cuts we use a branch-and-cut algorithm, based on the IP formulation of this problem. Using these algorithms, we obtain exact solutions for both problems in reasonable time. It turns out that there is a large gap in terms of the connectivity measures between the undirected and directed models. This nding supports our conclusion that economic relationships need to be taken into account when building a topology of the Internet.