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.

For t > 0 and g = 0, a vertex-weighted graph of total weight W is (t, g)-trimmable if it contains a vertex-induced subgraph of total weight at least (1-1/t)W and with no simple path of more than g edges. A family of graphs is trimmable if for every constant t > 0, there is a constant g = 0 such that every vertex-weighted graph in the family is (t, g)-trimmable. We show that every family of graphs of bounded domino treewidth is trimmable. This implies that every family of graphs of bounded degree is trimmable if the graphs in the family have bounded treewidth or are planar. We also show that every family of directed graphs of bounded layer bandwidth (a less restrictive condition than bounded directed bandwidth) is trimmable. As an application of these results, we derive polynomial-time approximation schemes for various forms of the problem of labeling a subset of given weighted point features with nonoverlapping sliding axes-parallel rectangular labels so as to maximize the total weight of the labeled features, provided that the ratios of label heights or the ratios of label lengths are bounded by a constant. This settles one of the last major open questions in the theory of map labeling. Keywords: Trimming weighted graphs - Domino treewidth - Planar graphs - Layer bandwidth - Point-feature label placement - Map labeling - Sliding labels - Polynomial-time approximation schemes.

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.

The original version of the article was inadvertently published with misinterpretations on author’s proof corrections on mathematical expressions.

Graph coloring has been studied extensively in the literature. The classical problem concerns the number of colors used. In this paper, we focus on coloring intervals where the input is a set of intervals and two overlapping intervals cannot be assigned the same color. In particular, we are interested in the setting where there is an increasing cost associated with using a higher color index. Given a set of intervals (on a line) and a coloring, the cost of the coloring at any point is the cost of the maximum color index used at that point and the cost of the overall coloring is the integral of the cost over all points on the line. The objective is to assign a valid color to each interval and minimize the total cost of the coloring. Intuitively, the maximum color index used at each point forms a skyline and so the objective is to obtain a minimum skyline coloring. The problem arises in various applications including optical networks and job scheduling.

In this paper we consider non-preemptive online scheduling of jobs with release times and deadlines on heterogeneous processors with speed scaling. The power needed by processor i to run at speed s is assumed to be \(s^{\alpha _i}\), where the exponent \(\alpha _i\) is a constant that can be different for each processor. We require the jobs to have agreeable deadlines, i.e., jobs with later release times also have later deadlines. The aim is to minimize the energy used to complete all jobs by their deadlines. For the case where the densities of the jobs differ only within a factor of two and the same holds for their interval lengths, we present an algorithm with constant competitive ratio. For arbitrary densities and interval lengths, we achieve a competitive ratio that is poly-logarithmic in the ratio of maximum to minimum density and in the ratio of maximum to minimum interval length.

We investigate the problem of computing the types of the relationships between Internet Autonomous Systems. We refer to the model introduced by Gao [IEEE/ACM TRANSACTIONS ON NETWORKING, 9(6):733–645, 2001] and Subramanian et al. (IEEE Infocom, 2002) that bases the discovery of such relationships on the analysis of the AS paths extracted from the BGP routing tables. We characterize the time complexity of the above problem, showing both NP-completeness results and efficient algorithms for solving specific cases. Motivated by the hardness of the general problem, we propose approximation algorithms and heuristics based on a novel paradigm and show their effectiveness against publicly available data sets. The experiments provide evidence that our algorithms perform significantly better than state-of-the-art heuristics.

Harmful Internet hijacking incidents put in evidence how fragile the Border Gateway Protocol (BGP) is, which is used to exchange routing information between Autonomous Systems (ASes). As proved by recent research contributions, even S-BGP, the secure variant of BGP that is being deployed, is not fully able to blunt traffic attraction attacks. Given a traffic flow between two ASes, we study how difficult it is for a malicious AS to devise a strategy for hijacking or intercepting that flow. We show that this problem marks a sharp difference between BGP and S-BGP. Namely, while it is solvable, under reasonable assumptions, in polynomial time for the type of attacks that are usually performed in BGP, it is NP-hard for S-BGP. Our study has several by-products. E.g., we solve a problem left open in the literature, stating when performing a hijacking in S-BGP is equivalent to performing an interception., Comment: 17 pages with 6 figures

Classical measures of network connectivity are the number of disjoint paths between a pair of nodes and the size of a minimum cut. For standard graphs, these measures can be computed efficiently using network flow techniques. However, in the Internet on the level of autonomous systems (ASs), referred to as AS-level Internet, routing policies impose restrictions on the paths that traffic can take in the network. These restrictions can be captured by the valley-free path model, which assumes a special directed graph model in which edge types represent relationships between ASs. We consider the adaptation of the classical connectivity measures to the valley-free path model, where it is 𝒩𝒫-hard to compute them. Our first main contribution consists of presenting algorithms for the computation of disjoint paths, and minimum cuts, in the valley-free path model. These algorithms are useful for ASs that want to evaluate different options for selecting upstream providers to improve the robustness of their connection to the Internet. Our second main contribution is an experimental evaluation of our algorithms on four types of directed graph models of the AS-level Internet produced by different inference algorithms. Most importantly, the evaluation shows that our algorithms are able to compute optimal solutions to instances of realistic size of the connectivity problems in the valley-free path model in reasonable time. Furthermore, our experimental results provide information about the characteristics of the directed graph models of the AS-level Internet produced by different inference algorithms. It turns out that (i) we can quantify the difference between the undirected AS-level topology and the directed graph models with respect to fundamental connectivity measures, and (ii) the different inference algorithms yield topologies that are similar with respect to connectivity and are different with respect to the types of paths that exist between pairs of ASs.

Consider the problem of discovering (or verifying) the edges and non-edges of a network, modelled as a connected undirected graph, using a minimum number of queries. A query at a vertex v discovers (or verifies) all edges and non-edges whose endpoints have different distance from v. In the network discovery problem, the edges and non-edges are initially unknown, and the algorithm must select the next query based only on the results of previous queries. We study the problem using competitive analysis and give a randomized on-line algorithm with competitive ratio O(sqrt(n*log n)) for graphs with n vertices. We also show that no deterministic algorithm can have competitive ratio better than 3. In the network verification problem, the graph is known in advance and the goal is to compute a minimum number of queries that verify all edges and non-edges. This problem has previously been studied as the problem of placing landmarks in graphs or determining the metric dimension of a graph. We show that there is no approximation algorithm for this problem with ratio o(log n) unless P=NP. Furthermore, we prove that the optimal number of queries for d-dimensional hypercubes is Theta(d/log d).

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.

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

In this chapter the author explains a clever approach to determining the winner of an election, and in so doing he demonstrates the following lessons: the most straightforward solution to a problem is not always the fastest one; often there are clever algorithms that can solve the same task with much less effort; it is not always easy to see whether an algorithm produces the correct result for every possible input; and sometimes one can prove that for a problem it is impossible to find an algorithm that is better than the one we already have.

We consider the problem of discovering properties (such as the diameter) of an unknown network G(V,E) with a minimum number of queries. Initially, only the vertex set V of the network is known. Information about the edges and non-edges of the network can be obtained by querying nodes of the network. A query at a node q ∈ V returns the union of all shortest paths from q to all other nodes in V . We study the problem as an online problem – an algorithm does not initially know the edge set of the network, and has to decide where to make the next query based on the information that was gathered by previous queries. We study how many queries are needed to discover the diameter, a minimal dominating set, a maximal independent set, the minimum degree, and the maximum degree of the network. We also study the problem of deciding with a minimum number of queries whether the network is 2-edge or 2-vertex connected. We use the usual competitive analysis to evaluate the quality of online algorithms, i.e., we compare online algorithms with optimum offline algorithms. For all properties except maximal independent set, 2-vertex connectivity and minimum/maximum degree, we present and analyze online algorithms. Furthermore we show, for all the aforementioned properties, that “many” queries are needed in the worst case. As our query model delivers more information about the network than the measurement heuristics that are currently used in practise, these negative results suggest that a similar behavior can be expected in realistic settings, or in more realistic models derived from the all-shortest-paths query model., Technical Report, 591

This special issue of Theory of Computing Systems is devoted to selected papers from the 3rd Workshop on Approximation and Online Algorithms (WAOA 2005) that took place in Palma de Mallorca, Spain in October 2005. Of 68 papers submitted to the workshop, 26 were accepted and 6 were invited to this special issue. The papers in this special issue deal with several of the most fundamental topics in approximation and online algorithms: optimization problems in graphs and networks, packing problems, and scheduling problems. Some of the papers consider new variants of classical problems. Bar-Yehuda, Feldman and Rawitz investigate the convex recoloring problem for trees, a problem arising in the context of phylogenetic tree reconstruction. They present an improved approximation algorithm, based on the local ratio technique and dynamic programming, as well as a fixed-parameter tractable algorithm. Blaser and Ram study the classical traveling salesman problem in a game-theoretic setting. They prove that it is NP-hard to determine whether the core of a metric TSP game is empty or not and provide approximately fair cost allocation schemes. Han, Iwama and Zhang consider the square packing problem, a two-dimensional geometric variant of the knapsack problem, in an online setting where previously packed squares can be removed later on. They give tight bounds on the competitive ratio for the

Given a set of weighted directed paths in a bidirected tree, the maximum weight edge-disjoint paths problem (MWEDP) is to select a subset of the given paths such that the selected paths are edge-disjoint and the total weight of the selected paths is maximized. MWEDP is NP - hard for bidirected trees of unbounded degree, even if all weights are the same (the unweighted case). Three different approximation algorithms are implemented: a known combinatorial (5/3 + ε)-approximation algorithm A 1 for the unweighted case, a new combinatorial 2-approximation algorithm A 2 for the weighted case, and a known (5/3 + ε)-approximation algorithm A 3 for the weighted case that is based on linear programming. For algorithm A 1 , it is shown how efficient data structures can be used to obtain a worst-case running-time of O(m + n + 4 1/ε √n ċ m) for instances consisting of m paths in a tree with n nodes. Experimental results regarding the running-times and the quality of the solutions obtained by the three approximation algorithms are reported. Where possible, the approximate solutions are compared to the optimal solutions, which were computed by running CPLEX on an integer linear programming formulation of MWEDP.

In all-optical networks with wavelength-division multiplexing several connections can share a physical link if the signals are transmitted on different wavelengths. As the number of available wavelengths is limited in practice, it is important to find wavelength assignments minimizing the number of different wavelengths used. This path coloring problem is NP-hard, and the best known polynomial-time approximation algorithm for directed tree networks achieves approximation ratio 5/3, which is optimal in the class of greedy algorithms for this problem. It is shown how the algorithm can be modified in order to improve its running-time to O(Tec(N,L)) for sets of paths with maximum load L in trees with N nodes, where Tec(n, k) is the time for edge-coloring a k-regular bipartite graph with n nodes. An implementation of this efficient version of the algorithm in C++ using the LEDA class library is described, and experimental results regarding the running-times and the number of wavelengths used are reported. An additional heuristic that reduces the number of wavelengths used in the average case while maintaining the worst-case bound of 5L/3 is described.

Modern high-performance communication networks pose a number of challenging problems concerning the efficient allocation of resources to connection requests. In all-optical networks with wavelength-division multiplexing, connection requests must be assigned paths and colors (wavelengths) such that intersecting paths receive different colors, and the goal is to minimize the number of colors used. This path coloring problem is proved NP -hard for undirected and bidirected ring networks. Path coloring in undirected tree networks is shown to be equivalent to edge coloring of multigraphs, which implies a polynomial-time optimal algorithm for trees of constant degree as well as NP -hardness and an approximation algorithm with absolute approximation ratio 4 3 and asymptotic approximation ratio 1.1 for trees of arbitrary degree. For bidirected trees, path coloring is shown to be NP -hard even in the binary case. A polynomial-time optimal algorithm is given for path coloring in undirected or bidirected trees with n nodes under the assumption that the number of paths touching every single node of the tree is O (( log n) 1−e ) . Call scheduling is the problem of assigning paths and starting times to calls in a network with bandwidth reservation such that the maximum completion time is minimized. In the case of unit bandwidth requirements, unit edge capacities, and unit call durations, call scheduling is equivalent to path coloring. If either the bandwidth requirements or the call durations can be arbitrary, call scheduling is shown NP -hard for virtually every network topology.

Broadcast Scheduling is a popular method for disseminating information in response to client requests. There are n pages of information, and clients request pages at different times. However, multiple clients can have their requests satisfied by a single broadcast of the requested page. In this article, we consider several related broadcast scheduling problems. One central problem we study simply asks to minimize the maximum response time (over all requests). Another related problem we consider is the version in which every request has a release time and a deadline, and the goal is to maximize the number of requests that meet their deadlines. While approximation algorithms for both these problems were proposed several years back, it was not known if they were NP-complete. One of our main results is that both these problems are NP-complete. In addition, we use the same unified approach to give a simple NP-completeness proof for minimizing the sum of response times. A very complicated proof was known for this version. Furthermore, we give a proof that FIFO is a 2-competitive online algorithm for minimizing the maximum response time (this result had been claimed earlier with no proof) and that there is no better deterministic online algorithm (this result was claimed earlier as well, but with an incorrect proof).

The problem of establishing and completing a given set of calls as early as possible is studied for bidirectional and directed calls in various classes of networks. Even under the assumption of unit bandwidth requirements and unit call durations, call scheduling is NP-hard for trees with unbounded degree, for rings, and for meshes. Whereas bidirectional calls can be scheduled optimally in polynomial time for trees of constant degree, the problem for directed calls is already NP-hard for binary trees. Approximation algorithms with a constant performance ratio are known for many NP-hard variants of call scheduling.