We study the problem of scheduling jobs with precedence constraints and present two polynomial time approximation schemes for it. The first one is for the case when the machines are identical and the precedence graph ...
详细信息
We study the problem of scheduling jobs with precedence constraints and present two polynomial time approximation schemes for it. The first one is for the case when the machines are identical and the precedence graph partitions the jobs into groups of fixed size. As an interesting particular case, this yields a polynomial time approximation scheme for scheduling jobs with chain or tree precedence constraints on identical machines, when each chain or tree is of constant size. The second approximation scheme is for scheduling jobs with arbitrarily long chain precedence constraints on uniformly related machines when the number of machines is fixed.
In this paper, we study the generalized capacitated tree-routing problem (GCTR), which was introduced to unify the several known multicast problems in networks with edge/demand capacities. Let G = (V, E) be a connecte...
详细信息
In this paper, we study the generalized capacitated tree-routing problem (GCTR), which was introduced to unify the several known multicast problems in networks with edge/demand capacities. Let G = (V, E) be a connected underlying graph with a bulk edge capacity lambda > 0 and an edge weight w(e) >= 0, e is an element of E;we are allowed to construct a network on G by installing any edge capacity k(e)lambda with an integer ke >= 0 for each edge e is an element of E, where the resulting network costs Sigma e is an element of (E) k(e)w(e). Given a sink s is an element of V, a set M subset of V of terminals with a demand q(V) >= 0, V is an element of M and a demand capacity. > 0, we wish to construct the minimum cost network so that all the demands can be sent to s along a suitable collection T = {T1, T2,..., T p} of trees rooted at s, where the total demand collected by each tree Ti is bounded from above by., and the flow amount f (e) of T that goes through each edge e is bounded from above by the edge capacity ke lambda. In this paper, f (e) is defined as Sigma Ti is an element of T: e is an element of Ti-[ (alpha +) (beta qTi (e)]) for prescribed constants alpha, beta >= 0, where qTi (e) denotes the total demand that passes through the edge e along Ti. The term a means a fixed amount used to establish the routing Ti by separating the inside of Ti from the outside while the term alpha qTi (e) means the net capacity proportional to the demand qTi (e). The objective of GCTR is to construct a minimum cost network that admits a collection T of trees to send all demand to sink. It was left open to show whether GCTR with lambda< alpha+ beta k. is approximable by a constant factor or not. In this paper, we present a 13.037-approximation algorithm to GCTR for this case. (C) 2009 Elsevier B. V. All rights reserved.
We study a variation of the vertex cover problem where it is required that the graph induced by the vertex cover is connected. We prove that this problem is polynomial in chordal graphs, has a PTAS in planar graphs, i...
详细信息
We study a variation of the vertex cover problem where it is required that the graph induced by the vertex cover is connected. We prove that this problem is polynomial in chordal graphs, has a PTAS in planar graphs, is APX-hard in bipartite graphs and is 5/3approximable in any class of graphs where the vertex cover problem is polynomial (in particular in bipartite graphs). Finally, dealing with hypergraphs, we study the complexity and the approximability of two natural generalizations. (C) 2009 Elsevier B.V. All rights reserved.
Answering an open question published in Operations Research (54, 73-91, 2006) in the area of network design and logistic optimization, we present the first constant-factor approximation algorithms for the problem comb...
详细信息
Answering an open question published in Operations Research (54, 73-91, 2006) in the area of network design and logistic optimization, we present the first constant-factor approximation algorithms for the problem combining facility location and cable installation in which capacity constraints are imposed on both facilities and cables. We study the problem of designing a minimum cost network to serve client demands by opening facilities for service provision and installing cables for service shipment. Both facilities and cables have capacity constraints and incur buy-at-bulk costs. This Max SNP-hard problem arises in diverse applications and is shown in this paper to admit a combinatorial 19.84-approximation algorithm of cubic running time. This is achieved by an integration of primal-dual schema, Lagrangian relaxation, demand clustering and bi-factor approximation. Our techniques extend to several variants of this problem, which include those with unsplitable demands or requiring network connectivity, and provide constant-factor approximate algorithms in strongly polynomial time.
This paper deals with a single allocation problem in hub-and-spoke networks. We present a simple deterministic 3-approximation algorithm and randomized 2-approximation algorithm based on a linear relaxation problem an...
详细信息
This paper deals with a single allocation problem in hub-and-spoke networks. We present a simple deterministic 3-approximation algorithm and randomized 2-approximation algorithm based on a linear relaxation problem and a randomized rounding procedure. We handle the case where the number of hubs is three, which is known to be NP-hard, and present a (5/4)-approximation algorithm. The single allocation problem includes a special class of the metric labeling problem, defined by introducing an assumption that both objects and labels are embedded in a common metric space. Under this assumption, we can apply our algorithms to the metric labeling problem without losing theoretical approximation ratios. As a byproduct, we also obtain a (4/3)-approximation algorithm for an ordinary metric labeling problem with three labels. (C) 2008 Elsevier B.V. All rights reserved.
The approximability of the unweighted independent set problem has been analyzed in terms of sparseness parameters such as the average degree and inductiveness. In the weighted case, no corresponding results are possib...
详细信息
The approximability of the unweighted independent set problem has been analyzed in terms of sparseness parameters such as the average degree and inductiveness. In the weighted case, no corresponding results are possible for average degree, since adding vertices of small weight can decrease the average degree arbitrarily without significantly changing the approximation ratio. In this paper, we introduce two weighted measures, namely weighted average degree and weighted inductiveness, and analyze algorithms for the weighted independent set problem in terms of these parameters. (C) 2008 Elsevier B.V. All rights reserved.
This paper presents an economic lot-sizing problem with perishable inventory and general economies of scale cost functions. For the case with backlogging allowed, a mathematical model is formulated, and several proper...
详细信息
This paper presents an economic lot-sizing problem with perishable inventory and general economies of scale cost functions. For the case with backlogging allowed, a mathematical model is formulated, and several properties of the optimal solutions are explored. With the help of these optimality properties, a polynomial time approximation algorithm is developed by a new method. The new method adopts a shift technique to obtain a feasible solution of subproblem and takes the optimal solution of the subproblem as an approximation solution of our problem. The worst case performance for the approximation algorithm is proven to be （4√2 ＋ 5）/7. Finally, an instance illustrates that the bound is tight.
The selected-internal Steiner minimum tree problem is a generalization of original Steiner minimum tree problem. Given a weighted complete graph G=(V,E) with weight function c, and two subsets R (') aSS RaS dagger...
详细信息
The selected-internal Steiner minimum tree problem is a generalization of original Steiner minimum tree problem. Given a weighted complete graph G=(V,E) with weight function c, and two subsets R (') aSS RaS dagger V with |R-R (')|a parts per thousand yen2, selected-internal Steiner minimum tree problem is to find a minimum subtree T of G interconnecting R such that any leaf of T does not belong to R ('). In this paper, suppose c is metric, we obtain a (1+rho)-approximation algorithm for this problem, where rho is the best-known approximation ratio for the Steiner minimum tree problem.
We consider a multi-agent scheduling problem on a single machine in which each agent is responsible for his own set of jobs and wishes to minimize the total weighted completion time of his own set of jobs. It is known...
详细信息
We consider a multi-agent scheduling problem on a single machine in which each agent is responsible for his own set of jobs and wishes to minimize the total weighted completion time of his own set of jobs. It is known that the unweighted problem with two agents is NP-hard in the ordinary sense. For this case, we can reduce our problem to a Multi-Objective Shortest-Path (MOSP) problem and this reduction leads to several results including Fully Polynomial Time approximation Schemes (FPTAS). We also provide an efficient approximation algorithm with a reasonably good worst-case ratio. (C) 2009 Elsevier B.V. All rights reserved.
The selected-internal Steiner minimum tree problem is a generalization of original Steiner minimum tree problem. Given a weighted complete graph G=(V,E) with weight function c, and two subsets R (') aSS RaS dagger...
详细信息
The selected-internal Steiner minimum tree problem is a generalization of original Steiner minimum tree problem. Given a weighted complete graph G=(V,E) with weight function c, and two subsets R (') aSS RaS dagger V with |R-R (')|a parts per thousand yen2, selected-internal Steiner minimum tree problem is to find a minimum subtree T of G interconnecting R such that any leaf of T does not belong to R ('). In this paper, suppose c is metric, we obtain a (1+rho)-approximation algorithm for this problem, where rho is the best-known approximation ratio for the Steiner minimum tree problem.
暂无评论