The network substitution problem is to substitute an existing network for a new network so that to minimize the cost of exploiting the existing network during the period when the new network is being constructed. We s...
详细信息
The network substitution problem is to substitute an existing network for a new network so that to minimize the cost of exploiting the existing network during the period when the new network is being constructed. We show that this problem is NP-hard, and propose a 2-approximation algorithm for solving it. (c) 2005 Elsevier B.V. All rights reserved.
In a (linear) parametric optimization problem, the objective value of each feasible solution is an affine function of a real-valued parameter and one is interested in computing a solution for each possible value of th...
详细信息
In a (linear) parametric optimization problem, the objective value of each feasible solution is an affine function of a real-valued parameter and one is interested in computing a solution for each possible value of the parameter. For many important parametric optimization problems including the parametric versions of the shortest path problem, the assignment problem, and the minimum cost flow problem, however, the piecewise linear function mapping the parameter to the optimal objective value of the corresponding non-parametric instance (the optimal value function) can have super-polynomially many breakpoints (points of slope change). This implies that any optimal algorithm for such a problem must output a super-polynomial number of solutions. We provide a method for lifting approximation algorithms for non-parametric optimization problems to their parametric counterparts that is applicable to a general class of parametric optimization problems. The approximation guarantee achieved by this method for a parametric problem is arbitrarily close to the approximation guarantee of the algorithm for the corresponding non-parametric problem. It outputs polynomially many solutions and has polynomial running time if the non-parametric algorithm has polynomial running time. In the case that the non-parametric problem can be solved exactly in polynomial time or that an FPTAS is available, the method yields an FPTAS. In particular, under mild assumptions, we obtain the first parametric FPTAS for each of the specific problems mentioned above and a (3/2+epsilon)-approximation algorithm for the parametric metric traveling salesman problem. Moreover, we describe a post-processing procedure that, if the non-parametric problem can be solved exactly in polynomial time, further decreases the number of returned solutions such that the method outputs at most twice as many solutions as needed at minimum for achieving the desired approximation guarantee.
In this article, we investigate the dynamic (multi-period) facility location problem with potentially unserved clients or outliers. We propose a 3-approximation primal-dual algorithm based on an integer linear program...
详细信息
In this article, we investigate the dynamic (multi-period) facility location problem with potentially unserved clients or outliers. We propose a 3-approximation primal-dual algorithm based on an integer linear program formulation of the problem. We further improve the approximation ratio to 2 by combining the cost scaling and greedy improvement techniques.
We present a -approximation algorithm for the non-uniform soft capacitated k-facility location problem, violating the capacitated constrains by no more than a factor of 25. The main technique is based on the primal-du...
详细信息
We present a -approximation algorithm for the non-uniform soft capacitated k-facility location problem, violating the capacitated constrains by no more than a factor of 25. The main technique is based on the primal-dual algorithm for the soft capacitated facility location problem, and the exploitation of the combinatorial structure of the fractional solution for the soft capacitated k-facility location problem.
The survivable network design problem (SNDP) is to construct a minimum-cost subgraph satisfying certain given edge-connectivity requirements. The first polynomial-time approximation algorithm was given by Williamson e...
详细信息
The survivable network design problem (SNDP) is to construct a minimum-cost subgraph satisfying certain given edge-connectivity requirements. The first polynomial-time approximation algorithm was given by Williamson et al, (Combinatorica 15 (1995) 435-454). This paper gives an improved version that is more efficient. Consider a graph of n vertices and connectivity requirements that are at most k. Both algorithms find a solution that is within a factor 2k - 1 of optimal for k greater than or equal to 2 and a factor 2 of optimal for k = 1. Our algorithm improves the time from O(k(3)n(4)) to O(k(2)n(2) + kn(2) root log log n). Our algorithm shares features with those of Williamson et al, (Combinatorica 15 (1995) 435-454) out also differs from it at a high level, necessitating a different analysis of correctness and accuracy;our analysis is based on a combinatorial characterization of the "redundant" edges. Several other ideas are introduced to gain efficiency. These include a generalization of Padberg and Rao's characterization of minimum odd cuts, use of a representation of all minimum (s, t) cuts in a network, and a new priority queue system. The latter also improves the efficiency of the approximation algorithm of Goemans and Williamson (SIAM Journal on Computing 24 (1995) 296-317) for constrained forest problems such as minimum-weight matching, generalized Steiner trees acid others. (C) 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.
The main contribution of this work is to propose a primal-dual combinatorial 3(1 + epsilon)-approximation algorithm for the two-level facility location problem (2-LFLP) by exploring the approximation oracle concept. T...
详细信息
The main contribution of this work is to propose a primal-dual combinatorial 3(1 + epsilon)-approximation algorithm for the two-level facility location problem (2-LFLP) by exploring the approximation oracle concept. This result improves the previous primal-dual 6-approximation algorithm for the multilevel facility location problem, and also matches the previous primal-dual approximation ratio for the single-level facility location problem. One of the major merits of primal-dual type algorithms is their easy adaption to other variants of the facility location problems. As a demonstration, our primal-dual approximation algorithm can be easily adapted to several variants of the 2-LFLP, including models with stochastic scenario, dynamically arrived demands, and linear facility cost. (C) 2014 Elsevier B.V. All rights reserved.
The translocation operation is one of the popular operations for genome rearrangement. In this paper, we present a algorithm for computing unsigned translocation distance which improves upon the best known 2-approxima...
详细信息
The translocation operation is one of the popular operations for genome rearrangement. In this paper, we present a algorithm for computing unsigned translocation distance which improves upon the best known 2-approximation algorithm [J. Kececioglu, R. Ravi, Of mice and men: algorithms for evolutionary distances between genomes with translocation, in: 6th ACM-SIAM Symposium on Discrete algorithms, 1995, pp. 604-6131. (c) 2007 Elsevier Inc. All rights reserved.
We consider the facility location problem with submodular penalties (FLPSP), introduced by Hayrapetyan et al. (Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete algorithms (SODA), pp. 933-942, 2005), ...
详细信息
We consider the facility location problem with submodular penalties (FLPSP), introduced by Hayrapetyan et al. (Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete algorithms (SODA), pp. 933-942, 2005), who presented a 2.50-approximation algorithm that is non-combinatorial because this algorithm has to solve the LP-relaxation of an integer program with exponential number of variables. The only known polynomial algorithm for this exponential LP is via the ellipsoid algorithm as the corresponding separation problem for its dual program can be solved in polynomial time. By exploring the properties of the submodular function, we offer a primal-dual 3-approximation combinatorial algorithm for this problem.
An l-pseudoforest is a graph each of whose connected components is at most I edges removal being a tree. The l-Pseudoforest Deletion problem is to delete a vertex set P of minimum weight from a given vertex-weighted g...
详细信息
An l-pseudoforest is a graph each of whose connected components is at most I edges removal being a tree. The l-Pseudoforest Deletion problem is to delete a vertex set P of minimum weight from a given vertex-weighted graph G = (V, E) such that the remaining graph G[V \ P] is an l-pseudoforest The Feedback Vertex Set problem is a special case of the l-Pseudoforest Deletion problem with l = 0. In this paper, we present a polynomial time 41-approximation algorithm for the l-Pseudoforest Deletion problem with l >= 1 by using the local ratio technique. When l=1, we get a better approximation ratio 2 for the problem by further analyzing the local ratio, which matches the current best constant approximation factor for the Feedback Vertex Set problem. (C) 2019 Elsevier B.V. All rights reserved.
We consider the following planar maximum weight triangulation (MAT) problem: given a set of n points in the plane, find a triangulation such that the total length of edges in triangulation is maximized. We prove an Om...
详细信息
We consider the following planar maximum weight triangulation (MAT) problem: given a set of n points in the plane, find a triangulation such that the total length of edges in triangulation is maximized. We prove an Omega(root n) lower bound on the approximation factor for several heuristics: maximum greedy triangulation, maximum greedy spanning tree triangulation and maximum spanning tree triangulation. We then propose the Spoke Triangulation algorithm, which approximates the maximum weight triangulation for points in general position within a factor of almost four in O(n log n) time. The proof is simpler than the previous work. We also prove that Spoke Triangulation approximates the maximum weight triangulation of a convex polygon within a factor of two.
暂无评论