Using a connected dominating set (CDS) to serve as a virtual backbone of a wireless sensor network is an effective way to save energy and alleviate broadcasting storm. Since nodes may fail due to accidental damage or ...
详细信息
ISBN:
(纸本)9781467399531
Using a connected dominating set (CDS) to serve as a virtual backbone of a wireless sensor network is an effective way to save energy and alleviate broadcasting storm. Since nodes may fail due to accidental damage or energy depletion, it is desirable to construct a fault tolerant CDS, which can be modeled as a k-connected m-fold dominating set ((k, m)-CDS for short). A subset of nodes C subset of V(G) is a (k, m)-CDS of G if every node in V(G)\C is adjacent with at least m nodes in C and the subgraph of G induced by C is k-connected. In this paper, we present an approximation algorithm for the minimum (3, m)-CDS problem with m >= 3, which has size at most gamma times that of an optimal solution, where gamma = alpha + 8 + 2ln(2 alpha - 6) for alpha >= 4 and gamma = 3 alpha + 2 ln 2 for alpha < 4, and alpha is the approximation ratio for the minimum (2, m)-CDS problem. This is the first performance-guaranteed algorithm for the minimum (3, m)-CDS problem in a general wireless network, and improves previous performance ratio in a homogeneous wireless sensor network by a large amount.
Link scheduling is a fundamental problem in wireless ad hoc and sensor networks. In this paper, we focus on the shortest link scheduling(SLS) under SINR and hypergraph models, and propose an approximation algorithm Ge...
详细信息
ISBN:
(纸本)9783319077826;9783319077819
Link scheduling is a fundamental problem in wireless ad hoc and sensor networks. In this paper, we focus on the shortest link scheduling(SLS) under SINR and hypergraph models, and propose an approximation algorithm GeoSLS by using geometric links for better performance than GOW* proposed by Blough, Resta and Santi(2010). For the average length of scheduling, GeoSLS decreases 1/m compared with GOW*, where m = left perpendicular4p+(Delta(max)-4).(1-p)right perpendicular is the expected number of the links in the set V returned by HyperMaxLS and 0 < p < 1 is the probability of the number of the links scheduled simultaneously in the set V. In the worst, ideal and average cases, the ratios of time complexity of our algorithm GeoSLS to GOW* are O(Delta(max)/(k) over bar), O(1/((k) over ***(max))) and O(Delta(max)/((k) over bar .m)), respectively, where 1 < <(k)over bar> < Delta(max) is a constant called the SNR diversity of instance G.
The translocation operation is one of the popular operations for genome rearrangement. In this paper, we present a 1.75-approximation algorithm for computing unsigned translocation distance which improves upon the bes...
详细信息
ISBN:
(纸本)3540309357
The translocation operation is one of the popular operations for genome rearrangement. In this paper, we present a 1.75-approximation algorithm for computing unsigned translocation distance which improves upon the best known 2-approximation algorithm [1].
The virtual machine placement problem (VMPP) is an np-hard optimization problem in cloud computing that involves efficiently allocating virtual machines (VMs) to physical hosts in such a way that the resource wastage ...
详细信息
We present a (1 + root 3 + is an element of)-approximation algorithm for the k-median problem with uniform penalties, extending the recent result by Li and Svensson for the classical k-median problem without penalties...
详细信息
ISBN:
(纸本)9783319487489
We present a (1 + root 3 + is an element of)-approximation algorithm for the k-median problem with uniform penalties, extending the recent result by Li and Svensson for the classical k-median problem without penalties. One important difference of this work from that of Li and Svensson is a new definition of sparse instance to exploit the combinatorial structure of our problem. (C) 2018 Elsevier B.V. All rights reserved.
In this paper, we study the single machine total completion scheduling problem subject to a period of maintenance. We propose an approximation algorithm to solve the problem with a worst case error bound of 3/17. Furt...
详细信息
In this paper, we study the single machine total completion scheduling problem subject to a period of maintenance. We propose an approximation algorithm to solve the problem with a worst case error bound of 3/17. Furthermore, an example is provided to show that the bound is tight. Computational experiments and an analysis are given afterwards. (C) 2003 Elsevier B.V. All rights reserved.
Being the unbalanced version of the famous Min s-t Cut problem, the Min k-Size s-t Cut problem asks to find a k-size s-t cut with the minimum capacity, where a k-size s-t cut means an s-t cut with its s-side having si...
详细信息
ISBN:
(纸本)9783319087825
Being the unbalanced version of the famous Min s-t Cut problem, the Min k-Size s-t Cut problem asks to find a k-size s-t cut with the minimum capacity, where a k-size s-t cut means an s-t cut with its s-side having size at most k. This problem is fundamental and has extensive applications, especially in community identification in social and information networks. It is known that the Min k-Size s-t Cut problem is NP-hard and can be approximated within O (logn), where n is the number of vertices in the input graph. In this paper, we give a new approximation algorithm for the Min k-Size s-t Cut problem based on the parametric flow technique. The algorithm is very simple and has only three lines to state. Its approximation ratio is k+1/K+1-k*, where k* is the size of the s-side of an optimal solution. (C) 2015 Elsevier B.V. All rights reserved.
Genomic Scaffold Filling problem forms an important class of problems, and has been paid lots of attention in the literature. In this paper, we study one of the Genomic Scaffold Filling problem, called One-sided-GSF-m...
详细信息
ISBN:
(数字)9783030271954
ISBN:
(纸本)9783030271954;9783030271947
Genomic Scaffold Filling problem forms an important class of problems, and has been paid lots of attention in the literature. In this paper, we study one of the Genomic Scaffold Filling problem, called One-sided-GSF-max-BC problem. The previous approximation ratio for the problem is 2. However, as we pointed out in the introduction part, the ratio 2 algorithm in the literature can only deal with special instances of the problem, not really solve the One-sided-GSF-max-BC problem. In this paper, we give an approximation algorithm of ratio 2.57 for the One-sided-GSF-max-BC problem. Our method is based on auxiliary graphs constructed and two applications of finding maximum matching in auxiliary graphs.
In this paper, we study the algorithm for solving a kind of new problem called generalized separated continuous conic programming (GSCCP), which has great modeling power. Based on the relationships between GSCCP and i...
详细信息
ISBN:
(纸本)9783037853511
In this paper, we study the algorithm for solving a kind of new problem called generalized separated continuous conic programming (GSCCP), which has great modeling power. Based on the relationships between GSCCP and its discretization, GSCCP and its dual, we proposed an approximation, algorithm which can produce a feasible solution for GSCCP with prescribed precision. We also present a numerical example to illustrate the efficiency of this algorithm. To our knowledge, this is the first algorithm for solving GSCCP so far.
We give constant-factor approximation algorithms for branch-decomposition of planar graphs. Our main result is an algorithm which for an input planar graph G of n vertices and integer k, in O(n log(4) n) time either c...
详细信息
ISBN:
(纸本)9783319123400;9783319123394
We give constant-factor approximation algorithms for branch-decomposition of planar graphs. Our main result is an algorithm which for an input planar graph G of n vertices and integer k, in O(n log(4) n) time either constructs a branch-decomposition of G with width at most (2 + delta)k, delta > 0 is a constant, or a (k + 1) x [k+1/2] cylinder minor of G implying O(G) > k, bw(G) is the branchwidth of G. This is the first (n) time constant-factor approximation for branchwidth/treewidth and largest grid/cylinder minors of planar graphs and improves the previous min{0(n(1+epsilon)), O(nk(3))} (epsilon > 0 is a constant) time constant-factor approximations. For a planar graph G and k = bw(G), a branch-decomposition of width at most (2+delta)k and gxg/2 cylinder/grid minor with g = k/beta, beta> 2 is constant, can be computed by our algorithm in 0(n log(4) n log k) time.
暂无评论