This paper deals with cooperative competition in facility location problems in which potential players (investors) are in competition (or conflict) over acquiring suitable sites and clients. In order to formulate the ...
详细信息
This paper deals with cooperative competition in facility location problems in which potential players (investors) are in competition (or conflict) over acquiring suitable sites and clients. In order to formulate the problem, a game-theoretical multi-objective model with the objective of maximizing investor utility is presented. In the proposed method, an acceptance threshold constraint is applied to facility allocation that is based on a combination of distance between a facility and clients, and investors' product prices. Since the common solution methods for multi-objective optimization, such as weighted sums, epsilon-constraints, multi-objective meta-heuristic algorithms, etc. are not efficient enough, and cannot guarantee achieving Nash equilibrium points, a new approach is developed to solve the presented problem. Moreover, according to the computational complexity of the problem, an approximation algorithm is introduced for large-sized problems. Finally, the computational results demonstrate that the proposed algorithm performs efficiently in obtaining Nash equilibrium points. (C) 2017 Elsevier Ltd. All rights reserved.
For a continuous multi-objective optimization problem, it is usually not a practical approach to compute all its nondominated points because there are infinitely many of them. For this reason, a typical approach is to...
详细信息
For a continuous multi-objective optimization problem, it is usually not a practical approach to compute all its nondominated points because there are infinitely many of them. For this reason, a typical approach is to compute an approximation of the nondominated set. A common technique for this approach is to generate a polyhedron which contains the nondominated set. However, often these approximations are used for further evaluations. For those applications a polyhedron is a structure that is not easy to handle. In this paper, we introduce an approximation with a simpler structure respecting the natural ordering. In particular, we compute a box-coverage of the nondominated set. To do so, we use an approach that, in general, allows us to update not only one but several boxes whenever a new nondominated point is found. The algorithm is guaranteed to stop with a finite number of boxes, each being sufficiently thin.
In this article we introduce an algorithm that approximates the nondominated sets of multiobjective mixed-integer convex optimization problems. The algorithm constructs an inner and outer approximation of the front ex...
详细信息
In this article we introduce an algorithm that approximates the nondominated sets of multiobjective mixed-integer convex optimization problems. The algorithm constructs an inner and outer approximation of the front exploiting the convexity of the patches for problems with an arbitrary number of criteria. In the algorithm, the problem is decomposed into patches, which are multiobjective convex problems, by fixing the integer assignments. The patch problems are solved using (simplicial) Sandwiching. We identify parts of patches that are dominated by other patches and ensure that these patch parts are not refined further. We prove that the algorithm converges and show a bound on the reduction of the approximation error in the course of the algorithm. We illustrate the behaviour of our algorithm using some numerical examples and compare its performance to an algorithm from literature.
We study the following scheduling problem with transportation. Given a set of n jobs that need to be processed on a single machine, we need to deliver the finished jobs to one of the two destinations using a single tr...
详细信息
We study the following scheduling problem with transportation. Given a set of n jobs that need to be processed on a single machine, we need to deliver the finished jobs to one of the two destinations using a single transporter. The goal is to minimize the time that all the jobs are delivered to their destination, such that the transporter returns. We propose a 11/6+epsilon-approximation algorithm which improves upon the best-known approximation ratio of 2.
Multiprocessor job scheduling problem has become increasingly interesting, for both theoretical study and practical applications. Theoretical study of the problem has made significant progress recently, which, however...
详细信息
Multiprocessor job scheduling problem has become increasingly interesting, for both theoretical study and practical applications. Theoretical study of the problem has made significant progress recently, which, however, seems not to imply practical algorithms for the problem, yet. Practical algorithms have been developed only for systems with three processors and the techniques seem difficult to extend to systems with more than three processors. This paper offers new observations and introduces new techniques for the multiprocessor job scheduling problem on systems with four processors. A very simple and practical linear time approximation algorithm of ratio bounded by 1.5 is developed for the multi-processor job scheduling problem P (4)|fix|C (max), which significantly improves previous results. Our techniques are also useful for multiprocessor job scheduling problems on systems with more than four processors.
Previous work on the partial Latin square extension (PLSE) problem resulted in a 2-approximation algorithm based on the LP relaxation of a three-dimensional assignment IP formulation. We present an e/(e - I)-approxima...
详细信息
Previous work on the partial Latin square extension (PLSE) problem resulted in a 2-approximation algorithm based on the LP relaxation of a three-dimensional assignment IP formulation. We present an e/(e - I)-approximation algorithm that is based on the LP relaxation of a packing IP formulation of the PLSE problem. (C) 2003 Published by Elsevier B.V.
Given a weighted directed graph G = (V, E, c), where c : E -> R+ is an edge cost function, a subset X of vertices (terminals), and a root vertex v(r), the directed Steiner tree problem (DSP) asks for a minimum-cost...
详细信息
Given a weighted directed graph G = (V, E, c), where c : E -> R+ is an edge cost function, a subset X of vertices (terminals), and a root vertex v(r), the directed Steiner tree problem (DSP) asks for a minimum-cost tree which spans the paths from root vertex v(r) to each terminal. Charikar et al.'s algorithm is well-known for this problem. It achieves an approximation guarantee of l(l - 1)k(1/l) in O(n(l)k(2l)) time for any fixed level l > 1, where 1 is the level of the tree produced by the algorithm, n is the number of vertices, vertical bar V vertical bar, and k is the number of terminals, vertical bar X vertical bar. However, it requires a great amount of computing power, and there are some problems in the proof of the approximation guarantee of the algorithm. This paper provides a faster approximation algorithm improving Charikar et al.'s DSP algorithm with a better time complexity, O(n(l)K(l) + n(2)k + nm), where m is the number of edges, and an amended root 8k - delta In k factor for the 2-level Steiner tree, where delta = root 6 - 2 = 0.4494.
Let T=(V,E) be a tree in which each edge is assigned a cost;let P be a set of source-sink pairs of vertices in V in which each source-sink pair produces a profit. Given a lower bound K for the profit, the K-prize-coll...
详细信息
Let T=(V,E) be a tree in which each edge is assigned a cost;let P be a set of source-sink pairs of vertices in V in which each source-sink pair produces a profit. Given a lower bound K for the profit, the K-prize-collecting multicut problem in trees with submodular penalties is to determine a partial multicut M subset of E such that the total profit of the disconnected pairs after removing M from T is at least K, and the total cost of edges in M plus the penalty of the set of still-connected pairs is minimized, where the penalty is determined by a nondecreasing submodular function. Based on the primal-dual scheme, we present a combinatorial polynomial-time algorithm by carefully increasing the penalty. In the theoretical analysis, we prove that the approximation factor of the proposed algorithm is ((8)(3)+ K-4(3 )+epsilon) , where K is the total curvature of the submodular function and epsilon is any fixed positive number. Experiments reveal that the objective value of the solutions generated by the proposed algorithm is less than 130% compared with that of the optimal value in most cases.
This study addresses the energy efficiency challenge in cloud data centers by examining the Virtual Machine Placement (VMP) problem. VMP involves mapping virtual machines (VMs) to physical machines (PMs) under capacit...
详细信息
This study addresses the energy efficiency challenge in cloud data centers by examining the Virtual Machine Placement (VMP) problem. VMP involves mapping virtual machines (VMs) to physical machines (PMs) under capacity constraints. The paper focuses on the bin packing with linear usage cost (BPLUC) variant of bin packing, which includes fixed and variable costs in the calculation of the cost of a used bin. We prove that every approximation algorithm for the bin and vector bin packing can be used for BPLUC and VBPLUC, respectively. We propose a more power-efficient approach to VMP by applying a vector bin packing algorithm to minimize power consumption in data centers. We test the proposed algorithm on various synthetic and real workloads, and the experimental results demonstrate that it is more power-efficient than existing algorithms for VMP. The findings suggest that the proposed algorithm has significant implications for energy-efficient strategies in cloud data centers. Generally, this study makes contributes to the development of energy-efficient approaches to VMP that can help reduce power consumption and improve the sustainability of cloud data centers.
We consider the MAX SAT problem with the additional constraint that at most P variables have a true value. We obtain a (1 - e(-1))-approximation algorithm for this problem. Feige [6] has proved that for MAX SAT with c...
详细信息
We consider the MAX SAT problem with the additional constraint that at most P variables have a true value. We obtain a (1 - e(-1))-approximation algorithm for this problem. Feige [6] has proved that for MAX SAT with cardinality constraint with clauses without negations this is the best possible performance guarantee unless P = NP.
暂无评论