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.
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.
We consider the nth power metric facility location problem with linear penalties ((MFLPLP)-F-n) in this work, extending both the nth power metric facility location problem ((MFLP)-F-n) and the metric facility location...
详细信息
We consider the nth power metric facility location problem with linear penalties ((MFLPLP)-F-n) in this work, extending both the nth power metric facility location problem ((MFLP)-F-n) and the metric facility location problem with linear penalties (MFLPLP). We present an LP-rounding based approximation algorithm to the (MFLPLP)-F-n with bi-factor approximation ratio (gamma(f), gamma(c)), where gamma(f) and gamma(c) are the ratios corresponding to facility, and connection and penalty costs respectively. Finally we show that the bi-factor curve is close to the lower bound (gamma(f), 1+(3(n) - 1) e(-gamma f)) when the facility factor gamma(f) > 2 for theM(2)FLPLP.
As a classic NP-hard problem in machine learning and computational geometry,the k-means problem aims to partition the given dataset into k clusters according to the minimal squared Euclidean *** from k-means problem a...
详细信息
As a classic NP-hard problem in machine learning and computational geometry,the k-means problem aims to partition the given dataset into k clusters according to the minimal squared Euclidean *** from k-means problem and most of its variants,fuzzy k-means problem belongs to the soft clustering problem,where each given data point has relationship to every center *** to fuzzy k-means problem,fuzzy k-means problem with penalties allows that some data points need not be clustered instead of being paid *** this paper,we propose an O(αk In k)-approximation algorithm based on seeding algorithm for fuzzy k-means problem with penalties,whereαinvolves the ratio of the maximal penalty value to the minimal ***,we implement numerical experiments to show the effectiveness of our algorithm.
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).
In this paper, we study the Maximum Internal Spanning Tree Problem (MIST). Given an undirected simple graph G, the task for the Maximum Internal Spanning Tree problem is to find a spanning tree of G with maximum numbe...
详细信息
In this paper, we study the Maximum Internal Spanning Tree Problem (MIST). Given an undirected simple graph G, the task for the Maximum Internal Spanning Tree problem is to find a spanning tree of G with maximum number of internal vertices. We present an approximation algorithm with performance ratio 4//3 , which improves upon the best known performance ratio 3/2 . Our algorithm benefits from a new observation for bounding the number of internal vertices of a spanning tree. We can also give an example to show that the performance ratio 4/3 is actually tight for this algorithm. Finally, we show that MIST is Max-SNP-hard. (c) 2021 Elsevier Inc. All rights reserved.
Given an edge-weighted tree T and an integer p greater than or equal to 1, the minmax p-traveling salesmen problem on a tree T asks to find p tours such that the union of the p tours covers all the vertices. The objec...
详细信息
Given an edge-weighted tree T and an integer p greater than or equal to 1, the minmax p-traveling salesmen problem on a tree T asks to find p tours such that the union of the p tours covers all the vertices. The objective is to minimize the maximum of length of the p tours. It is known that the problem is NP-hard and has a (2 - 2/(p+1))-approximation algorithm which runs in O(p(P-1)n(P-1)) time for a tree with n vertices. In this paper, we consider an extension of the problem in which the set of vertices to be covered now can be chosen as a subset S of vertices and weights to process vertices in S are also introduced in the tour length. For the problem, we give an approximation algorithm that has the same performance guarantee, but runs in O((p - 1)! . n) time. (C) 2003 Elsevier B.V. All rights reserved.
暂无评论