In this paper we present a 1.52-approximation algorithm for the metric uncapacitated facility location problem, and a 2-approximation algorithm for the metric capacitated facility location problem with soft capacities...
详细信息
In this paper we present a 1.52-approximation algorithm for the metric uncapacitated facility location problem, and a 2-approximation algorithm for the metric capacitated facility location problem with soft capacities. Both these algorithms improve the best previously known approximation factor for the corresponding problem, and our soft-capacitated facility location algorithm achieves the integrality gap of the standard linear programming relaxation of the problem. Furthermore, we will show, using a result of Thorup, that our algorithms can be implemented in quasi-linear time.
Motivated by the Steiner tree problem with minimum number of Steiner points and bounded edge-length in [4], we consider the problem of constructing specific subgraph with minimum number of length-bounded stock pieces ...
详细信息
Motivated by the Steiner tree problem with minimum number of Steiner points and bounded edge-length in [4], we consider the problem of constructing specific subgraph with minimum number of length-bounded stock pieces (CSS-MSP, for short), which is defined as follows. In some constructing specific subgraph problem Q (CSS, for short), the objective is to choose a minimum-length subset of edges, such that these edges form a specific subgraph (such as a spanning tree or a Steiner tree). In the CSS-MSP problem Q', these edges are further required to be cut from some stock pieces of length L, and the new objective, however, is to minimize the number of stock pieces of length L to construct all edges in such a specific subgraph. We obtain two main results. (1) Whenever the CSS problem Q can be approximated by an alpha-approximation algorithm (alpha >= 1) (for the case alpha = 1, the CSS problem Q is solved optimally by a polynomial-time exact algorithm), we design two approximation algorithms with performance ratios 2 alpha and 7 alpha/4 to solve the CSS-MSP problem Q';(2) In addition, when the problem Q is to find a minimum spanning tree, we present a 3/2-approximation algorithm and an APTAS to solve the problem Q' of constructing spanning tree with minimum number of length-bounded stock pieces. (C) 2018 Elsevier B.V. All rights reserved.
We study the problems of pricing an indivisible product to consumers who are embedded in a given social network. The goal is to maximize the revenue of the seller by the so-called iterative pricing that offers consume...
详细信息
We study the problems of pricing an indivisible product to consumers who are embedded in a given social network. The goal is to maximize the revenue of the seller by the so-called iterative pricing that offers consumers a sequence of prices over time. The consumers are assumed to be impatient in that they buy the product as soon as the seller posts a price not greater than their valuations of the product. The product's value for a consumer is determined by two factors: a fixed consumer-specified intrinsic value and a variable externality that is exerted from the consumer's neighbors in a linear way. We focus on the scenario of negative externalities, which captures many interesting situations, but is much less understood in comparison with its positive externality counterpart. Assuming complete information about the network, consumers' intrinsic values, and the negative externalities, we prove that it is NP-hard to find an optimal iterative pricing, even for unweighted tree networks with uniform intrinsic values. Complementary to the hardness result, we design a 2-approximation algorithm for general weighted networks with (possibly) nonuniform intrinsic values. We show that, as an approximation to optimal iterative pricing, single pricing works fairly well for many interesting cases, such as forests, ErdAs-R,nyi networks and Barabasi-Albert networks, although its worst-case performance can be arbitrarily bad in general networks.
In the minimum-cost k-(S, T) connected digraph (abbreviated as k-(S, T) connectivity) problem we are given a positive integer k, a directed graph G = (V, E) with nonnegative costs on the edges, and two subsets S, T of...
详细信息
In the minimum-cost k-(S, T) connected digraph (abbreviated as k-(S, T) connectivity) problem we are given a positive integer k, a directed graph G = (V, E) with nonnegative costs on the edges, and two subsets S, T of V;the goal is to find a subset of edges (E) over cap of minimum cost such that the subgraph (V, (E) over cap) has k edge-disjoint directed paths from each vertex in S to each vertex in T. Most of our results focus on a specialized version of the problem that we call the standard version, where every edge of positive cost has its tail in S and its head in T. This version of the problem captures NP-hard problems such as the minimum-cost k-vertex connected spanning subgraph problem. We give an approximation algorithm with a guarantee of O((log k)(log n)) for the standard version of the k-(S, T) connectivity problem, where n denotes the number of vertices. For k = 1, we give a simple 2-approximation algorithm that generalizes a well-known 2-approximation algorithm for the minimum-cost strongly connected spanning subgraph problem. For k = 2, we give a 3-approximation algorithm;this matches the best approximation guarantee known for the special case of the minimum-cost 2-vertex connected spanning subgraph problem. Besides the standard version, we study another version that is intermediate between the standard version and the problem in its full generality. In the relaxed version of the (S, T) connectivity problem, each edge of positive cost has its head in T but there is no restriction on the tail. We study the relaxed version with the connectivity parameter k fixed at one and observe that this version is at least as hard to approximate as the directed Steiner tree problem. We match this by giving an algorithm that achieves an approximation guarantee of alpha(n)+1 for the relaxed (S, T) connectivity problem, where alpha(n) denotes the best approximation guarantee available for the directed Steiner tree problem. The key to the analysis is a structural result
In this paper, we prove that the Max Morse Matching Problem is approximable, thus resolving an open problem posed by Joswig and Pfetsch [1]. For D-dimensional simplicial complexes, we obtain a (D+1)/(D-2+D+1)-factor a...
详细信息
In this paper, we prove that the Max Morse Matching Problem is approximable, thus resolving an open problem posed by Joswig and Pfetsch [1]. For D-dimensional simplicial complexes, we obtain a (D+1)/(D-2+D+1)-factor approximation ratio using a simple edge reorientation algorithm that removes cycles. For D >= 5, we describe a 2/D-factor approximation algorithm for simplicial manifolds by processing the simplices in increasing order of dimension. This algorithm leads to 1/2-factor approximation for 3-manifolds and 4/9-factor approximation for 4-manifolds. This algorithm may also be applied to non-manifolds resulting in a 1/(D+1)-factor approximation ratio. One application of these algorithms is towards efficient homology computation of simplicial complexes. Experiments using a prototype implementation on several datasets indicate that the algorithm computes near optimal results. (C) 2016 Elsevier B.V. All rights reserved.
We study the approximability of minimum total weighted tardiness with a modified objective which includes an additive constant. This ensures the existence of a positive lower bound for the minimum value. Moreover the ...
详细信息
We study the approximability of minimum total weighted tardiness with a modified objective which includes an additive constant. This ensures the existence of a positive lower bound for the minimum value. Moreover the new objective has a natural interpretation in just-in-time production systems. (C) 2007 Elsevier B.V. All rights reserved.
Sorting by Genome Rearrangements is a classic problem in Computational Biology. Several models have been considered so far, each of them defines how a genome is modeled (for example, permutations when assuming no dupl...
详细信息
Sorting by Genome Rearrangements is a classic problem in Computational Biology. Several models have been considered so far, each of them defines how a genome is modeled (for example, permutations when assuming no duplicated genes, strings if duplicated genes are allowed, and/or use of signs on each element when gene orientation is known), and which rearrangements are allowed. Recently, a new problem, called Sorting by Multi-Cut Rearrangements, was proposed. It uses the k-cut rearrangement which cuts a permutation (or a string) at k >= 2 places and rearranges the generated blocks to obtain a new permutation (or string) of same size. This new rearrangement may model chromoanagenesis, a phenomenon consisting of massive simultaneous rearrangements. Similarly as the Double-Cut-and-Join, this new rearrangement also generalizes several genome rearrangements such as reversals, transpositions, revrevs, transreversals, and block-interchanges. In this paper, we extend a previous work based on unsigned permutations and strings to signed permutations. We show the complexity of this problem for different values of k, and that the approximation algorithm proposed for unsigned permutations with any value of k can be adapted to signed permutations. We also show a 1.5-approximation algorithm for the specific case k = 4, as well as a generic approximation algorithm applicable for any k >= 5, that always reaches constant ratio. The latter makes use of the cycle graph, a well-known structure in genome rearrangements. We implemented and tested the proposed algorithms on simulated data.
The time-dependent orienteering problem is dual to the time-dependent traveling salesman problem. It consists of visiting a maximum number of sites within a given deadline. The traveling time between two sites is in g...
详细信息
The time-dependent orienteering problem is dual to the time-dependent traveling salesman problem. It consists of visiting a maximum number of sites within a given deadline. The traveling time between two sites is in general dependent on the starting time. For any epsilon > 0, we provide a (2 + epsilon)-approximation algorithm for the time-dependent orienteering problem which runs in polynomial time if the ratio between the maximum and minimum traveling time between any two sites is constant. No prior upper approximation bounds were known for this time-dependent problem. (C) 2001 Elsevier Science B.V. All rights reserved.
In this paper, we address the trip-constrained vehicle routing cover problem (theTcVRC problem). Specifically, given a metric complete graphG=(V,E;w)with a set D(subset of V)of depots, a setJ(=V\D)of customer location...
详细信息
In this paper, we address the trip-constrained vehicle routing cover problem (theTcVRC problem). Specifically, given a metric complete graphG=(V,E;w)with a set D(subset of V)of depots, a setJ(=V\D)of customer locations, each customerhaving unsplittable demand 1, andkvehicles with capacityQ, it is asked to find a setC={C-i|=1,2,...,k}ofktours forkvehicles to service all customers, each tourfor a vehicle starts and ends at one depot inDand permits to be replenished at someother depots inDbefore continuously servicing at mostQcustomers, i.e., the numberof customers continuously serviced in per trip of each tour is at mostQ(except thetwo end-vertices of that trip), where each trip is a path or cycle, starting at a depot andending at other depot (maybe the same depot) inD, such that there are no other depotsin the interior of that path or cycle, the objective is to minimize the maximum weightof suchktours inC, i.e., minCmax{w(C-i)|i=1,2,...,k}, wherew(Ci)is thetotal weight of edges in that tourCi. Consideringkvehicles whether to have commondepot or suppliers, we consider three variations of the TcVRC problem, i.e., (1) the trip-constrained vehicle routing cover problem with multiple suppliers (the TcVRC-MSproblem) is asked to find a setC={Ci|i=1,2,...,k}ofktours mentioned-above,the objective is to minimize the maximum weight of suchktours inC;(2) the trip-constrained vehicle routing cover problem with common depot and multiple suppliers(the TcVRC-CDMS problem) is asked to find a setC={Ci|i=1,2,...,k}ofk tours mentioned-above, where each tour starts and ends at same depotvinD, eachvehicle having its suppliers at some depots inD(possibly includingv), the objectiveis to minimize the maximum weight of suchktours inC;(3) the trip-constrainedk-traveling salesman problem with non-suppliers (the TckTS-NS problem, simply theTckTSP-NS) is asked to find a setC={C-i=1,2,...,k}of k tours mentioned-above, where each tour starts and ends at same depotvinD, each vehicle havingnon-suppli
In the weighted rectangle stabbing problem we are given a grid in R-2 consisting of columns and rows each having a positive integral weight, and a set of closed axis-parallel rectangles each having a positive integral...
详细信息
In the weighted rectangle stabbing problem we are given a grid in R-2 consisting of columns and rows each having a positive integral weight, and a set of closed axis-parallel rectangles each having a positive integral demand. The rectangles are placed arbitrarily in the grid with the only assumption being that each rectangle is intersected by at least one column or row. The objective is to find a minimum-weight (multi) set of columns and rows of the grid so that for each rectangle the total multiplicity of selected columns and rows stabbing it is at least its demand. A special case of this problem, called the interval stabbing problem, arises when each rectangle is intersected by exactly one row. We describe an algorithm called STAB, which is shown to be a constant-factor approximation algorithm for different variants of this stabbing problem.
暂无评论