In this paper, we consider the two-stage stochastic fault-tolerant facility location problem with uniform connectivity demand (2-SFTFLPUCD). We present the currently best known approximation ratio 1.8526 for 2-SFTFLPU...
详细信息
In this paper, we consider the two-stage stochastic fault-tolerant facility location problem with uniform connectivity demand (2-SFTFLPUCD). We present the currently best known approximation ratio 1.8526 for 2-SFTFLPUCD. Initially, we demonstrate a stronger result of the 3-approximation algorithm based on analysis of the sum of opening and connection cost. Subsequently, we seed a greedy augmentation algorithm with the solution of a 3-approximation algorithm to yield an improved approximation ratio.
作者：
Zhang, LiLi, QiaoliangHunan Agr Univ
Coll Informat & Intelligence Changsha 410128 Hunan Peoples R China Hunan Normal Univ
Sch Math & Stat Key Lab Comp & Stochast Math Minist Educ Changsha 410081 Hunan Peoples R China
In this paper, we consider dynamic facility location problem with unit demand (DFLPUD). We propose a 1.52-approximation algorithm that skillfully integrates dual-fitting and greedy augmentation schemes. Our algorithmi...
详细信息
In this paper, we consider dynamic facility location problem with unit demand (DFLPUD). We propose a 1.52-approximation algorithm that skillfully integrates dual-fitting and greedy augmentation schemes. Our algorithmic framework begins by formulating DFLPUD as a set covering linear integer programming problem. Then we scale the opening cost of all facilities and use the solution of dual-fitting algorithm to seed a local search to yield an improved performance guarantee 1.52. To the best of our knowledge, this is the best known approximation ratio for DFLPUD.
In the k-product uncapacitated facility location problem with penalties, we are given a set of demand points where clients are located and a set of potential sites where facilities with unlimited capacities can be ope...
详细信息
In the k-product uncapacitated facility location problem with penalties, we are given a set of demand points where clients are located and a set of potential sites where facilities with unlimited capacities can be opened. There are k different kinds of products to be supplied by a set of open facilities. Each open facility can supply only a distinct product with a non-negative fixed cost determined by the product it wants to supply. Each client is either supplied with k kinds of products by a set of k different open facilities or completely rejected. There is a non-negative service cost between each pair of locations and also a penalty cost for each client if its service is rejected. These service costs are assumed to be symmetric and satisfy the triangle inequality. The goal is to select a set of clients to reject their service and then choose a set of facilities to be opened to service the remaining clients so that the total cost of opening facilities, servicing the clients, and the penalty is minimized. We address two different integer programs to describe the problem. Based on the linear programming rounding technique, we propose a (2k + 1)-approximation algorithm for this problem.
In this work, we consider the Submodular Maximization under Knapsack (SMK) constraint problem over the ground set of size n. The problem recently attracted a lot of attention due to its applications in various domains...
详细信息
In this work, we consider the Submodular Maximization under Knapsack (SMK) constraint problem over the ground set of size n. The problem recently attracted a lot of attention due to its applications in various domains of combinatorial optimization, artificial intelligence, and machine learning. We improve the approximation factor of the fastest deterministic algorithm from 6+& varepsilon;to 5+& varepsilon;while keeping the best query complexity of O(n), where & varepsilon;>0 is a constant parameter. Our technique is based on optimizing the performance of two components: the threshold greedy subroutine and the building of two disjoint sets as candidate solutions. Besides, by carefully analyzing the cost of candidate solutions, we obtain a tighter approximation factor.
A long-standing conjecture for the traveling salesman problem (TSP) states that the integrality gap of the standard linear programming relaxation of the TSP (sometimes called the Subtour LP or the Held-Karp bound) is ...
详细信息
A long-standing conjecture for the traveling salesman problem (TSP) states that the integrality gap of the standard linear programming relaxation of the TSP (sometimes called the Subtour LP or the Held-Karp bound) is at most 4/3 for symmetric instances of the TSP obeying the triangle inequality;that is, the cost of an optimal tour is at most 4/3 times the value of the value of the corresponding linear program. There is a variety of evidence in support of the conjecture (see, for instance, Goemans in Math Program 69:335-349, 1995;Benoit and Boyd in Math Oper Res 33:921-931, 2008). It has long been known that the integrality gap is at most 3/2 (Wolsey in Math Program Study 13:121-134, 1980;Shmoys and Williamson in Inf Process Lett 35:281-285, 1990). Despite significant efforts by the community, the conjecture remains open. In this paper we consider the half-integral case, in which a feasible solution to the LP has solution values in {0,1/2,1}. Such instances have been conjectured to be the most difficult instances for the overall four-thirds conjecture (Schalekamp et al. in Math Oper Res 39(2):403-417, 2014). Karlin et al. (in: Proceedings of the 52nd Annual ACM Symposium on the the Theory of Computing, ACM, New York, 2020), in a breakthrough result, were able to show that in the half-integral case, the integrality gap is at most 1.49993;Gupta et al. (in: Integer Programming and Combinatorial Optimization. Lecture Notes in Computer Science, 2022. https://***/abs/2111.09290) showed a slight improvement of this result to 1.4983. Additionally, this result led to the first significant progress on the overall conjecture in decades;the same authors showed the integrality gap of the Subtour LP is at most 1.5-& varepsilon;for some & varepsilon;>10(-36) Karlin et al. in 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS). https://***/10.1109/FOCS54457.2022.00084. With the improvements on the 3/2 bound remaining very incremental, even in the half
We investigate k-level squared metric facility location problem with outli-ers (k-SMFLPWO) for any constant k. In k-SMFLPWO, given k facilities set F-l , where l is an element of {1,2,& ctdot;,k} , clients set C w...
详细信息
We investigate k-level squared metric facility location problem with outli-ers (k-SMFLPWO) for any constant k. In k-SMFLPWO, given k facilities set F-l , where l is an element of {1,2,& ctdot;,k} , clients set C with cardinality n and a non-negative integer qapproximation algorithm and the property of squared metric triangle inequality, we present a constant factor approximation algorithm for k-SMFLPWO.
We reconsider the min-max clustered cycle cover (MM-CCC) problem, which is described as follows. Given an undirected complete graph G = (V, E;w ) with a positive integer k , where the vertex set V is partitioned into ...
详细信息
We reconsider the min-max clustered cycle cover (MM-CCC) problem, which is described as follows. Given an undirected complete graph G = (V, E;w ) with a positive integer k , where the vertex set V is partitioned into h clusters V 1 , ... , V h , and w : E -> & Ropf;+ is an edge-weight function satisfying the triangle inequality, it is asked to find k cycles such that they traverse all vertices and the vertices in each cluster are required to be traversed consecutively. The objective is to minimize the weight of the maximum weight cycle. We propose a strongly polynomial time 16- approximation algorithm for the MM-CCC problem. The result improves the previous algorithm in terms of running time.
Path cover is one of the well-known NP-hard problems that has received much attention. In this paper, we study a variant of path cover, denoted by MPCv4+, to cover as many vertices in a given graph G=(V,E) as possible...
详细信息
Path cover is one of the well-known NP-hard problems that has received much attention. In this paper, we study a variant of path cover, denoted by MPCv4+, to cover as many vertices in a given graph G=(V,E) as possible by a collection of vertex-disjoint paths each of order four or above. The problem admits an existing O(vertical bar V vertical bar(8))-time 2-approximation algorithm by applying several time-consuming local improvement operations (Gong et al.: Proceedings of MFCS 2022, LIPIcs 241, pp 53:1-53:14, 2022). In contrast, our new algorithm uses a completely different method and it is an improved O(min{|E|(2)|V|(2),|V|(5)})-time 1.874-approximation algorithm, which answers the open question in Gong et al. (2022) in the affirmative. An important observation leading to the improvement is that the number of vertices in a maximum matching M of G is relatively large compared to that in an optimal solution of MPCv4+. Our new algorithm forms a feasible solution of MPCv4+ from a maximum matching M by computing a maximum-weight path-cycle cover in an auxiliary graph to connect as many edges in M as possible.
We consider the Max Directed 3-Section problem, which is closely connected to other well-known graph partition problems, such as Max Cut and Max Bisection. Given an arc-weighted directed graph, the goal of the Max Dir...
详细信息
We consider the Max Directed 3-Section problem, which is closely connected to other well-known graph partition problems, such as Max Cut and Max Bisection. Given an arc-weighted directed graph, the goal of the Max Directed 3-Section problem is to partition the vertex set into three disjoint subsets with equal size, while maximizing the total weight of arcs crossing different vertex subsets. By combining the Lasserre hierarchy with the random hyperplane rounding strategy, we propose a polynomial-time algorithm with approximation ratio of 0.489.
In minimum power network design problems we are given an undirected graph G = (V, E) with edge costs {c(e) :e is an element of E}. The goal is to find an edge set F subset of E that satisfies S a prescribed property o...
详细信息
In minimum power network design problems we are given an undirected graph G = (V, E) with edge costs {c(e) :e is an element of E}. The goal is to find an edge set F subset of E that satisfies S a prescribed property of minimum power p(c) (F) = Sigma(upsilon is an element of V) max{c(e) :e is an element of F is incident to upsilon}. In the MIN-POWER k EDGE DISJOINT st-PATHS problem F should contain k edge disjoint st-paths. The problem admits a k-approximation algorithm, and it was an open question to achieve an approximation ratio sublinear in k for simple graphs, even for unit costs. We give a 2 root 2k-approximation algorithm for general costs.
暂无评论