Partial set cover problem and set multi-cover problem are two generalizations of the set cover problem. In this paper, we consider the partial set multi-cover problem which is a combination of them: given an element s...
详细信息
Partial set cover problem and set multi-cover problem are two generalizations of the set cover problem. In this paper, we consider the partial set multi-cover problem which is a combination of them: given an element set E, a collection of sets S subset of 2(E), a total covering ratio q, each set S is an element of S is associated with a cost c(S), each element e is an element of E is associated with a covering requirement re, the goal is to find a minimum cost sub-collection S' subset of S to fully cover at least q vertical bar E vertical bar elements, where element e is fully covered if it belongs to at least r(e) sets of S'. Denote by r(max) = max{r(e) : e is an element of E} the maximum covering requirement. We present an (O(r(max) log(2) n(1+ ln(1/epsilon) + 1-q/epsilon q)), 1 - epsilon)-bicriteria approximation algorithm, that is, the output of our algorithm has cost O(r(max) log(2) n(1+ ln(1/epsilon) + 1-q/epsilon q)) times of the optimal value while the number of fully covered elements is at least (1 - epsilon)q vertical bar E vertical bar.
We study a scenario-based stochastic and prize-collecting version of the set multicover problem, where there is uncertainty about a demand for each element to be covered and the penalty cost is imposed linearly on the...
详细信息
We study a scenario-based stochastic and prize-collecting version of the set multicover problem, where there is uncertainty about a demand for each element to be covered and the penalty cost is imposed linearly on the shortfall in each demand. This problem is NP-hard and has an application in shift scheduling in crowdsourced delivery services. For this problem, we present an LP-based O(ln n)-approximation algorithm, where n is the number of elements to be covered. (C) 2022 Elsevier B.V. All rights reserved.
We present a new polynomial-time heuristic algorithm for finding a solution to the Traveling Salesman Problem (TSP) for any complete and edge-weighted graph K sub(n), with a set of vertices V and a set of edges E wher...
详细信息
We present a new polynomial-time heuristic algorithm for finding a solution to the Traveling Salesman Problem (TSP) for any complete and edge-weighted graph K sub(n), with a set of vertices V and a set of edges E where !V! = n. In a few words, this method is based on the idea of linking the elements of V progressively, one by one, in such a way that the vertex selection which produces fewest disturbances to the other vertices not yet connected, will be selected as the next vertex to join to the subset of already connected vertices. When the cost of the result is compared to the cost of the best circuit, it appears that a good sub-solution is obtained in most of the cases tested. Moreover, comparison tests made between the heuristic introduced and the well-known Quick method, produce a better behaviour, for almost every case, in the first approach.
In this paper, we consider a variant of the classical uncapacitated facility location problem, so-called squared metric two-stage stochastic facility location problem (SM-2-SFLP) which can treat the uncertainty of the...
详细信息
In this paper, we consider a variant of the classical uncapacitated facility location problem, so-called squared metric two-stage stochastic facility location problem (SM-2-SFLP) which can treat the uncertainty of the set of clients and facility costs. We assume that the connection cost is squared metric, a variant of the metric case which is widely researched. We give a new 0-1 integer linear programming for SM-2-SFLP. Based on the new formulation, we apply two known algorithms to SM-2-SFLP, and analyze the approximation ratio and per-scenario bound respectively.
作者：
Liu, SudingYunnan Univ
Sch Math & Stat Kunming 650504 Peoples R China Univ Waterloo
David R Cheriton Sch Comp Sci Waterloo ON N2L 3G1 Canada
We address the 1-line Steiner tree problem with minimum number of Steiner points. Given a line l, a point set P of n terminals in R-2 and a positive constant K, we are asked to find a Steiner tree T-l to interconnect ...
详细信息
We address the 1-line Steiner tree problem with minimum number of Steiner points. Given a line l, a point set P of n terminals in R-2 and a positive constant K, we are asked to find a Steiner tree T-l to interconnect the line l and the n terminals such that the Euclidean length of each edge in T-l is no more than the given positive constant K except those connecting two points on the line l, the objective is to minimize total number of the Steiner points in T-l, i.e. min T-l {vertical bar S-out vertical bar + vertical bar S-on vertical bar}, where vertical bar S-out vertical bar and vertical bar S-on vertical bar are the number of Steiner points located outside of the line l and on this line l, respectively. We design a 4-approximation algorithm with time complexity of O(n(3)) for the 1-line Steiner tree problem with minimum number of Steiner points.
In this paper, we study the minimum (connected) k-bounded-degree node deletion problem (Min(C)kBDND). For a connected graph G, a constant k and a weight function w : V -> R+, a vertex set C subset of V (G) is a kBD...
详细信息
In this paper, we study the minimum (connected) k-bounded-degree node deletion problem (Min(C)kBDND). For a connected graph G, a constant k and a weight function w : V -> R+, a vertex set C subset of V (G) is a kBDND-set if the maximum degree of graph G - C is at most k. If furthermore, the subgraph of G induced by C is connected, then C is a CkBDND-set. The goal of MinWkBDND (resp. MinWCkBDND) is to find a kBDND-set (resp. CkBDND-set) with the minimum weight. In this paper, we focus on their cardinality versions with w(v) equivalent to 1, v is an element of V, which are denoted as MinkBDND and MinCkBDND. This paper presents a (1 + epsilon) and a 3.76-approximation algorithm for MinkBDND and MinCkBDND on unit disk graphs, respectively, where 0 < epsilon <1 is an arbitrary constant. (C) 2020 Published by Elsevier B.V.
We consider the problem of partitioning a finite sequence of Euclidean points into a given number of clusters (subsequences) using the criterion of the minimal sum (over all clusters) of intercluster sums of squared d...
详细信息
We consider the problem of partitioning a finite sequence of Euclidean points into a given number of clusters (subsequences) using the criterion of the minimal sum (over all clusters) of intercluster sums of squared distances from the elements of the clusters to their centers. It is assumed that the center of one of the desired clusters is at the origin, while the center of each of the other clusters is unknown and determined as the mean value over all elements in this cluster. Additionally, the partition obeys two structural constraints on the indices of sequence elements contained in the clusters with unknown centers: (1) the concatenation of the indices of elements in these clusters is an increasing sequence, and (2) the difference between an index and the preceding one is bounded above and below by prescribed constants. It is shown that this problem is strongly NP-hard. A 2-approximation algorithm is constructed that is polynomial-time for a fixed number of clusters.
The problem of diagnostic test scheduling (DTS) is to assign to each edge e of a diagnostic graph G a time interval of length l(e) so that intervals corresponding to edges at any given vertex do not overlap and the ov...
详细信息
The problem of diagnostic test scheduling (DTS) is to assign to each edge e of a diagnostic graph G a time interval of length l(e) so that intervals corresponding to edges at any given vertex do not overlap and the overall finishing time is minimum. In this correspondence we show that the DTS problem is NP-complete. Then we present a longest, first sequential scheduling algorithm which runs in worst case time O(dm log n) and uses O(m) space to produce a solution of length less than four times optimal. Then we show that the general performance bound can be strengthened to 3 * OPT(G) for low-degree graphs and to 2 ·OPT(G) in some special cases of binomial diagnostic graphs.
In this paper, we study the uncapacitated facility location problem with service installation costs depending on the type of service required. We propose a polynomial-time approximation algorithm with approximation ra...
详细信息
In this paper, we study the uncapacitated facility location problem with service installation costs depending on the type of service required. We propose a polynomial-time approximation algorithm with approximation ratio 1.808 which improves the previous approximation ratio of 2.391 of Shmoys, Swamy, and Levi. (c) 2007 Elsevier B.V. All rights reserved.
Using outward rotations, we obtain an approximation algorithm for Max-Bisection problem, i.e., partitioning the vertices of an undirected graph into two blocks of equal cardinality so as to maximize the weights of cro...
详细信息
Using outward rotations, we obtain an approximation algorithm for Max-Bisection problem, i.e., partitioning the vertices of an undirected graph into two blocks of equal cardinality so as to maximize the weights of crossing edges. In many interesting cases, the algorithm performs better than the algorithms of Ye and of Halperin and Zwick. The main tool used to obtain this result is semidefinite programming.
暂无评论