We develop approximation algorithms for the problem of placing replicated data in arbitrary networks, where the nodes may both issue requests for data objects and have capacity for storing data objects so as to minimi...
详细信息
We develop approximation algorithms for the problem of placing replicated data in arbitrary networks, where the nodes may both issue requests for data objects and have capacity for storing data objects so as to minimize the average data-access cost. We introduce the data placement problem to model this problem. We have a set of caches F, a set of clients D, and a set of data objects O. Each cache i can store at most u(i) data objects. Each client j is an element of D has demand d(j) for a specific data object o(j) is an element of O and has to be assigned to a cache that stores that object. Storing an object o in cache i incurs a storage cost of f(i)(o), and assigning client j to cache i incurs an access cost of d(j)c(ij). The goal is to find a placement of the data objects to caches respecting the capacity constraints, and an assignment of clients to caches so as to minimize the total storage and client access costs. We present a 10-approximation algorithm for this problem. Our algorithm is based on rounding an optimal solution to a natural linear-programming relaxation of the problem. One of the main technical challenges encountered during rounding is to preserve the cache capacities while incurring only a constant-factor increase in the solution cost. We also introduce the connected data placement problem to capture settings where write-requests are also issued for data objects, so that one requires a mechanism to maintain consistency of data. We model this by requiring that all caches containing a given object be connected by a Steiner tree to a root for that object, which issues a multicast message upon a write to (any copy of) that object. The total cost now includes the cost of these Steiner trees. We devise a 14-approximation algorithm for this problem. We show that our algorithms can be adapted to handle two variants of the problem: (a) a k-median variant, where there is a specified bound on the number of caches that may contain a given object, and (b) a ge
In this paper, we consider k-echelon extensions of the deterministic one warehouse multi-retailer problem. We give constant factor approximation algorithms for some of these extensions when k is fixed. We focus first ...
详细信息
In this paper, we consider k-echelon extensions of the deterministic one warehouse multi-retailer problem. We give constant factor approximation algorithms for some of these extensions when k is fixed. We focus first on the case without backorders and we give a -approximation algorithm under general assumptions on the evolution of the holding costs as products move toward the final customers. We then improve this result to a k-approximation when the holding costs are monotonically non-increasing or non-decreasing (which is a natural situation in practice). Finally we address problems with backorders: we give a 3-approximation for the one-warehouse multi-retailer problem with backlog and a k-approximation algorithm for the k-level Joint Replenishment Problem with backlog (a variant where inventory can only be kept at the final retailers). Ours results are the first constant approximation algorithms for those problems. In addition, we demonstrate the potential of our approach on a practical case. Our preliminary experiments show that the average optimality gap is around 15%.
In this paper we study variants of the nonpreemptive parallel job scheduling problem in which the number of machines is polynomially bounded in the number of jobs. For this problem we show that a schedule with length ...
详细信息
In this paper we study variants of the nonpreemptive parallel job scheduling problem in which the number of machines is polynomially bounded in the number of jobs. For this problem we show that a schedule with length at most (1 + epsilon) OPT can be calculated in polynomial time. Unless P = NP, this is the best possible result (in the sense of approximation ratio), since the problem is strongly NP-hard. For the case where all jobs must be allotted to a subset of consecutive machines, a schedule with length at most (1.5 + epsilon) OPT can be calculated in polynomial time. The previously best known results are algorithms with absolute approximation ratio 2. Furthermore, we extend both algorithms to the case of malleable jobs with the same approximation ratios.
One of the main goals in the analysis of microarray data is to identify groups of genes and groups of experimental conditions (including environments, individuals, and tissues) that exhibit similar expression patterns...
详细信息
One of the main goals in the analysis of microarray data is to identify groups of genes and groups of experimental conditions (including environments, individuals, and tissues) that exhibit similar expression patterns. This is the so-called biclustering problem. In this paper, we consider two variations of the biclustering problem: the consensus submatrix problem and the bottleneck submatrix problem. The input of the problems contains an m x n matrix A and integers l and k. The consensus submatrix problem is to find an l x k submatrix with l < m and k < n and a consensus vector such that the sum of distances between the rows in the submatrix and the consensus vector is minimized. The bottleneck submatrix problem is to find an l x k submatrix with l < m and k < n, an integer d and a center vector such that the distance between every row in the submatrix and the vector is at most d and d is minimized. We show that both problems are NP-hard and give randomized approximation algorithms for special cases of the two problems. Using standard techniques, we can derandomize the algorithms to get polynomial time approximation schemes for the two problems. To the best of our knowledge, this is the first time that approximation algorithms with guaranteed ratios are presented for microarray data analysis.
In this paper,we address the problem of constructing a Steiner tree in the Euclidean plane R^(2)using stock pieces of materials with fixed length,which is modelled as *** a set X={r_(1),r_(2)…,r_(n)}of n terminals in...
详细信息
In this paper,we address the problem of constructing a Steiner tree in the Euclidean plane R^(2)using stock pieces of materials with fixed length,which is modelled as *** a set X={r_(1),r_(2)…,r_(n)}of n terminals in R^(2)and some stock pieces of materials with fixed length L,we are asked to construct a Steiner tree T interconnecting all terminals in X,and each edge in T must be constructed by a part of that stock piece of *** objective is to minimize the cost of constructing such a Steiner tree T,where the cost includes three components,(1)The cost of Steiner points needed in T;(2)The construction cost of constructing all edges in T and(3)The cost of stock pieces of such materials used to construct all edges in *** can obtain two main results.(1)Using techniques of constructing a Euclidean minimum spanning tree on the set X and a strategy of solving the bin-packing problem,we present a simple 4-approximation algorithm in time O(n log n)to solve this new problem;(2)Using techniques of computational geometry to solve two nonlinear mathematical programming to obtain a key Lemma 8 and using other strategy of solving the bin-packing problem,we design a 3-approximation algorithm in time O(n^(3))to resolve this new problem.
The MAX-MIN tiling problem is as follows. We are given A[1,..., n][1,..., n], a two-dimensional array where each entry A[i][j] stores a non-negative number. Define a tile of A to be a subarray A[l,..., r][t,..., b] of...
详细信息
The MAX-MIN tiling problem is as follows. We are given A[1,..., n][1,..., n], a two-dimensional array where each entry A[i][j] stores a non-negative number. Define a tile of A to be a subarray A[l,..., r][t,..., b] of A, the weight of a tile to be the sum of all array entries in it, and a tiling of A to be a collection of tiles of A such that each entry A[i][j] is contained in exactly one tile. Given a weight bound W the goal of our MAX-MIN tiling problem is to find a tiling of A such that: (1) each tile is of weight at least W (the MIN condition), and (2) the number of tiles is maximized (the MAX condition). The MAX-MIN tiling problem is known to be NP-hard;here, we present first non-trivial approximations algorithms for solving it. (C) 2003 Elsevier Science (USA). All rights reserved.
We present a correction to the paper, "approximation algorithms for shop scheduling problems with minsum objective" (Journal of Scheduling 2002;5:287-305) by Queyranne and Sviridenko. This correction provide...
详细信息
We present a correction to the paper, "approximation algorithms for shop scheduling problems with minsum objective" (Journal of Scheduling 2002;5:287-305) by Queyranne and Sviridenko. This correction provides a correct derivation of its 2e rho approximation result.
We present a generic scheme for approximating NP-hard problems on graphs of treewidth k = omega (log n). When a tree-decomposition of width l is given, the scheme typically yields an l / log n-approximation factor;oth...
详细信息
We present a generic scheme for approximating NP-hard problems on graphs of treewidth k = omega (log n). When a tree-decomposition of width l is given, the scheme typically yields an l / log n-approximation factor;otherwise, an extra log k factor is incurred. Our method applies to several basic subgraph and partitioning problems, including the maximum independent set problem. (c) 2004 Elsevier B.V. All rights reserved.
In this paper, we present approximation algorithms for minimum vertex and edge guard problems for polygons with or without holes with a total of n vertices. For simple polygons, approximation algorithms for both probl...
详细信息
In this paper, we present approximation algorithms for minimum vertex and edge guard problems for polygons with or without holes with a total of n vertices. For simple polygons, approximation algorithms for both problems run in O(n(4)) time and yield solutions that can be at most O(log n) times the optimal solution. For polygons with holes, approximation algorithms for both problems give the same approximation ratio of O(log n), but the running time of the algorithms increases by a factor of n to O(n(5)). (C) 2009 Elsevier B.V. All rights reserved.
Bayesian network structures with a maximum in-degree of k can be approximated with respect to a positive scoring metric up to an factor of 1/k. (c) 2008 Elsevier B.V. All rights reserved.
Bayesian network structures with a maximum in-degree of k can be approximated with respect to a positive scoring metric up to an factor of 1/k. (c) 2008 Elsevier B.V. All rights reserved.
暂无评论