In this paper, we study the dominating selection optimisation problem with multiple channels and multiple radios in wireless sensor networks. The objective is to maximise the number of targets covered while selecting ...
详细信息
In this paper, we study the dominating selection optimisation problem with multiple channels and multiple radios in wireless sensor networks. The objective is to maximise the number of targets covered while selecting at most k nodes and at most k(i) channels with each selected node v(i). Our problem is a general case of the maximum coverage problem. We propose two algorithms: the first one is based on linear programming and PIPAGE rounding, in which its approximation ratio is 1/K(1-(1-1/m)(m)), where m is the number of the dominating nodes and K = max k(i). The second algorithm is based on greedy strategy with low time complexity. The simulation shows that the both two algorithms have good performance.
We give the first 2-approximation algorithm for the cluster vertex deletion problem. This approximation factor is tight, since approximating the problem within any constant factor smaller than 2 is UGC-hard. Our algor...
详细信息
We give the first 2-approximation algorithm for the cluster vertex deletion problem. This approximation factor is tight, since approximating the problem within any constant factor smaller than 2 is UGC-hard. Our algorithm combines previous approaches, based on the local ratio technique and the management of twins, with a novel construction of a "good" cost function on the vertices at distance at most 2 from any vertex of the input graph. As an additional contribution, we also study cluster vertex deletion from the polyhedral perspective, where we prove almost matching upper and lower bounds on how well linear programming relaxations can approximate the problem.
In this paper, we investigate the maximum induced matching problem (MaxIM) on C-5-free d-regular graphs. The previously known best approximation ratio for MaxIM on C-5-free d-regular graphs is (3d/4 - 1/8 + 3/16d-8). ...
详细信息
In this paper, we investigate the maximum induced matching problem (MaxIM) on C-5-free d-regular graphs. The previously known best approximation ratio for MaxIM on C-5-free d-regular graphs is (3d/4 - 1/8 + 3/16d-8). In this paper, we design a (2d/3 + 1/3)-approximation algorithm, whose approximation ratio is strictly smaller/better than the previous one when d >= 6.
We study a generalization of the vertex cover problem. For a given graph with weights on the vertices and an integer k, we aim to find a subset of the vertices with minimum total weight, so that at least k edges in th...
详细信息
We study a generalization of the vertex cover problem. For a given graph with weights on the vertices and an integer k, we aim to find a subset of the vertices with minimum total weight, so that at least k edges in the graph are covered. The problem is called the k-partial vertex cover problem. There are some 2-approximation algorithms for the problem. In the paper we do not improve on the approximation ratios of the previous algorithms, but we derive an iterative rounding algorithm. We present our technique in two algorithms. The first is an iterative rounding algorithm and gives a （2 ＋ Q/OPT ）-approximation for the k-partial vertex cover problem where Q is the largest finite weight in the problem definition and OPT is the optimal value for the instance. The second algorithm uses the first as a subroutine and achieves an approximation ratio of 2.
Given two rooted binary phylogenetic trees with identical leaf label-set, the maximum agreement forest (MAF) problem asks for a largest common subforest of the two trees. This problem has been studied extensively in t...
详细信息
Given two rooted binary phylogenetic trees with identical leaf label-set, the maximum agreement forest (MAF) problem asks for a largest common subforest of the two trees. This problem has been studied extensively in the literature, and has been known to be NP-complete and MAX SNP-hard. The previously best ratio of approximation algorithms for this problem is 3. In this paper, we make full use of the special relations among leaves in phylogenetic trees and present an approximation algorithm with ratio 2.5 for the MAF problem on two rooted binary phylogenetic trees.
In this paper, we consider the k-prize-collecting Steiner tree problem (k-PCST), extending both the prize-collecting Steiner tree problem (PCST) and the k-minimum spanning tree problem (k-MST). In this problem, we are...
详细信息
In this paper, we consider the k-prize-collecting Steiner tree problem (k-PCST), extending both the prize-collecting Steiner tree problem (PCST) and the k-minimum spanning tree problem (k-MST). In this problem, we are given a connected graph G=(V,E), a root vertex r and an integer k. Every edge in E has a nonnegative cost. Every vertex in V has a nonnegative penalty cost. We want to find an r-rooted tree F that spans at least k vertices such that the total cost, including the edge cost of the tree F and the penalty cost of the vertices not spanned by F, is minimized. Our main contribution is to present a 5-approximation algorithm for the k-PCST via the methods of primal-dual and Lagrangean relaxation.
We study the Betweenness problem. We are given a set of vertices and betweenness constraints. Each betweenness constraint of the form x similar to {y, z} requires that vertex x lies between vertices y and z. Our goal ...
详细信息
We study the Betweenness problem. We are given a set of vertices and betweenness constraints. Each betweenness constraint of the form x similar to {y, z} requires that vertex x lies between vertices y and z. Our goal is to find a vertex ordering that maximizes the number of satisfied constraints. In 1995, Chor and Sudan designed an SDP algorithm that satisfies half of all constraints in a satisfiable instance. We present a simple combinatorial linear time algorithm with the same approximation guarantee. (C) 2012 Elsevier B.V. All rights reserved.
Given a rectangle R with area alpha and a set of n positive reals A = {a1, a2,..., a(n)} with Sigma(ai is an element of A) ai = alpha, we consider the problem of dissecting R into it rectangles r(i) with area a(i) (i ...
详细信息
Given a rectangle R with area alpha and a set of n positive reals A = {a1, a2,..., a(n)} with Sigma(ai is an element of A) ai = alpha, we consider the problem of dissecting R into it rectangles r(i) with area a(i) (i = 1, 2,..., n) so that the set R of resulting rectangles minimizes an objective function such as the sum of the perimeters of the rectangles in R, the maximum perimeter of the rectangles in I., and the maximum aspect ratio of the rectangles in R, where we call the problems with these objective functions PERI-SUM, PERI-MAX and ASPECTRATIO. respectively. We propose an O(n log n) time algorithm that finds a dissection R of R that is a 1.25-approxi mate solution to PERI-SUM, a (2)/(root 3) approximate solution to PERI-MAX, and has an aspect ratio at most max {rho(R), 3, 1 + max(i=i=1,...,n-1) (ai+1)/(ai)}, where rho(R) denotes the aspect ratio of R. (c) 2006 Elsevier B.V. All fights reserved.
In this paper, we initiate the study of total liar's domination of a graph. A subset LaS dagger V of a graph G=(V,E) is called a total liar's dominating set of G if (i) for all vaV, |N (G) (v)a (c) L|a parts p...
详细信息
In this paper, we initiate the study of total liar's domination of a graph. A subset LaS dagger V of a graph G=(V,E) is called a total liar's dominating set of G if (i) for all vaV, |N (G) (v)a (c) L|a parts per thousand yen2 and (ii) for every pair u,vaV of distinct vertices, |(N (G) (u)a(a)N (G) (v))a (c) L|a parts per thousand yen3. The total liar's domination number of a graph G is the cardinality of a minimum total liar's dominating set of G and is denoted by gamma (TLR) (G). The Minimum Total Liar's Domination Problem is to find a total liar's dominating set of minimum cardinality of the input graph G. Given a graph G and a positive integer k, the Total Liar's Domination Decision Problem is to check whether G has a total liar's dominating set of cardinality at most k. In this paper, we give a necessary and sufficient condition for the existence of a total liar's dominating set in a graph. We show that the Total Liar's Domination Decision Problem is NP-complete for general graphs and is NP-complete even for split graphs and hence for chordal graphs. We also propose a 2(ln Delta(G)+1)-approximation algorithm for the Minimum Total Liar's Domination Problem, where Delta(G) is the maximum degree of the input graph G. We show that Minimum Total Liar's Domination Problem cannot be approximated within a factor of for any I mu > 0, unless NPaS dagger DTIME(|V|(loglog|V|)). Finally, we show that Minimum Total Liar's Domination Problem is APX-complete for graphs with bounded degree 4.
This paper deals with the maximum-weight 2-path packing problem (M2PP), which is the problem of computing a set of vertex-disjoint paths of length 2 in a given edge-weighted complete graph so that the total weight of ...
详细信息
This paper deals with the maximum-weight 2-path packing problem (M2PP), which is the problem of computing a set of vertex-disjoint paths of length 2 in a given edge-weighted complete graph so that the total weight of edges in the paths is maximized. Previously, Hassin and Rubinstein gave a randomized cubic-time approximation algorithm for M2PP which achieves an expected ratio of 35/67 - epsilon approximate to 0.5223 - epsilon for any constant epsilon > 0. We refine their algorithm and derandomize it to obtain a deterministic cubic-time approximation algorithm for the problem which achieves a better ratio (namely, 0.5265 - epsilon for any constant epsilon > 0).
暂无评论