We present a new approximation algorithm for the bin packing problem which has a linear running time and an absolute approximation factor of 3/2. It is known that this approximation factor is the best factor achievabl...
详细信息
We present a new approximation algorithm for the bin packing problem which has a linear running time and an absolute approximation factor of 3/2. It is known that this approximation factor is the best factor achievable, unless P = NP. (C) 2003 Elsevier Science B.V. All rights reserved.
In this paper, we give the first approximation algorithm for the problem of max-min fair allocation of indivisible goods. An instance of this problem consists of a set of k people and m indivisible goods. Each person ...
详细信息
In this paper, we give the first approximation algorithm for the problem of max-min fair allocation of indivisible goods. An instance of this problem consists of a set of k people and m indivisible goods. Each person has a known linear utility function over the set of goods which might be different from the utility functions of other people. The goal is to distribute the goods among the people and maximize the minimum utility received by them. The approximation ratio of our algorithm is Omega(1/root k log(3) k). As a crucial part of our algorithm, we design and analyze an iterative method for rounding a fractional matching on a tree which might be of independent interest. We also provide better bounds when we are allowed to exclude a small fraction of the people from the problem.
Given an underlying communication network represented as an edge-weighted graph G = (V, E), a source node S is an element of V, a set of destination nodes D subset of V, and a capacity k which is a positive integer, t...
详细信息
Given an underlying communication network represented as an edge-weighted graph G = (V, E), a source node S is an element of V, a set of destination nodes D subset of V, and a capacity k which is a positive integer, the capacitated multicast tree routing problem asks for a minimum cost routing scheme for source s to send data to all destination nodes, under the constraint that in each routing tree at most k destination nodes are allowed to receive the data copies. The cost of the routing scheme is the sum of the costs of all individual routing trees therein. Improving on Our previous approximation algorithm for the problem, we present a new algorithm which achieves a worst case performance ratio of root 2089+77/80 + 5/4 rho, where rho denotes the best known approximation ratio for the Steiner minimum tree problem. Since rho is about 1.55 at the writing of the paper, the ratio achieved by Our new algorithm is less than 3.4713. In comparison, the previously best ratio Was 8/5 + 5/4 rho approximate to 3.5375. (C) 2009 Elsevier B.V. All rights reserved.
We give the first approximation algorithm for the generalized network Steiner problem, a problem in network design. An instance consists of a network with link-costs and, for each pair {i,j} of nodes, an edge-connecti...
详细信息
We give the first approximation algorithm for the generalized network Steiner problem, a problem in network design. An instance consists of a network with link-costs and, for each pair {i,j} of nodes, an edge-connectivity requirement r(ij). The goal is to find a minimum-coir network using the available links and satisfying the requirements. Our algorithm outputs a solution whose cost is within 2[log(2)(r + 1)] of optimal, where r is the highest requirement value. In the course of proving the performance guarantee, we prove a combinatorial minmax approximate equality relating minimum-cost networks to maximum packings of certain kinds of cuts. As a consequence of the proof of this theorem, we obtain an approximation algorithm for optimally packing these cuts;we show that this algorithm has application to estimating the reliability of a probabilistic network.
This work studies solution methods for approximating a given tensor by a sum of R rank-1 tensors with one or more of the latent factors being orthonormal. Such a problem arises from applications such as image processi...
详细信息
This work studies solution methods for approximating a given tensor by a sum of R rank-1 tensors with one or more of the latent factors being orthonormal. Such a problem arises from applications such as image processing, joint singular value decomposition, and independent component analysis. Most existing algorithms are of the iterative type, while algorithms of the approximation type are limited. By exploring the multilinearity and orthogonality of the problem, we introduce an approximation algorithm in this work. Depending on the computation of several key subproblems, the proposed approximation algorithm can be either deterministic or randomized. The approximation lower bound is established, both in the deterministic and the expected senses. The approximation ratio depends on the size of the tensor, the number of rank-1 terms, and is independent of the problem data. When reduced to the rank-1 approximation case, the approximation bound coincides with those in the literature. Moreover, the presented results fill a gap left in Yang (SIAM J Matrix Anal Appl 41:1797-1825, 2020), where the approximation bound of that approximation algorithm was established when there is only one orthonormal factor. Numerical studies show the usefulness of the proposed algorithm.
In this paper we consider a unified (polynomial time) approximation method for node-deletion problems with nontrivial and hereditary graph properties. One generic algorithm scheme is presented, which can be applied to...
详细信息
In this paper we consider a unified (polynomial time) approximation method for node-deletion problems with nontrivial and hereditary graph properties. One generic algorithm scheme is presented, which can be applied to any node-deletion problem for finding approximate solutions. It will be shown then that the quality of solutions found by this algorithm is determined by the quality of any minimal solution in any graph in which nodes are weighted according to a certain scheme chosen by the algorithm. For various node-deletion problems simple and natural schemes for weight assignment are considered. It will be proven that the weight of any minimal solution is a good approximation to the optimal weight when graphs are weighted according to them, implying that our generic algorithm indeed computes good approximate solutions for those node-deletion problems. (C) 1998 Elsevier Science B.V. All rights reserved.
This paper studies a 4-approximation algorithm for k-prize collecting Steiner tree problems. This problem generalizes both k-minimum spanning tree problems and prize collecting Steiner tree problems. Our proposed algo...
详细信息
This paper studies a 4-approximation algorithm for k-prize collecting Steiner tree problems. This problem generalizes both k-minimum spanning tree problems and prize collecting Steiner tree problems. Our proposed algorithm employs two 2-approximation algorithms for k-minimum spanning tree problems and prize collecting Steiner tree problems. Also our algorithm framework can be applied to a special case of k-prize collecting traveling salesman problems.
This paper focuses on the scheduling problem on two parallel machines with delivery coordination. In particular, given a set of n jobs, we aim to find a schedule with a minimal makespan such that all jobs are first ex...
详细信息
This paper focuses on the scheduling problem on two parallel machines with delivery coordination. In particular, given a set of n jobs, we aim to find a schedule with a minimal makespan such that all jobs are first executed on two parallel machines then delivered at the destination with a transporter. This problem is known to be NP-hard Chang and Lee (Eur J Oper Res 158(2):470-487, 2004), cannot be solved with an approximation ratio strictly less than 3/2 unless P=NP. We close the gap by proposing a polynomial time algorithm whose approximation ratio is 3/2+epsilon with epsilon > 0, improve the previous best ratio 14/9 + epsilon.
The aim of this paper is to establish a new approximation algorithm for fixed points of nonexpansive mappings in general Banach spaces and to illustrate some numerical results. The approximation algorithm we shall dis...
详细信息
The aim of this paper is to establish a new approximation algorithm for fixed points of nonexpansive mappings in general Banach spaces and to illustrate some numerical results. The approximation algorithm we shall discuss is x(t,n) = (tT)(x0)(n), where x(0) is an element of D(T) is arbitrary, n is a natural number, and t is an element of (0, 1). We shall also provide some numerical error estimates.
We are concerned with the problem of scheduling monotonic moldable tasks on identical processors to minimize the makespan. We focus on the natural case where the number m of processors as resources is fixed or relativ...
详细信息
We are concerned with the problem of scheduling monotonic moldable tasks on identical processors to minimize the makespan. We focus on the natural case where the number m of processors as resources is fixed or relatively small compared with the number n of tasks. We present an efficient (3/2)-approximation algorithm with time complexity O(nmlog(nm)) (for m > n) and O(n(2) log n) (for m <= n). To the best of our knowledge, the best relevant known results are: (a) a (3/2 + epsilon)-approximation algorithm with time complexity O(nm log(n/epsilon)), (b) a fully polynomial-time approximation scheme for the case of m >= 16n/epsilon, and (c) a polynomial-time approximation scheme with time complexity O(n(g(1/epsilon))) when m is bounded by a polynomial in n , where g(center dot) is a super-exponential function. On the other hand, the novel general technique developed in this paper for removing the epsilon-term in the worst-case performance ratio can be applied to improving the performance guarantee of certain dual algorithms for other combinatorial optimization problems. (c) 2022 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://***/licenses/by/4.0/)
暂无评论