In the k-level uncapacitated facility location problem, we have a set of demand points where clients are located. The demand of each client is known. Facilities have to be located at given sites in order to service th...
详细信息
In the k-level uncapacitated facility location problem, we have a set of demand points where clients are located. The demand of each client is known. Facilities have to be located at given sites in order to service the clients, and each client is to be serviced by a sequence of k different facilities, each of which belongs to a distinct level. There are no capacity restrictions on the facilities. There is a positive fixed cost of setting up a facility, and a per unit cost of shipping goods between each pair of locations. We assume that these distances are all nonnegative and satisfy the triangle inequality. The problem is to find an assignment of each client to a sequence of k facilities, one at each level, so that the demand of each client is satisfied, for which the sum of the setup costs and the service costs is minimized. We develop a randomized algorithm for the k-level facility location problem that is guaranteed to find a feasible solution of expected cost within a factor of 3 of the optimum cost. The algorithm is a randomized rounding procedure that uses an optimal solution of a linear programming relaxation and its dual to make a random choice of facilities to be opened. We show how this algorithm can be derandomized to yield a 3-approximation algorithm. (C) 1999 Elsevier Science B.V. All rights reserved.
In this paper, we design a 2-approximation algorithm for the parallel-machine customer order scheduling with delivery time and submodular rejection penalties based on Lovasz rounding technique, which improves the corr...
详细信息
In this paper, we design a 2-approximation algorithm for the parallel-machine customer order scheduling with delivery time and submodular rejection penalties based on Lovasz rounding technique, which improves the corresponding result obtained in Zheng et al. (J. Oper. Res. Soc. China, 2022).
In this paper, we introduce a squared metric k-facility location problem (SM-k-FLP) which is a generalization of the squared metric facility location problem and k-facility location problem (k-FLP). In the SM-k-FLP, w...
详细信息
In this paper, we introduce a squared metric k-facility location problem (SM-k-FLP) which is a generalization of the squared metric facility location problem and k-facility location problem (k-FLP). In the SM-k-FLP, we are given a client set and a facility set from a metric space, a facility opening cost for each , and an integer k. The goal is to open a facility subset with and to connect each client to the nearest open facility such that the total cost (including facility opening cost and the sum of squares of distances) is minimized. Using local search and scaling techniques, we offer a constant approximation algorithm for the SM-k-FLP.
We give a (1-1/e)-approximation algorithm for the may-profit generalized assignment problem (Max-GAP) with fixed profits when the profit (but not necessarily the size) of every item is independent from the bin it is a...
详细信息
We give a (1-1/e)-approximation algorithm for the may-profit generalized assignment problem (Max-GAP) with fixed profits when the profit (but not necessarily the size) of every item is independent from the bin it is assigned to. The previously best-known approximation ratio for this problem was 1/2. (c) 2005 Elsevier B.V. All rights reserved.
We derive a 3/2-approximation algorithm for the NP-hard parallel machine total weighted completion time problem with controllable processing times by the technique of convex quadratic programming relaxation. (C) 2001 ...
详细信息
We derive a 3/2-approximation algorithm for the NP-hard parallel machine total weighted completion time problem with controllable processing times by the technique of convex quadratic programming relaxation. (C) 2001 Elsevier Science B.V. All rights reserved.
Although, the Hamiltonicity of solid grid graphs are polynomial-time decidable, the complexity of the longest cycle problem in these graphs is still open. In this paper, by presenting a linear-time constant-factor app...
详细信息
Although, the Hamiltonicity of solid grid graphs are polynomial-time decidable, the complexity of the longest cycle problem in these graphs is still open. In this paper, by presenting a linear-time constant-factor approximation algorithm, we show that the longest cycle problem in solid grid graphs is in APX. More precisely, our algorithm finds a cycle of length at least 2n/3 + 1 in 2-connected n-node solid grid graphs. (C) 2015 Elsevier B.V. All rights reserved.
A subset F of vertices of a graph G is called a vertex cover P-k set if every path of order k in G contains at least one vertex from F. Denote by psi(k)(G) the minimum cardinality of a vertex cover P-k set in G. The v...
详细信息
A subset F of vertices of a graph G is called a vertex cover P-k set if every path of order k in G contains at least one vertex from F. Denote by psi(k)(G) the minimum cardinality of a vertex cover P-k set in G. The vertex cover P-k (VCPk) problem is to find a minimum vertex cover P-k set. It is easy to see that the VCP2 problem corresponds to the well-known vertex cover problem. In this paper, we restrict our attention to the VCP4 problem in cubic graphs. The paper proves that the VCP4 problem is NP-hard for cubic graphs. Further, we give sharp lower and upper bounds on psi(4)(G) for cubic graphs and propose a 2-approximation algorithm for the VCP4 problem in cubic graphs.
For a time-sensitive application, the usefulness of its end results (also called the application's accrued utility value in the paper) depends on the time when the application is completed and its results are deli...
详细信息
For a time-sensitive application, the usefulness of its end results (also called the application's accrued utility value in the paper) depends on the time when the application is completed and its results are delivered. In this paper, we address the accrued utility value maximization problem for narrow parallel and time-sensitive applications. We first consider the problem in the context of a discrete time domain and present the Spatial-Temporal Interference Based (STIB) scheduling algorithm. We formally prove that the STIB algorithm is a 2-approximation algorithm. Second, we extend our work to a continuous time domain and present a heuristic scheduling algorithm, i.e., the Continuous Spatial-Temporal Interference Based (STIB-C) algorithm to maximize the system's total accrued utility value when the system operates in a continuous time domain. The extensive empirical evaluations reveal that: (1) in a discrete time domain, the systems' total accrued utility values obtained through the STIB algorithm are consistent with the theoretic bound, i.e., they never go below 50 percent of the optimal value. In fact, on average, the STIB algorithm can achieve over 92.5 percent of the optimal value;(2) compared to other scheduling policies listed in the literature, the developed STIB and STIB-C algorithms have clear advantages in terms of the system's total accrued utility value and the profitable application ratio. In particular, in terms of the system's total accrued utility value, both the STIB and the STIB-C algorithms achieve as much as six times for both the First Come First Come Serve(FCFS) with backfilling algorithm and the Gang Earliest Deadline First (EDF) algorithm, and 4.5 times for the 0-1 Knapsack based scheduling algorithm. In terms of the profitable application ratio, both the STIB and the STIB-C algorithms obtain as much as four times for both the FCFS with backfilling algorithm and the Gang EDF algorithm, and two times for the 0-1 Knapsack based scheduling algo
It is well-known that the multiple knapsack problem is NP-hard, and does not admit an FPTAS even for the case of two identical knapsacks. Whereas the 0-1 knapsack problem with only one knapsack has been intensively st...
详细信息
It is well-known that the multiple knapsack problem is NP-hard, and does not admit an FPTAS even for the case of two identical knapsacks. Whereas the 0-1 knapsack problem with only one knapsack has been intensively studied, and some effective exact or approximation algorithms exist. A natural approach for the multiple knapsack problem is to pack the knapsacks successively by using an effective algorithm for the 0-1 knapsack problem. This paper considers such an approximation algorithm that packs the knapsacks in the nondecreasing order of their capacities. We analyze this algorithm for 2 and 3 knapsack problems by the worst-case analysis method and give all their error bounds.
Modifying the topology of a network to mitigate the spread of an epidemic with epidemiological constant. amounts to the NP-hard problem of finding a partial subgraph with maximum number of edges and spectral radius bo...
详细信息
Modifying the topology of a network to mitigate the spread of an epidemic with epidemiological constant. amounts to the NP-hard problem of finding a partial subgraph with maximum number of edges and spectral radius bounded above by.. A software-defined network capable of real-time topology reconfiguration can then use an algorithm for finding such subgraph to quickly remove spreading malware threats without deploying specific security countermeasures. In this paper, we propose a novel randomized approximation algorithm based on the relaxation and rounding framework that achieves a O(log n) approximation in the case of finding a subgraph with spectral radius bounded by.. [log n,.1(G)) where.1(G) is the spectral radius of the input graph and n is the number of nodes. We combine this algorithm with a maximum matching algorithm to obtain a O(log2 n)-approximation algorithm for all values of.. We also describe how the mathematical programming formulation we give has several advantages over previous approaches which attempted at finding a subgraph with minimum spectral radius given an edge removal budget. Finally, we show that the analysis of our randomized rounding scheme is essentially tight by relating it to classical results from random graph theory.
暂无评论