Data aggregation has been the focus of many researchers as one of the most important applications in Wireless Sensor Networks. A main issue of data aggregation is how to construct efficient schedules by which data can...
详细信息
Data aggregation has been the focus of many researchers as one of the most important applications in Wireless Sensor Networks. A main issue of data aggregation is how to construct efficient schedules by which data can be aggregated without any interference. The problem of constructing minimum latency data aggregation schedules (MLAS) has been extensively studied in the literature although most of existing works use the graph-based interference model. In this paper, we study the MLAS problem in the more realistic physical model known as signal-to-interference-noise-ratio (SINR). We first derive an Omega(log n) approximation lower bound for the MLAS problem in the metric SINR model. We also prove the NP-hardness of the decision version of MLAS in the geometric SINR model. This is a significant contribution as these results have not been obtained before for the SINR model. In addition, we propose two constant factor approximation algorithms whose latency is bounded by O(Delta + R) for the dual power model, where A is the maximum node degree of a network and R is the network radius. Finally we study the performance of the algorithms through simulation. (c) 2012 Elsevier B.V. All rights reserved.
We study the problem of finding the maximum number of disjoint uni-color paths in an edge-colored graph. We show the NP-hardness and the approximability and present approximation and exact algorithms. We also study th...
详细信息
We study the problem of finding the maximum number of disjoint uni-color paths in an edge-colored graph. We show the NP-hardness and the approximability and present approximation and exact algorithms. We also study the length-bounded version of the problem, in which the numbers of edges of the found paths are required to be upper bounded by a fixed integerl I. lt is shown that the problem can be solved in polynomial time for I <= 3 and is NP-hard for I >= 4. We also show that the problem can be approximated with ratio (I-1)/2 + epsilon in polynomial time for any epsilon > 0. Particularly, for I = 4, we present an efficient 2-approximation algorithm. (C) 2012 Elsevier B.V. All rights reserved.
A watchman tour in a polygonal domain (for short, polygon) is a closed curve in the polygon such that every point in the polygon is visible from at least one point of the tour. We show that the length of a minimum wat...
详细信息
A watchman tour in a polygonal domain (for short, polygon) is a closed curve in the polygon such that every point in the polygon is visible from at least one point of the tour. We show that the length of a minimum watchman tour in a polygon P with k holes is O(per(P) + root k . diam(P)), where per(P) and diam(P) denote the perimeter and the diameter of P. respectively. Apart from the multiplicative constant, this bound is tight in the worst case. We then generalize our result to watchman tours in polyhedra with holes in 3-space. We obtain an upper bound of O(per(P) + root k . per(P) . diam(P) + k(2/3) . diam(P)), which is again tight in the worst case. Our methods are constructive and lead to efficient algorithms for computing such tours. We also revisit the NP-hardness proof of the Watchman Tour Problem for polygons with holes. (C) 2012 Elsevier B.V. All rights reserved.
Consider the NP-hard problem of, given a simple graph G, to find a series-parallel subgraph of G with the maximum number of edges. The algorithm that, given a connected graph G, outputs a spanning tree of G, is a 1/2-...
详细信息
Consider the NP-hard problem of, given a simple graph G, to find a series-parallel subgraph of G with the maximum number of edges. The algorithm that, given a connected graph G, outputs a spanning tree of G, is a 1/2-approximation. Indeed, if n is the number of vertices in G, any spanning tree in G has n-1 edges and any series-parallel graph on n vertices has at most 2n-3 edges. We present a 7/12 -approximation for this problem and results showing the limits of our approach.
The degree of a CSP instance is the maximum number of times that any variable appears in the scopes of constraints. We consider the approximate counting problem for Boolean CSP with bounded-degree instances, for const...
详细信息
The degree of a CSP instance is the maximum number of times that any variable appears in the scopes of constraints. We consider the approximate counting problem for Boolean CSP with bounded-degree instances, for constraint languages containing the two unary constant relations {0} and {1}. When the maximum allowed degree is large enough (at least 6) we obtain a complete classification of the complexity of this problem. It is exactly solvable in polynomial time if every relation in the constraint language is affine. It is equivalent to the problem of approximately counting independent sets in bipartite graphs if every relation can be expressed as conjunctions of {0}, {1} and binary implication. Otherwise, there is no FPRAS unless NP = RP. For lower degree bounds, additional cases arise, where the complexity is related to the complexity of approximately counting independent sets in hypergraphs. (C) 2012 Elsevier Inc. All rights reserved.
We study a reliable facility location problem wherein some facilities are subject to failure from time to time. If a facility fails, customers originally assigned to it have to be reassigned to other (operational) fac...
详细信息
We study a reliable facility location problem wherein some facilities are subject to failure from time to time. If a facility fails, customers originally assigned to it have to be reassigned to other (operational) facilities. We formulate this problem as a two-stage stochastic program and then as a nonlinear integer program. Several heuristics that can produce near-optimal solutions are proposed for this NP-hard problem. For the special case where the probability that a facility fails is a constant (independent of the facility), we provide an approximation algorithm with a worst-case bound of 4. The effectiveness of our heuristics is tested by extensive computational studies, which also lead to some managerial insights.
Cooperative communication (CC) offers an efficient and low-cost way to achieve spatial diversity by forming a virtual antenna array among single-antenna nodes that cooperatively share their antennas. It has been well ...
详细信息
Cooperative communication (CC) offers an efficient and low-cost way to achieve spatial diversity by forming a virtual antenna array among single-antenna nodes that cooperatively share their antennas. It has been well recognized that the selection of relay nodes plays a critical role in the performance of CC. Most existing relay selection strategies focus on optimizing the outage probability or energy consumption. To fill in the vacancy of research on throughput improvement via CC, we study the relay selection problem with the objective of optimizing the throughput in this paper. For unicast, it is a P problem, and an optimal relay selection algorithm is provided with a correctness proof. For broadcast, we show the challenge of relay selection by proving it nonprobabilistic hard (NP-hard). A greedy heuristic algorithm is proposed to effectively choose a set of relay nodes that maximize the broadcast throughput. Simulation results show that the proposed algorithms can achieve high throughput under various network settings.
Determining the minimum distance of a linear code is one of the most important problems in algorithmic coding theory. The exact version of the problem was shown to be NP-complete by Vardy. The gap version of the probl...
详细信息
Determining the minimum distance of a linear code is one of the most important problems in algorithmic coding theory. The exact version of the problem was shown to be NP-complete by Vardy. The gap version of the problem was shown to be NP-hard for any constant factor under a randomized reduction in an earlier work. It was shown in the same paper that the minimum distance problem is not approximable in randomized polynomial time to the factor 2(log1-epsilon n) unless NP subset of RTIME(2(polylog(n))). In this paper, we derandomize the reduction and thus prove that there is no deterministic polynomial time algorithm to approximate the minimum distance to any constant factor unless P = NP. We also prove that the minimum distance is not approximable in deterministic polynomial time to the factor 2(log1-epsilon n) unless NP subset of DTIME(2(polylog(n))). As the main technical contribution, for any constant 2/3 < rho < 1, we present a deterministic algorithm that given a positive integer s, runs in time poly(s) and constructs a code C of length poly(s) with an explicit Hamming ball of radius rho d(C), such that the projection at the first s coordinates sends the codewords in the ball surjectively onto a linear subspace of dimension s, where d(C) denotes the minimum distance of C. The codes are obtained by concatenating Reed-Solomon codes with Hadamard codes.
We consider the feedback vertex set and feedback arc set problems on bipartite tournaments. We improve on recent results by giving a 2-approximation algorithm for the feedback vertex set problem. We show that this res...
详细信息
We consider the feedback vertex set and feedback arc set problems on bipartite tournaments. We improve on recent results by giving a 2-approximation algorithm for the feedback vertex set problem. We show that this result is the best that we can attain when using optimal solutions to a certain linear program as a lower bound on the optimal value. For the feedback arc set problem on bipartite tournaments, we show that a recent 4-approximation algorithm proposed by Gupta (2008) [8] is incorrect. We give an alternative 4-approximation algorithm based on an algorithm for the feedback arc set on (non-bipartite) tournaments given by van Zuylen and Williamson (2009) [14]. (C) 2010 Elsevier B.V. All rights reserved.
We prove a strong inapproximability result for the Balanced Minimum Evolution Problem. Our proof also implies that the problem remains NP-hard even when restricted to metric instances. Furthermore, we give a MST-based...
详细信息
We prove a strong inapproximability result for the Balanced Minimum Evolution Problem. Our proof also implies that the problem remains NP-hard even when restricted to metric instances. Furthermore, we give a MST-based 2-approximation algorithm for the problem for such instances. (C) 2012 Gwenael Joret and Samuel Fiorini. Published by Elsevier B.V. All rights reserved.
暂无评论