We give an algorithm requiring O(c(1/epsilon 2) n) time to find an epsilon-optimal traveling salesman tour in the shortest-path metric defined by an undirected planar graph with nonnegative edgelengths. For the case o...
详细信息
We give an algorithm requiring O(c(1/epsilon 2) n) time to find an epsilon-optimal traveling salesman tour in the shortest-path metric defined by an undirected planar graph with nonnegative edgelengths. For the case of all lengths equal to 1, the time required is O(c(1/epsilon 2) n).
Our problem formulation is as follows. Given a weighted disk graph G where the weight of edge represents the transimission energy consumption, we wish to determine a dominating tree T of G such that the total weight o...
详细信息
ISBN:
(纸本)9783540885818
Our problem formulation is as follows. Given a weighted disk graph G where the weight of edge represents the transimission energy consumption, we wish to determine a dominating tree T of G such that the total weight of edges in T is minimized. To the best of our knowledge, this problem have, riot been addressed in the literature. Solving the dominating tree problem can yield a routing backbone for broadcast protocols since: (1) each node does not have to construct, their own broadcast tree, (2) utilize the virtual backbone to reduce the message overhead, and (3) the weight of backbone is minimized. Our contributions to this problem is multi-fold: First, the paper is the first to study this problem, prove the hardness of this problem and propose air approximation framework. Second, we present a heuristic to approximate the solution with low time complexity. Third, a distributed algorithm is provided for practical implementation. Finally, we verify the effectiveness of our proposal through simulation.
Given a set T of n points in IR2, a Manhattan Network G is a network with all its edges horizontal or vertical segments, such that for all p, q is an element of T, in G there exists a path (named a Manhattan path) of ...
详细信息
ISBN:
(纸本)9783540921813
Given a set T of n points in IR2, a Manhattan Network G is a network with all its edges horizontal or vertical segments, such that for all p, q is an element of T, in G there exists a path (named a Manhattan path) of the length exactly the Manhattan distance between p and q. The Minimum Manhattan Network problem is to find a Manhattan network of the minimum length, i.e., the total length of the segments of the network is to be minimized. In this paper we present a 2-approximation algorithm with time complexity O(n log n), which improves the 2-approximation algorithm with time complexity O(n(2)). Moreover, compared with other 2-approximation algorithms employing linear programming or dynamic programming technique, it was first discovered that only greedy strategy suffices to get 2-approximation network.
This paper presents a new, algorithm for finding better approximation solutions to the min-cost point coverage problem in wireless sensor networks. The problem is to compute a deterministic sensor deployment plan, wit...
详细信息
ISBN:
(纸本)9783540885818
This paper presents a new, algorithm for finding better approximation solutions to the min-cost point coverage problem in wireless sensor networks. The problem is to compute a deterministic sensor deployment plan, with minimum monetary cost on sensors, to cover the set of targets spread across a geographical region such that each target is covered by multiple sensors. This is a Max-SNP-complete problem. Our approximation algorithm, called alpha-beta approximation, is a convex combination of greedy LP-rounding and greedy set-cover selection. We show that, through a large number of numerical simulations on randomly generated targets and sites, alpha beta approximation produces efficiently better approximation results than the best approximation algorithm previously known. In particular, the alpha-beta approximation in our experiments never exceeds an approximation ratio of 1.07, providing up to 14.86% improvement over previous approximation algorithms.
We consider the capacitated multi-source multicast tree routing problem (CMMTR) in an undirected graph G = (V,E) with a vertex set V, an edge set E and an edge weight w(e) >= 0, e epsilon E. We are given a source s...
详细信息
We consider the capacitated multi-source multicast tree routing problem (CMMTR) in an undirected graph G = (V,E) with a vertex set V, an edge set E and an edge weight w(e) >= 0, e epsilon E. We are given a source set S epsilon V with a weight g(e) >= 0, e epsilon S, a terminal set M subset of V - S with a demand function q : M -> R+, and a real number K > 0, where g(s) means the cost for opening a vertex s is an element of S as a source in a multicast tree. Then the CMMTR asks to find a subset S' subset of S, a partition {Z(1), Z(2),..., Z(l)) of M, and a set of subtrees T-1, T-2,..., T-l of G such that, for each i, Sigma(l is an element of Zi) q(t) <= K and T-i spans Z(i) boolean OR {s} for some s epsilon S'. The objective is to minimize the sum of the opening cost of S' and the constructing cost of (T-i), i.e., Sigma(s epsilon S') g(s) + Sigma(l)(i)=1 w(T-i), where w(T-i) denotes the sum of weights of all edges in Ti. In this paper, we propose a (2puFL + PST)-approximation algorithm to the CMMTR, where puFL and PST are any approximation ratios achievable for the uncapacitated facility location and the Steiner tree problems, respectively. When all terminals have unit demands, we give a ((3/2)rho(UFL) + (4/3)rho(ST)) -approximation algorithm.
Wireless sensor networks promise a new paradigm for gathering data via collaboration among sensors spreading over a large geometrical region. Many applications impose delay requirements for data gathering and ask for ...
详细信息
Wireless sensor networks promise a new paradigm for gathering data via collaboration among sensors spreading over a large geometrical region. Many applications impose delay requirements for data gathering and ask for time-efficient schedules for aggregating sensed data and sending to the data sink. In this paper, the authors study the minimum data aggregation time problem under collision-free transmission model. In each time round, data sent by a sensor reaches all sensors within its transmission range, but a sensor can receive data only when it is the only data that reaches the sensor. The goal is to find the method that schedules data transmission and aggregation at sensors so that the time for all requested data to be sent to the data sink is minimal. The authors propose a 7△/log2｜s｜＋c, new approximation algorithm for this NP-hard problem with guaranteed performance ratio which significantly reduces the current best ratio of △- 1, where S is the set of sensors containing source data, A is the maximal number of sensors within the transmission range of any sensor, and e is a constant. The authors also conduct extensive simulation, the obtained results justify the improvement of proposed algorithm over the existing one.
Given m facilities each with an opening cost, n demands, and distance between every demand and facility, the Facility Location problem finds a solution which opens some facilities to connect every demand to an opened ...
详细信息
Given m facilities each with an opening cost, n demands, and distance between every demand and facility, the Facility Location problem finds a solution which opens some facilities to connect every demand to an opened facility such that the total cost of the solution is minimized. The κ-Facility Location problem further requires that the number of opened facilities is at most κ, where κ is a parameter given in the instance of the problem. We consider the Facility Location problems satisfying that for every demand the ratio of the longest distance to facilities and the shortest distance to facilities is at most ω, where ω is a predefined constant. Using the local search approach with scaling technique and error control technique, for any arbitrarily small constant ε 〉 0, we give a polynomial-time approximation algorithm for the ω-constrained Facility Location problem with approximation ratio 1 ＋ √ω ＋ ε, which significantly improves the previous best known ratio （ω ＋ 1）/α for some 1 ≤ α ≤2, and a polynomial-time approximation algorithm for the ω-constrained κ- Facility Location problem with approximation ratio ω ＋ 1 ＋ ε. On the aspect of approximation hardness, we prove that unless NP C DTIME（n^O（log log n））, the ω-constrained Facility Location problem cannot be approximated within 1 ＋ln √ω 1, which slightly improves the previous best known hardness result 1.243 ＋ 0.316 ln（ω - 1）. The experimental results on the standard test instances of Facility Location problem show that our algorithm also has good performance in practice.
In this paper we consider coupled-task single-machine and two-machine flow shop scheduling problems with exact delays, unit processing times, and the makespan as an objective function. The main results of the paper ar...
详细信息
In this paper we consider coupled-task single-machine and two-machine flow shop scheduling problems with exact delays, unit processing times, and the makespan as an objective function. The main results of the paper are fast 7/4- and 3/2-approximation algorithms for solving the single- and two-machine problems, respectively. (c) 2006 Elsevier B.V. All rights reserved.
In this article, we study metrics of negative type, which are metrics ( V, d) such that root d is an Euclidean metric;these metrics are thus also known as l(2)-squared metrics. We show how to embed n-point negative-ty...
详细信息
ISBN:
(纸本)9780898715859
In this article, we study metrics of negative type, which are metrics ( V, d) such that root d is an Euclidean metric;these metrics are thus also known as l(2)-squared metrics. We show how to embed n-point negative-type metrics into Euclidean space l(2) with distortion D = O(log (3/4) n). This embedding result, in turn, implies an O(log (3/4) k)-approximation algorithm for the Sparsest Cut problem with nonuniform demands. Another corollary we obtain is that n-point subsets of l(1) embed into l(2) with distortion O(log (3/4) n).
It was a long-standing open problem whether the minimum weight dominating set in unit disk graphs has a polynomial-time constant-approximation. In 2006, Ambuhl et al solved this problem by presenting a 72-approximatio...
详细信息
ISBN:
(纸本)9783540697329
It was a long-standing open problem whether the minimum weight dominating set in unit disk graphs has a polynomial-time constant-approximation. In 2006, Ambuhl et al solved this problem by presenting a 72-approximation for the minimum weight dominating set and also a 89-approximation for the minimum weight connected dominating set in unit disk graphs. In this paper, we improve their results by giving a (6 + epsilon)-approximation for the minimum weight dominating set and a (10 + epsilon)-approximation for the minimum weight connected dominating set in unit disk graphs where epsilon is any small positive number.
暂无评论