Non-preemptive scheduling of n independent jobs on m unrelated machines so as to minimize the maximal job completion time is considered. A polynomial algorithm with the worst-case absolute error of min{(1 - 1/m)p(max)...
详细信息
Non-preemptive scheduling of n independent jobs on m unrelated machines so as to minimize the maximal job completion time is considered. A polynomial algorithm with the worst-case absolute error of min{(1 - 1/m)p(max), p'(max)) is presented, where p(max) is the largest job processing time and p'(max) is the mth element from the non-increasing list of job processing times. This is better than the earlier known best absolute error of p(max). The algorithm is based on the rounding of acyclic multiprocessor distributions. An O(nm(2)) algorithm for the construction of an acyclic multiprocessor distribution is also presented. (C) 2006 Wiley Periodicals, Inc.
We consider the following optimisation problem that we encountered during the consolidation process of trains in a container transhipment terminal as well as in the intermediate storage of containers in sea ports in o...
详细信息
We consider the following optimisation problem that we encountered during the consolidation process of trains in a container transhipment terminal as well as in the intermediate storage of containers in sea ports in order to accelerate the loading and unloading of the vessels. There are n ordered pairs of points in the ni-dimensional metric space: (a(i), b(i)), 1 <= i <= n. The problem is to find a permutation i(1), i(2), ... , i(n) of numbers 1, 2, ... , n minimising the function Sigma(n-1)(j=1) d(b(ij), a(ij+1)) + d(b(in), a(i1)), where d(.,.) is the metric of the space. The problem can be considered as a special case of the asymmetric travelling salesman problem. As for Euclidean, Manhattan and Chehyshev metric the problem is NP-hard (as a generalisation of the well-known TSP problem) we propose the simple approximation algorithm with the approximation guarantee equal to 3. The approximation guarantee is tight as will be shown by a sequence of instances for which the approximation ratio converges to 3.
We consider the scheduling of simple linear deteriorating jobs on parallel machines from a new perspective based on game theory. In scheduling, jobs are often controlled by independent and selfish agents, in which eac...
详细信息
We consider the scheduling of simple linear deteriorating jobs on parallel machines from a new perspective based on game theory. In scheduling, jobs are often controlled by independent and selfish agents, in which each agent tries to select a machine for processing that optimizes its own payoff while ignoring the others. We formalize this situation as a game in which the players are job owners, the strategies are machines, and a player's utility is inversely proportional to the total completion time of the machine selected by the agent. The price of anarchy is the ratio between the worst-case equilibrium makespan and the optimal makespan. In this paper, we design a game theoretic approximation algorithm A and prove that it converges to a pure-strategy Nash equilibrium in a linear number of rounds. We also derive the upper bound on the price of anarchy of A and further show that the ratio obtained by A is tight. Finally, we analyze the time complexity of the proposed algorithm. (C) 2014 Elsevier B.V. All rights reserved.
In this paper, we study the k-level facility location problem with outliers (k-LFLPWO), which is an extension of the well-known k-level facility location problem (k-LFLP). In the k-LFLPWO, we are given k facility loca...
详细信息
In this paper, we study the k-level facility location problem with outliers (k-LFLPWO), which is an extension of the well-known k-level facility location problem (k-LFLP). In the k-LFLPWO, we are given k facility location sets, a client location set of cardinality n and a non-negative integer q < n. Every facility location set has a different level which belongs to {1, 2,..., k}. For any facility location, there is an opening cost. For any two locations, there is a connecting cost. We wish to connect at least n - q clients to opened facilities from level 1 to level k, such that the total cost including opening costs and connecting costs is minimized. Our main contribution is to present a 6-approximation algorithm, which is based on the technique of primal-dual, for the k-LFLPWO.
Facility location problem is one of the most important problems in the combinatorial optimization. The multi-level facility location problem and the facility location with capacities are important variants for the cla...
详细信息
Facility location problem is one of the most important problems in the combinatorial optimization. The multi-level facility location problem and the facility location with capacities are important variants for the classical facility location problem. In this work, we consider the multilevel facility location problem with soft capacities in the uncertain scenario. The uncertainty setting means the location process is stochastic. We consider a two-stage model. The soft-capacities setting means each facility has multiple capacities by paying multiple opening cost. The multi-level setting means the client needs to connect to a path. We propose a bifactor (1/alpha,6/(1-2 alpha))-approximation algorithm for the stochastic multi-level facility location problem (SMLFLP), where alpha is an element of(0,0.5) is a given constant. Then, we reduce the stochastic multi-level facility location problem with soft capacities to SMLFLP. The reduction implies a (1/alpha+6/(1-2 alpha)-approximation algorithm. The ratio is 14.9282 when setting alpha=0.183.
We consider the spherical k-means problem with outliers, an extension of the k-means problem. In this clustering problem, all sample points are on the unit sphere. Given two integers k and z, we can ignore at most z p...
详细信息
We consider the spherical k-means problem with outliers, an extension of the k-means problem. In this clustering problem, all sample points are on the unit sphere. Given two integers k and z, we can ignore at most z points (outliers) and need to find at most k cluster centers on the unit sphere and assign remaining points to these centers to minimize the k-means objective. It has been proved that any algorithm with a bounded approximation ratio cannot return a feasible solution for this problem. Our contribution is to present a local search bi-criteria approximation algorithm for the spherical k-means problem.
This paper presents an approximation algorithm for a vehicle routing problem on a tree-shaped network with a single depot where there are two types of demands, pickup demand and delivery demand. Customers are located ...
详细信息
This paper presents an approximation algorithm for a vehicle routing problem on a tree-shaped network with a single depot where there are two types of demands, pickup demand and delivery demand. Customers are located on nodes of the tree, and each customer has a positive demand of pickup and/or delivery. Demands of customers are served by a fleet of identical vehicles with unit capacity. Each vehicle can serve pickup and delivery demands. It is assumed that the demand of a customer is splittable, i.e., it can be served by more than one vehicle. The problem we are concerned with in this paper asks to find a set of tours of the vehicles with minimum total lengths. In each tour, a vehicle begins at the depot with certain amount of goods for delivery, visits a subset of the customers in order to deliver and pick up goods and returns to the depot. At any time during the tour, a vehicle must always satisfy the capacity constraint, i.e., at any time the sum of goods to be delivered and that of goods that have been picked up is not allowed to exceed the vehicle capacity. We propose a 2-approximation algorithm for the problem. (c) 2006 Elsevier B.V. All rights reserved.
We study the minimum weight dominating set problem in weighted unit disk graph, and give a polynomial time algorithm with approximation ratio 5 + epsilon, improving the previous best result of 6 + epsilon in [Yaochun ...
详细信息
We study the minimum weight dominating set problem in weighted unit disk graph, and give a polynomial time algorithm with approximation ratio 5 + epsilon, improving the previous best result of 6 + epsilon in [Yaochun Huang, Xiaofeng Gao, Zhao Zhang, Weili Wu, A better constant-factor approximation for weighted dominating set in unit disk graph, J. Comb. Optim. (ISSN: 1382-6905) (2008) 1573-2886. (Print) (Online)]. Combining the common technique used in the above mentioned reference, we can compute a minimum weight connected dominating set with approximation ratio 9 + epsilon, beating the previous best result of 10 + epsilon in the same work. (C) 2008 Elsevier B.V. All rights reserved.
We consider the k-level facility location problem with soft capacities （k-LFLPSC）. In the k- LFLPSC, each facility i has a soft capacity ui along with an initial opening cost fi ≥O, i.e., the capacity of facility i...
详细信息
We consider the k-level facility location problem with soft capacities （k-LFLPSC）. In the k- LFLPSC, each facility i has a soft capacity ui along with an initial opening cost fi ≥O, i.e., the capacity of facility i is an integer multiple of ui incurring a cost equals to the corresponding multiple of fi. We firstly propose a new bifactor （ln（1/β）/（1 -β）, 1 ＋ 2/（1 - β））-approximation algorithm for the k-level facility location problem （k-LFLP）, where β∈（0, 1） is a fixed constant. Then, we give a reduction from the k-LFLPSC to the k-LFLP. The reduction together with the above bifactor approximation algorithm for the k-LFLP imply a 5.5053-approximation algorithm for the k-LFLPSC which improves the previous 6-approximation.
This paper presents an improved lower bound and an approximation algorithm based on spectral decomposition for the binary constrained quadratic programming problem. To decompose spectrally the quadratic matrix in the ...
详细信息
This paper presents an improved lower bound and an approximation algorithm based on spectral decomposition for the binary constrained quadratic programming problem. To decompose spectrally the quadratic matrix in the objective function, we construct a low rank problem that provides a lower bound. Then an approximation algorithm for the binary quadratic programming problem together with a worst case performance analysis for the algorithm is provided.
暂无评论