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.
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.
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.
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.
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.
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.
An improved approximation algorithm is presented in this paper for the multicast k-tree routing problem. The algorithm has a worst case performance ratio of (2.4 + rho), where rho is the best approximation ratio for t...
详细信息
An improved approximation algorithm is presented in this paper for the multicast k-tree routing problem. The algorithm has a worst case performance ratio of (2.4 + rho), where rho is the best approximation ratio for the metric Steiner tree problem (and is about 1.55 so far). The previous best approximation algorithm for the multicast k-tree routing problem has a performance ratio of 4. Two techniques, weight averaging and tree partitioning, are developed to facilitate the algorithm design and analysis.
Given a complete k-partite graph G = (V-1, V-2,..., V-k;E) satisfying vertical bar V-1 vertical bar = vertical bar V-2 vertical bar = ... = vertical bar V-k vertical bar = n and weights of all k-cliques of G, the k-di...
详细信息
Given a complete k-partite graph G = (V-1, V-2,..., V-k;E) satisfying vertical bar V-1 vertical bar = vertical bar V-2 vertical bar = ... = vertical bar V-k vertical bar = n and weights of all k-cliques of G, the k-dimensional assignment problem finds a partition of vertices of G into a set of(pairwise disjoint) n k-cliques that minimizes the sum total of weights of the chosen cliques. In this paper, we consider a case in which the weight of a clique is defined by the sum of given weights of edges induced by the clique. Additionally, we assume that vertices of G are embedded in the d-dimensional space Q(d) and a weight of an edge is defined by the square of the Euclidean distance between its two endpoints. We describe that these problem instances arise from a multidimensional Gaussian model of a data-association problem. We propose a second-order cone programming relaxation of the problem and a polynomial time randomized rounding procedure. We show that the expected objective value obtained by our algorithm is bounded by (5/2 - 3/k) times the optimal value. Our result improves the previously known bound (4 - 6/k) of the approximation ratio. (C) 2007 Elsevier B.V. All rights reserved.
Knapsack median is a generalization of the classic k-median problem in which we replace the cardinality constraint with a knapsack constraint. It is currently known to be 32-approximable. We improve on the best known ...
详细信息
Knapsack median is a generalization of the classic k-median problem in which we replace the cardinality constraint with a knapsack constraint. It is currently known to be 32-approximable. We improve on the best known algorithms in several ways, including adding randomization and applying sparsification as a preprocessing step. The latter improvement produces the first LP for this problem with bounded integrality gap. The new algorithm obtains an approximation factor of 17.46. We also give a 3.05 approximation with small budget violation.
The paper investigates a new three-machine shop scheduling problem that arises from many production systems, such as the garment assembly line, etc. In such scenarios, each job consists of three operations, each of wh...
详细信息
The paper investigates a new three-machine shop scheduling problem that arises from many production systems, such as the garment assembly line, etc. In such scenarios, each job consists of three operations, each of which has to be non-preemptively processed by one specific machine. In contrast with the classical three-machine shop scheduling, the processing order of the operations of each job is partially restricted. In particular, the first two operations are ordered and all the same for all jobs, while the third operation is not restricted. The objective is to minimize the makespan. We show the problem is NP-hard in the ordinary sense and present a polynomial time approximation algorithm with a worst case performance ratio of 3/2.
暂无评论