We consider the problem of releasing multiple types of jobs to a facility over a fixed period. In the problem, each type of job has its own demand for the period and the daily capacity of the facility can fluctuate. T...
详细信息
We consider the problem of releasing multiple types of jobs to a facility over a fixed period. In the problem, each type of job has its own demand for the period and the daily capacity of the facility can fluctuate. The variability of each type is defined as the total absolute deviation between the number of jobs of the corresponding type released on consecutive days. The objective is to minimize the total variability over all types. We show that the problem is strongly NP-hard. In addition, we develop an approximation algorithm and analyze its approximability according to the level of fluctuation of the daily capacity. (C) 2012 Elsevier B.V. All rights reserved.
Different from the classical k-means problem, the functional k means problem involves a kind of dynamic data, which is generated by continuous processes. In this paper, we mainly design an O(ln k)-approximation algori...
详细信息
Different from the classical k-means problem, the functional k means problem involves a kind of dynamic data, which is generated by continuous processes. In this paper, we mainly design an O(ln k)-approximation algorithm based on the seeding method for functional k-means problem. Moreover, the numerical experiment presented shows that this algorithm is more efficient than the functional k-means clustering algorithm.
This paper studies approximation algorithm for the maximum weight budgeted connected set cover (MWBCSC) problem. Given an element set , a collection of sets , a weight function on , a cost function on , a connected gr...
详细信息
This paper studies approximation algorithm for the maximum weight budgeted connected set cover (MWBCSC) problem. Given an element set , a collection of sets , a weight function on , a cost function on , a connected graph (called communication graph) on vertex set , and a budget , the MWBCSC problem is to select a subcollection such that the cost , the subgraph of induced by is connected, and the total weight of elements covered by (that is ) is maximized. We present a polynomial time algorithm for this problem with a natural communication graph that has performance ratio , where is the maximum degree of graph and is the number of sets in . In particular, if every set has cost at most , the performance ratio can be improved to .
There is an error in our paper "An approximation algorithm fur Minimum-Cost Vertex-Connectivity Problems" (algorithmica (1997), 18:21-43). In that paper we considered the following problem: given an undirect...
详细信息
There is an error in our paper "An approximation algorithm fur Minimum-Cost Vertex-Connectivity Problems" (algorithmica (1997), 18:21-43). In that paper we considered the following problem: given an undirected graph and values r(ij) for each pair of vertices i and j, find a minimum-cost set of edged, such that there are r(ij) vertex-disjoint paths between vertices i and j. We gave approximation algorithms for two special cases of this problem. Our algorithms rely on a primal-dual approach which has led to approximation El algorithms for many edge-connectivity problems, The algorithms work in a series of stages;in each stage an augmentation subroutine augments the connectivity of the current solution. The error is in a lemma for the proof of the performance guarantee of the augmentation subroutine. In the case r(ij) = k for all i, j, we described a polynomial-time algorithm that claimed to output a solution of cost no more than 27-l(k) times optimal, where H(n) 1 + 1/2 + ... + 1/n. This result is erroneous. We describe an example where our primal-dual augmentation subroutine, when augmenting a k-vertex connected graph to a (k + 1)-vertex connected graph, gives solutions that are a factor n (k) away from the minimum, In the case r(ij) is an element of {0, 1, 2} for all i, j, we gave a polynomial-time algorithm which outputs a solution of cost no more than three times the optimal. In this case we prove that the statement in the lemma that was erroneous for the k-vertex connected case does hold, and that the algorithm performs as claimed.
Abstract We study the fleet size and mix vehicle routing problem with constraints on the capacity of each vehicle. The objective is to minimize the total cost including fixed utilization cost of vehicles and traveling...
详细信息
Abstract We study the fleet size and mix vehicle routing problem with constraints on the capacity of each vehicle. The objective is to minimize the total cost including fixed utilization cost of vehicles and traveling cost by vehicles. We give differential approximation algorithms for the fleet size and mix vehicle routing problem （FSMVRP） with two kinds of vehicles, the capacities of which are respectively nlk and n2k, n2 〉 nl ≥ 1, k ≥ 1. Using existing theories for vehicle routing problems and feature of the algorithms represented in the paper, we also prove that the algorithms give（1-6n＋3/（n＋1）2k＋n＋1）differential approximation ratio for （k, nk） VRP, n 〉 1and （1-6n2＋3n/n1k＋n2k）2k）differential approximation ratio for （nlk, n2k）VRP, n2 〉 nl 〉 1.
In metamodeling, the choice of sampling points is crucial for the quality of the model. In this context, the maximin Latin hypercube designs (LHD), with their space-filling and noncollapsing properties, are particular...
详细信息
In metamodeling, the choice of sampling points is crucial for the quality of the model. In this context, the maximin Latin hypercube designs (LHD), with their space-filling and noncollapsing properties, are particularly efficient. To this day, there is no polynomial time algorithm that produces optimal maximin LHDs, i.e., in which the minimum distance between two points (the separation distance) is maximal. We are interested in LHDs with a separation distance as large as possible. The algorithm we propose, IES, gives an approximate solution to the LHD problem regardless of its dimension and size with a theoretical performance guarantee. We introduce two upper bounds for the separation distance to find its approximation ratio. Its performance is compared with the best metaheuristic algorithm known for this problem, an appropriate simulated annealing scheme. Our algorithm defeats the metaheuristic algorithm for large instances of the problem while having a very short running time.
The minimum vertex ranking spanning tree problem (MVRST) is to find a spanning tree of G whose vertex ranking is minimum. In this paper, we show that MVRST is NP-hard. To prove this, we polynomially reduce the 3-dimen...
详细信息
The minimum vertex ranking spanning tree problem (MVRST) is to find a spanning tree of G whose vertex ranking is minimum. In this paper, we show that MVRST is NP-hard. To prove this, we polynomially reduce the 3-dimensional matching problem to MVRST. Moreover, we present a ([D-s/2] + 1)/([log(2)(D-s + 1)] + 1)-approximation algorithm for MVRST where D-s is the minimum diameter of spanning trees of G. (c) 2006 Elsevier B.V. All rights reserved.
In the uniform capacitated k-facility location problem (UC-k-FLP), we are given a set of facilities and a set of clients. Every client has a demand. Every facility have an opening cost and an uniform capacity. For eac...
详细信息
In the uniform capacitated k-facility location problem (UC-k-FLP), we are given a set of facilities and a set of clients. Every client has a demand. Every facility have an opening cost and an uniform capacity. For each client-facility pair, there is an unit service cost to serve the client with unit demand by the facility. The total demands served by a facility cannot exceed the uniform capacity. We want to open at most k facilities to serve all the demands of the clients without violating the capacity constraint such that the total opening and serving cost is minimized. The main contribution of this work is to present the first combinatorial bi-criteria approximation algorithm for the UC-k-FLP by violating the cardinality constraint.
The uncapacitated facility location problem in the following formulation is considered: max(S subset of or equal to I) Z(S) = Sigma(j is an element of J)max(i is an element of S)b(ij) - Sigma(i is an element of S)c(i)...
详细信息
The uncapacitated facility location problem in the following formulation is considered: max(S subset of or equal to I) Z(S) = Sigma(j is an element of J)max(i is an element of S)b(ij) - Sigma(i is an element of S)c(i), where I and J are finite sets, and b(ij), c(i)greater than or equal to 0 are rational numbers. Let Z* denote the optimal value of the problem and let Z(R) = Sigma(j is an element of J)min(i is an element of I)b(ij) - Sigma(i is an element of I)c(i). Cornuejols et al. (Ann. Discrete Math. 1 (1977) 163-178) prove that for the problem with the additional cardinality constraint \S\less than or equal to K, a simple greedy algorithm finds a feasible solution S such that (Z(S) - ZR)/(Z* - ZR)greater than or equal to 1 - e(-1) approximate to 0.632. We suggest a polynomial-time approximation algorithm for the unconstrained version of the problem, based on the idea of randomized rounding due to Goemans and Williamson (SIAM J. Discrete Math. 7 (1994) 656 - 666). It is proved that the algorithm delivers a solution S such that (Z(S) - Z(R))/(Z* - Z(R))greater than or equal to 2(root 2 - 1) approximate to 0.828. We also show that there exists epsilon > 0 such that it is NP-hard to find an approximate solution S with (Z(S) - Z(R))/(Z* - Z(R))greater than or equal to 1 - epsilon. (C) 1999 Elsevier Science B.V. All rights reserved.
This paper studies a multi-agent scheduling problem on two identical parallel machines. There are g agents, and each agent's objective is to minimize its makespan. We present an approximation algorithm such that t...
详细信息
This paper studies a multi-agent scheduling problem on two identical parallel machines. There are g agents, and each agent's objective is to minimize its makespan. We present an approximation algorithm such that the performance ratio of the makespan achieved by our algorithm relative to the minimum makespan is no more than for the ith completed agent. Moreover, we show that the performance ratio is tight.
暂无评论