In the k-means problem with penalties, we are given a data set D subset of R-l of n points where each point j is an element of D is associated with a penalty cost p(j) and an integer k. The goal is to choose a set CS ...
详细信息
In the k-means problem with penalties, we are given a data set D subset of R-l of n points where each point j is an element of D is associated with a penalty cost p(j) and an integer k. The goal is to choose a set CS subset of R-l with vertical bar CS vertical bar <= k and a penalized subset D-p subset of D to minimize the sum of the total squared distance from the points in D\D-p to CS and the total penalty cost of points in D-p, namely Sigma(j is an element of D\Dp) d(2)(j, CS)+ Sigma(j is an element of Dp) p(j). We employ the primaldual technique to give a pseudo-polynomial time algorithm with an approximation ratio of (6.357+ epsilon) for the k-means problem with penalties, improving the previous best approximation ratio 19.849 + epsilon for this problem given by Feng et al. in Proceedings of FAW(2019).
The problem of finding a largest stable matching where preference lists may include ties and unacceptable partners (MAX SMTI) is known to be NP-hard. It cannot be approximated within 33/29 (> 1.1379) unless P=NP, a...
详细信息
The problem of finding a largest stable matching where preference lists may include ties and unacceptable partners (MAX SMTI) is known to be NP-hard. It cannot be approximated within 33/29 (> 1.1379) unless P=NP, and the current best approximation algorithm achieves the ratio of 1.5. MAX SMTI remains NP-hard even when preference lists of one side do not contain ties, and it cannot be approximated within 21/19 (> 1.1052) unless P=NP. However, even under this restriction, the best known approximation ratio is still 1.5. In this paper, we improve it to 25/17 (< 1.4706).
Given an edge-weighted complete graph G on 3n vertices, the maximum-weight triangle packing problem asks for a collection of n vertex-disjoint triangles in G such that the total weight of edges in these n triangles is...
详细信息
Given an edge-weighted complete graph G on 3n vertices, the maximum-weight triangle packing problem asks for a collection of n vertex-disjoint triangles in G such that the total weight of edges in these n triangles is maximized. Although the problem has been extensively studied in the literature, it is surprising that prior to this work, no nontrivial approximation algorithm had been designed and analyzed for its metric case, where the edge weights in the input graph satisfy the triangle inequality. In this paper, we design the first nontrivial polynomial-time approximation algorithm for the maximum-weight metric triangle packing problem. Our algorithm is randomized and achieves an expected approximation ratio of 0.66768 - epsilon for any constant epsilon > 0.
The phylogenetic diversity (PD) of a set of species is a measure of their evolutionary distinctness based on a phylogenetic tree. PD is increasingly being adopted as an index of biodiversity in ecological conservation...
详细信息
The phylogenetic diversity (PD) of a set of species is a measure of their evolutionary distinctness based on a phylogenetic tree. PD is increasingly being adopted as an index of biodiversity in ecological conservation projects. The Noah's Ark Problem (NAP) is an NP-Hard optimization problem that abstracts a fundamental conservation challenge in asking to maximize the expected PD of a set of taxa given a fixed budget, where each taxon is associated with a cost of conservation and a probability of extinction. Only simplified instances of the problem, where one or more parameters are fixed as constants, have as of yet been addressed in the literature. Furthermore, it has been argued that PD is not an appropriate metric for models that allow information to be lost along paths in the tree. We therefore generalize the NAP to incorporate a proposed model of feature loss according to an exponential distribution and term this problem NAP with Loss (NAPL). In this paper, we present a pseudopolynomial time approximation scheme for NAPL.
Given two genomic maps G(1) and G(2) each represented as a sequence of n gene markers, the maximal strip recovery (MSR) problem is to retain the maximum number of markers in both G(1) and G(2) such that the resultant ...
详细信息
Given two genomic maps G(1) and G(2) each represented as a sequence of n gene markers, the maximal strip recovery (MSR) problem is to retain the maximum number of markers in both G(1) and G(2) such that the resultant subsequences, denoted as G(1)* and G(2)* can be partitioned into the same set of maximal strips, which are common substrings of length greater than or equal to two. The complementary maximal strip recovery (CMSR) problem has the complementary goal to delete the minimum number of markers. Both MSR and CMSR have been shown to be NP-hard and APX-complete, and they admit a 4-approximation and a 3-approximation respectively. In this paper, we present an improved 7/3-approximation algorithm for the CMSR problem, with its worst-case performance analysis done through a local amortization with a re-weighting scheme. (C) 2011 Elsevier Inc. All rights reserved.
We study a multiple-vehicle routing problem with a minimum makespan objective and compatibility constraints. We provide an approximation algorithm and a nearly-matching hardness of approximation result. We also provid...
详细信息
We study a multiple-vehicle routing problem with a minimum makespan objective and compatibility constraints. We provide an approximation algorithm and a nearly-matching hardness of approximation result. We also provide computational results on benchmark instances with diverse sizes showing that the proposed algorithm (i) has a good empirical approximation factor. (ii) runs in a short amount of time and (iii) produces solutions comparable to the best feasible solutions found by a direct integer program formulation. (C) 2018 Elsevier B.V. All rights reserved.
This paper studies the minimum weight partial connected set cover problem (PCSC). Given an element set U, a collection of subsets of U, a weight function c : , a connected graph on vertex set , and a positive integer ...
详细信息
This paper studies the minimum weight partial connected set cover problem (PCSC). Given an element set U, a collection of subsets of U, a weight function c : , a connected graph on vertex set , and a positive integer , the goal is to find a minimum weight subcollection such that the subgraph of G induced by is connected, , and the weight of is minimum. If the graph has the property that any two sets with a common element has hop distance at most r in , then the problem is called r-hop PCSC. We presented an -approximation algorithm for the minimum weight 1-hop PCSC problem and an -approximation algorithm for the minimum cardinality r-hop PCSC problem. Our performance ratio improves previous results and our method is much simpler than previous methods.
In this paper, we study the generalized submodular maximization problem with a nonnegative monotone submodular set function as the objective function and subject to a matroid constraint. The problem is generalized thr...
详细信息
In this paper, we study the generalized submodular maximization problem with a nonnegative monotone submodular set function as the objective function and subject to a matroid constraint. The problem is generalized through the curvature parameter alpha is an element of [0, 1] which measures how far a set function deviates from linearity to submodularity. We propose a deterministic approximation algorithm which uses the approximation algorithm proposed by Buchbinder et al. [2] as a building block and inherits the approximation guarantee for alpha = 1. For general value of the curvature parameter alpha is an element of [0, 1], we present an approximation algorithm with a factor of 1+h(alpha)(y)+Delta.[3+alpha-(2+alpha)y-(1+alpha)h(alpha)(y)]/2+alpha+(1+alpha)(1-y), where y is an element of [0, 1] is a predefined parameter for tuning the ratio. In particular, when alpha = 1 we obtain a ratio 0.5008 when setting y = 0.9, coinciding with the renowned state-of-art approximate ratio; when alpha = 0 that the object is a linear function, the approximation factor equals one and our algorithm is indeed an exact algorithm that always produces optimum solutions. (C) 2021 Elsevier B.V. All rights reserved.
Finding the shortest vector in a lattice is a NP-hard problem. The best known approximation alpha(n-1/2), alpha >= 4/3, which is not algorithm for this problem is LLL algorithm with the approximation factor of alph...
详细信息
Finding the shortest vector in a lattice is a NP-hard problem. The best known approximation alpha(n-1/2), alpha >= 4/3, which is not algorithm for this problem is LLL algorithm with the approximation factor of alpha a good approximation factor. This work proposes a new polynomial time approximation algorithm for the shortest lattice vector problem. The proposed method makes use of only integer arithmetic and does not require Gram-Schmidt orthogonal basis for generating reduced basis. The proposed method is able to obtain an approximation factor of 1/(1-delta), where 0 <= delta < 1.
Motivated by recent applications in robust optimization and in sign-constrained linear-quadratic control, we study in this paper a new class of optimization problems called separated continuous conic programming (SCCP...
详细信息
Motivated by recent applications in robust optimization and in sign-constrained linear-quadratic control, we study in this paper a new class of optimization problems called separated continuous conic programming (SCCP). Focusing on a symmetric primal-dual pair, we develop a strong duality theory for the SCCP. Our idea is to use discretization to connect the SCCP and its dual to two ordinary conic programs. We show if the latter are strongly feasible and with finite optimal values, a condition that is readily veri. able, then the strong duality holds for the SCCP. This approach also leads to a polynomial-time approximation algorithm that solves the SCCP to any required accuracy.
暂无评论