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.
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.
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.
Given a graph G, an integer k, and a demand set D = {(s(1), t(1)),..., (s(1), t(1))}, the k-Steiner Forest problem finds a forest in graph G to connect at least k demands in D such that the cost of the forest is minim...
详细信息
Given a graph G, an integer k, and a demand set D = {(s(1), t(1)),..., (s(1), t(1))}, the k-Steiner Forest problem finds a forest in graph G to connect at least k demands in D such that the cost of the forest is minimized. This problem was proposed by Hajiaghayi and Jain in SODA'06. Thereafter, using a Lagrangian relaxation technique, Segev et al. gave the first approximation algorithm to this problem in ESA'06, with performance ratio O(n(2/3) log l). We give a simpler and faster approximation algorithm to this problem with performance ratio O(n(2/3) log k) via greedy approach, improving the previously best known ratio in the literature. (C) 2008 Elsevier B.V. All rights reserved.
Given a positive integer M, and a set S = {x(1),x(2),...,x(n),) of positive integers, the maximum subset sum problem is to find a subset S' of S such that Sigma(x is an element of S') x is maximized under the ...
详细信息
Given a positive integer M, and a set S = {x(1),x(2),...,x(n),) of positive integers, the maximum subset sum problem is to find a subset S' of S such that Sigma(x is an element of S') x is maximized under the constraint that the summation is no larger than M. In addition, the cardinality of S' is also a maximum among all subsets of S which achieve the maximum subset sum. This problem is known to be NP-hard. We analyse the average-case performance of a simple on-line approximation algorithm assuming that all integers in S are independent and have the same probability distribution. We develop a general methodology, i.e., using recurrence relations, to evaluate the expected values of the content and the cardinality of S' for any distribution. The maximum subset sum problem has important applications, especially in static job scheduling in multiprogammed parallel systems. The algorithm studied can also be easily adapted for dynamic job scheduling in such systems. (C) 1998 Elsevier Science Ltd. 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...
详细信息
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.
Translocation has been long learned as a basic operation to rearrange the structure of a genome. Translocation sorting asks to find a shortest sequence of translocations that transforms one genome into another, which ...
详细信息
Translocation has been long learned as a basic operation to rearrange the structure of a genome. Translocation sorting asks to find a shortest sequence of translocations that transforms one genome into another, which has attracted attention of many scientists in algorithm design. Signed translocation sorting can be solved in polynomial time. Unsigned translocation sorting turns out to be NP-Hard and Max-SNP-Hard. The best known approximation algorithm by now for unsigned translocation sorting can achieve a performance ratio 1.408. In this paper, we propose a new approximation algorithm for unsigned translocation sorting which can achieve a asymptotic performance ratio 1.375. (C) 2020 Elsevier Inc. All rights reserved.
暂无评论