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.
Breakpoint graph decomposition is a crucial step in all recent approximation algorithms for SORTING BY REVERSALS, which is one of the best-known algorithmic problems in computational molecular biology. Caprara and Riz...
详细信息
Breakpoint graph decomposition is a crucial step in all recent approximation algorithms for SORTING BY REVERSALS, which is one of the best-known algorithmic problems in computational molecular biology. Caprara and Rizzi recently improved the approximation ratio for breakpoint graph decomposition from 3/2 to 33/23 + epsilon approximate to 1.4348 + epsilon, for any positive epsilon. In this paper, we extend the techniques of Caprara and Rizzi and incorporate a balancing argument to further improve the approximation ratio to 5073-15root1201/3208 + epsilon approximate to 1.4193 + epsilon, for any positive epsilon. These improvements imply improved approximation results for SORTING BY REVERSALS for almost all random permutations.
Given a graph G = (V, E), an L(2, 1)-labeling of the graph is an assignment l from the vertex set to the set of nonnegative integers such that for any pair of vertices (u, v), vertical bar l(u) - l(v)vertical bar >...
详细信息
Given a graph G = (V, E), an L(2, 1)-labeling of the graph is an assignment l from the vertex set to the set of nonnegative integers such that for any pair of vertices (u, v), vertical bar l(u) - l(v)vertical bar >= 2 if u and v are adjacent, and l(u) not equal l(v) if u and v are at distance 2. The L(2, 1)-labeling problem is to minimize the range of l (i.e., max(u is an element of V)(l(u))-min(u is an element of V)(l(u))+ 1). Although the problem is generally hard to approximate within any constant factor, it was known to be approximable within factor 10.67 for unit disk graphs. This paper designs a new way of partitioning the plane into squares for periodic labeling, based on which we present an 8-approximation polynomial-time algorithm for L(2, 1)-labeling of unit disk graphs. (c) 2023 Elsevier B.V. All rights reserved.
In this paper, we study the dynamic facility location problem with submodular penalties （DFLPSP）. We present a combinatorial primal-dual 3-approximation algorithm for the DFLPSP.
In this paper, we study the dynamic facility location problem with submodular penalties （DFLPSP）. We present a combinatorial primal-dual 3-approximation algorithm for the DFLPSP.
Graph partition problems have been investigated extensively in combinatorial optimization. In this work, we consider an important graph partition problem which has applications in the design of VLSI circuits, namely, ...
详细信息
Graph partition problems have been investigated extensively in combinatorial optimization. In this work, we consider an important graph partition problem which has applications in the design of VLSI circuits, namely, the balanced Max-3-Uncut problem. We formulate the problem as a discrete linear program with complex variables and propose an approximation algorithm with an approximation ratio of 0.3456 using a semidefinite programming rounding technique along with a greedy swapping step afterwards to guarantee the balanced constraint. Our analysis utilizes a bivariate function, rather than the univariate function in previous work.
For a given undirected (edge) weighted graph G = (V, E), a terminal set S subset of V and a root r is an element of S, the rooted k-vertex connected minimum Steiner network (kVSMN(r)) problem requires to construct a m...
详细信息
For a given undirected (edge) weighted graph G = (V, E), a terminal set S subset of V and a root r is an element of S, the rooted k-vertex connected minimum Steiner network (kVSMN(r)) problem requires to construct a minimum-cost subgraph of G such that each terminal in S \ {r} is k-vertex connected to r. As an important problem in survivable network design, the kVSMNr problem is known to be NP-hard even when k = 1 [14]. For k = 3 this paper presents a simple combinatorial eight-approximation algorithm, improving the known best ratio 14 of Nutov [20]. Our algorithm constructs an approximate 3VSMNr through augmenting a two-vertex connected counterpart with additional edges of bounded cost to the optimal. We prove that the total cost of the added edges is at most six times of the optimal by showing that the edges in a 3VSMNr compose a subgraph containing our solution in such a way that each edge appears in the subgraph at most six times.
In multi-objective convex optimization it is necessary to compute an infinite set of nondominated points. We propose a method for approximating the nondominated set of a multi-objective nonlinear programming problem, ...
详细信息
In multi-objective convex optimization it is necessary to compute an infinite set of nondominated points. We propose a method for approximating the nondominated set of a multi-objective nonlinear programming problem, where the objective functions and the feasible set are convex. This method is an extension of Benson's outer approximation algorithm for multi-objective linear programming problems. We prove that this method provides a set of weakly epsilon-nondominated points. For the case that the objectives and constraints are differentiable, we describe an efficient way to carry out the main step of the algorithm, the construction of a hyperplane separating an exterior point from the feasible set in objective space. We provide examples that show that this cannot always be done in the same way in the case of non-differentiable objectives or constraints.
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.
暂无评论