Let T=(V,E) be a tree in which each edge is assigned a cost;let P be a set of source-sink pairs of vertices in V in which each source-sink pair produces a profit. Given a lower bound K for the profit, the K-prize-coll...
详细信息
Let T=(V,E) be a tree in which each edge is assigned a cost;let P be a set of source-sink pairs of vertices in V in which each source-sink pair produces a profit. Given a lower bound K for the profit, the K-prize-collecting multicut problem in trees with submodular penalties is to determine a partial multicut M subset of E such that the total profit of the disconnected pairs after removing M from T is at least K, and the total cost of edges in M plus the penalty of the set of still-connected pairs is minimized, where the penalty is determined by a nondecreasing submodular function. Based on the primal-dual scheme, we present a combinatorial polynomial-time algorithm by carefully increasing the penalty. In the theoretical analysis, we prove that the approximation factor of the proposed algorithm is ((8)(3)+ K-4(3 )+epsilon) , where K is the total curvature of the submodular function and epsilon is any fixed positive number. Experiments reveal that the objective value of the solutions generated by the proposed algorithm is less than 130% compared with that of the optimal value in most cases.
This study addresses the energy efficiency challenge in cloud data centers by examining the Virtual Machine Placement (VMP) problem. VMP involves mapping virtual machines (VMs) to physical machines (PMs) under capacit...
详细信息
This study addresses the energy efficiency challenge in cloud data centers by examining the Virtual Machine Placement (VMP) problem. VMP involves mapping virtual machines (VMs) to physical machines (PMs) under capacity constraints. The paper focuses on the bin packing with linear usage cost (BPLUC) variant of bin packing, which includes fixed and variable costs in the calculation of the cost of a used bin. We prove that every approximation algorithm for the bin and vector bin packing can be used for BPLUC and VBPLUC, respectively. We propose a more power-efficient approach to VMP by applying a vector bin packing algorithm to minimize power consumption in data centers. We test the proposed algorithm on various synthetic and real workloads, and the experimental results demonstrate that it is more power-efficient than existing algorithms for VMP. The findings suggest that the proposed algorithm has significant implications for energy-efficient strategies in cloud data centers. Generally, this study makes contributes to the development of energy-efficient approaches to VMP that can help reduce power consumption and improve the sustainability of cloud data centers.
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.
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).
This paper describes the traveling tournament problem, a well-known benchmark problem in the field of tournament timetabling. We propose an approximation algorithm for the traveling tournament problem with the constra...
详细信息
This paper describes the traveling tournament problem, a well-known benchmark problem in the field of tournament timetabling. We propose an approximation algorithm for the traveling tournament problem with the constraints such that both the number of consecutive away games and that of consecutive home games are at most k. When ka parts per thousand currency sign5, the approximation ratio of the proposed algorithm is bounded by (2k-1)/k+O(k/n) where n denotes the number of teams;when k > 5, the ratio is bounded by (5k-7)/(2k)+O(k/n). For k=3, the most investigated case of the traveling tournament problem to date, the approximation ratio of the proposed algorithm is 5/3+O(1/n);this is better than the previous approximation algorithm proposed for k=3, whose approximation ratio is 2+O(1/n).
Hard-capacitated k-means (HCKM) is one of the fundamental problems remaining open in combinatorial optimization and engineering. In HCKM, one is required to partition a given n-point set into k disjoint clusters with ...
详细信息
Hard-capacitated k-means (HCKM) is one of the fundamental problems remaining open in combinatorial optimization and engineering. In HCKM, one is required to partition a given n-point set into k disjoint clusters with known capacity so as to minimize the sum of within-cluster variances. It is known to be at least APX-hard, and most of the work on it has been done from a meta heuristic or bi-criteria approximation perspective. To the best our knowledge, no constant approximation algorithm or existence proof of such an algorithm is known. As our main contribution, we propose an FPT(k) approximation algorithm with constant performance guarantee for HCKM in this paper.
暂无评论