The ring loading problem and its variants have been extensively studied in the last fifteen years, under the assumption that all requests have to be satisfied. However, in many practical cases, one may wish to reject ...
详细信息
The ring loading problem and its variants have been extensively studied in the last fifteen years, under the assumption that all requests have to be satisfied. However, in many practical cases, one may wish to reject some requests, which results in a penalty cost. We introduce the ring loading problem with penalty cost, which generalizes the well-known ring loading problem (Schrijver et al., 1999 [14]). We prove that this problem is NP-hard even if the demand can be split, and design a 1.58-approximation algorithm for the integer demand splittable case and a (1.58 + epsilon)-approximation algorithm for the demand unsplittable case, for any given number epsilon > 0. (C) 2013 Elsevier B.V. All rights reserved.
We introduce and study a discrete multi-period extension of the classical knapsack problem, dubbed generalized incremental knapsack. In this setting, we are given a set of n items, each associated with a non-negative ...
详细信息
We introduce and study a discrete multi-period extension of the classical knapsack problem, dubbed generalized incremental knapsack. In this setting, we are given a set of n items, each associated with a non-negative weight, and T time periods with non-decreasing capacities W-1 <= ... <= W-T. When item i is inserted at time t, we gain a profit of p(it );however, this item remains in the knapsack for all subsequent periods. The goal is to decide if and when to insert each item, subject to the time-dependent capacity constraints, with the objective of maximizing our total profit. Interestingly, this setting subsumes as special cases a number of recently-studied incremental knapsack problems, all known to be strongly NP-hard. Our first contribution comes in the form of a polynomial-time (1/2 - epsilon)-approximation for the generalized incremental knapsack problem. This result is based on a reformulation as a single-machine sequencing problem, which is addressed by blending dynamic programming techniques and the classical Shmoys-Tardos algorithm for the generalized assignment problem. Combined with further enumeration-based self-reinforcing ideas and new structural properties of nearly-optimal solutions, we turn our algorithm into a quasi-polynomial time approximation scheme (QPTAS). Hence, under widely believed complexity assumptions, this finding rules out the possibility that generalized incremental knapsack is APX-hard.
We present approximation algorithms for the unsplittable flow problem (UFP) in undirected graphs. As is standard in this line of research, we assume that the maximum demand is at most the minimum Capacity. We focus on...
详细信息
We present approximation algorithms for the unsplittable flow problem (UFP) in undirected graphs. As is standard in this line of research, we assume that the maximum demand is at most the minimum Capacity. We focus on the non-uniform capacity case in which the edge capacities can vary arbitrarily over the graph. Our results are: We obtain an O(Delta alpha(-1) log(2) n) approximation ratio for UFP, where n is the number of vertices, Delta is the maximum degree, and alpha is the expansion of the graph. Furthermore, if we specialize to the case where all edges have the same capacity, Our algorithm gives an O(Delta alpha(-1) log n) approximation. For certain strong constant-degree expanders considered by Frieze [17] we obtain an O(root log n) approximation for the uniform capacity case. For UFP on the line and the ring, we give the first constant-factor approximation algorithms. All of the above results improve if the maximum demand is bounded away from the minimum capacity. The above results either improve upon or are incomparable with previously known results for these problems. The main technique used for these results is randomized rounding followed by greedy alteration, and is inspired by the use of this idea in recent work.
We study the problem of aligning as many points as possible horizontally, vertically, or diagonally, when each point is allowed to be placed anywhere in its own given region. Different shapes of placement regions and ...
详细信息
We study the problem of aligning as many points as possible horizontally, vertically, or diagonally, when each point is allowed to be placed anywhere in its own given region. Different shapes of placement regions and different sets of alignment orientations are considered. More generally, we assume that a graph is given on the points, and only the alignments of points that are connected in the graph count. We show that for planar graphs the problem is NP-hard, and we provide an inapproximability result for general graphs. For the case of trees and planar graphs, we give approximation algorithms whose performance depends on the shape of the given regions and the set of orientations. When the orientations are the ones given by the axes and the regions are axis-parallel rectangles, we obtain a polynomial time approximation scheme.
The computational complexity of reasoning within the Dempster-Shafer theory of evidence is one of the major points of criticism this formalism has to face. To overcome this difficulty various approximation algorithms ...
详细信息
The computational complexity of reasoning within the Dempster-Shafer theory of evidence is one of the major points of criticism this formalism has to face. To overcome this difficulty various approximation algorithms have been suggested that aim bf reducing the number of focal elements in the belief functions involved. This article reviews a number of algorithms based on this method and introduces a new one-the DI algorithm-that was designed to bring about minimal deviations in those values that are relevant to decision making. If describes an empirical study that examines the appropriateness of these approximation procedures in decision-making situations. It presents and interprets the empirical findings along several dimensions and discusses the various tradeoffs that have to be taken into account when actually applying one of these methods. (C) 1997 Elsevier Science Inc.
We study the capacitated k-facility location problem, in which we are given a set of clients with demands, a set of facilities with capacities and a positive integer k. It costs f(i) to open facility i, and c(ij) for ...
详细信息
We study the capacitated k-facility location problem, in which we are given a set of clients with demands, a set of facilities with capacities and a positive integer k. It costs f(i) to open facility i, and c(ij) for facility i to serve one unit of demand from client j. The objective is to open at most k facilities serving all the demands and satisfying the capacity constraints while minimizing the sum of service and opening costs. In this paper, we give the first fully polynomial time approximation scheme (FPTAS) for the single-sink (single-client) capacitated k-facility location problem. Then, we show that the capacitated k-facility location problem with uniform capacities is solvable in polynomial time if the number of clients is fixed by reducing it to a collection of transportation problems. Third, we analyze the structure of extreme point solutions, and examine the efficiency of this structure in designing approximation algorithms for capacitated k-facility location problems. Finally, we extend our results to obtain an improved approximation algorithm for the capacitated facility location problem with uniform opening costs. (C) 2014 Elsevier B.V. All rights reserved.
In the single-source unsplittable flow problem, we are given a network G, a source vertex s, and k commodities with sinks t(i) and real-valued demands rho(i), 1less than or equal toiless than or equal tok. We seek to ...
详细信息
In the single-source unsplittable flow problem, we are given a network G, a source vertex s, and k commodities with sinks t(i) and real-valued demands rho(i), 1less than or equal toiless than or equal tok. We seek to route the demand rho(i) of each commodity i along a single s-t(i) flow path so that the total flow routed across any edge e is bounded by the edge capacity u(e). The conceptual difficulty of this NP-hard problem arises from combining packing constraints due to the existence of capacities with path selection in a graph of arbitrary topology. In this paper we give a generic framework, which yields approximation algorithms that are simpler than those previously known and achieve significant improvements upon the approximation ratios. Our framework, with appropriate subroutines, applies to all optimization versions previously considered and, unlike previous work, treats in a unified manner directed and undirected graphs. We provide extensions of our algorithms which yield the best possible approximation guarantees for restricted sets of demand values and an associated scheduling problem.
We consider a class of stochastic online matching problems, where a set of sequentially arriving jobs are to be matched to a group of workers. The objective is to maximize the total expected reward, defined as the sum...
详细信息
We consider a class of stochastic online matching problems, where a set of sequentially arriving jobs are to be matched to a group of workers. The objective is to maximize the total expected reward, defined as the sum of the rewards of each matched worker-job pair. Each worker can be matched to multiple jobs subject to the constraint that previously matched jobs are completed. We provide constant approximation algorithms for different variations of this problem with equal-length jobs.
Given n(f) sites, each equipped with one facility, and n(c) cities, fault tolerant facility location (FTFL) [K. Jain and V. V. Vazirani, APPROX '00: Proceedings of the Third International Workshop on approximation...
详细信息
Given n(f) sites, each equipped with one facility, and n(c) cities, fault tolerant facility location (FTFL) [K. Jain and V. V. Vazirani, APPROX '00: Proceedings of the Third International Workshop on approximation algorithms for Combinatorial Optimization, Spinger, New York, 2000, pp. 177-183] requires computing a minimum-cost connection scheme such that each city connects to a specified number of facilities. When each city connects to exactly one facility, FTFL becomes the classical uncapacitated facility location problem (UFL) that is well-known NP hard. The current best solution to FTFL admits an approximation ratio 1.7245 due to Byrka, Srinivasan, and Swamy applying the dependent rounding technique announced recently [Proceedings of IPCO, 2010, pp. 244-257], which improves the ratio 2.076 obtained by Swamy and Shmoys based on LP rounding [ACM Trans. algorithms, 4 (2008), pp. 1-27]. In this paper, we study a variant of the FTFL problem, namely, fault tolerant facility allocation (FTFA), as another generalization of UFL by allowing each site to hold multiple facilities and show that we can obtain better solutions for this problem. We first give two algorithms with 1.81 and 1.61 approximation ratios in time complexity O(m R log m) and O(Rn-3), respectively, where R is the maximum number of facilities required by any city, m = n(f)n(c), and n = max{n(f), n(c)}. Instead of applying the dual-fitting technique that reduces the dual problem's solution to fit the original problem as used in the literature [K. Jain et al., Journal of the ACM, 50 (2003), pp. 795-824;K. Jain, M. Mahdian, and A. Saberi, STOC'02: Proceedings of the 34th Annual ACM Symposium on the Theory of Computing, New York, 2002, pp. 731-740;A. Saberi et al., approximation, Randomization, and Combinatorial Optimization: algorithms and Techniques, Springer, New York, 2001, pp. 127-137], we propose a method called inverse dual-fitting that alters the original problem to fit the dual solution and show that t
This work deals with the continuous time lot-sizing inventory problem when demand and costs are time-dependent. We adapt a cost balancing technique developed for the periodic-review version of our problem to the conti...
详细信息
This work deals with the continuous time lot-sizing inventory problem when demand and costs are time-dependent. We adapt a cost balancing technique developed for the periodic-review version of our problem to the continuous-review framework. We prove that the solution obtained costs at most twice the cost of an optimal solution. We study the numerical complexity of the algorithm and generalize the policy to several important extensions while preserving its performance guarantee of two. Finally, we propose a modified version of our algorithm for the lot-sizing model with some restricted settings that improves the worst-case bound. (C) 2013 Elsevier B.V. All rights reserved.
暂无评论