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.
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.
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 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.
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.
In this paper, we study the path version of the Traveling Salesman Problem with the edge cost function satisfying a "relaxed" form of triangle inequality called the biased triangle inequality. We denote this...
详细信息
In this paper, we study the path version of the Traveling Salesman Problem with the edge cost function satisfying a "relaxed" form of triangle inequality called the biased triangle inequality. We denote this problem as the Biased-TSP-Path. In this paper, we prove that the Biased-TSP-Path is approximable within a constant factor. Specifically, we design a 4-approximation algorithm by a suitable modification of the double-tree algorithm using effective shortcutting procedures. (C) 2019 Elsevier B.V. All rights reserved.
This paper studies the problem of constructing maximum-lifetime data aggregation trees in wireless sensor networks for collecting sensor readings. This problem is known to be NP-hard. Wireless sensor networks in which...
详细信息
This paper studies the problem of constructing maximum-lifetime data aggregation trees in wireless sensor networks for collecting sensor readings. This problem is known to be NP-hard. Wireless sensor networks in which transmission power levels of sensors are adjustable and heterogeneous are considered. An approximation algorithm is developed to construct a data aggregation tree whose inverse lifetime is guaranteed to be within a bound from the optimal one. Adjustable transmission power levels of the sensors introduce an additional term in the bound compared with the bound for networks in which transmission power levels of all sensors are fixed. The additional term is proportional to the difference between the maximum and minimum amounts of energy for a sensor to transmit a message using respectively its maximum and minimum transmission power levels. The proposed algorithm is further enhanced to obtain an improved version. Simulation results show that properly adjusting transmission power levels of the sensors yields higher lifetime of the network than keeping their transmission power levels at the maximum level.
暂无评论