We derive a 3/2-approximation algorithm for the NP-hard parallel machine total weighted completion time problem with controllable processing times by the technique of convex quadratic programming relaxation. (C) 2001 ...
详细信息
We derive a 3/2-approximation algorithm for the NP-hard parallel machine total weighted completion time problem with controllable processing times by the technique of convex quadratic programming relaxation. (C) 2001 Elsevier Science B.V. All rights reserved.
We present a multi-exchange local search algorithm for approximating the capacitated facility location problem (CFLP), where a new local improvement operation is introduced that possibly exchanges multiple facilities ...
详细信息
ISBN:
(纸本)3540221131
We present a multi-exchange local search algorithm for approximating the capacitated facility location problem (CFLP), where a new local improvement operation is introduced that possibly exchanges multiple facilities simultaneously. We give a tight analysis for our algorithm and show that the performance guarantee of the algorithm is between 3 + 2root2 - epsilon and 3 + 2 root2 + epsilon for any given constant epsilon > 0. Previously known best approximation ratio for the CFLP is 7.88, due to Mahdian and Pal (2003), based on the operations proposed by Pal, Tardos and Wexler (2001). Our upper bound 3 + 2root2 + epsilon also matches the best known ratio, obtained by Chudak and Williamson (1999), for the CFLP with uniform capacities. In order to obtain the tight bound of our new algorithm, we make interesting use of the notion of exchange graph of Pal et al. and techniques from the area of parallel machine scheduling.
The two-machine flow-shop sequencing problem with arbitrary release dates of jobs and the minimum makespan criterion is considered. The problem is known to be NP-hard, and the best-known approximation algorithms are t...
详细信息
The two-machine flow-shop sequencing problem with arbitrary release dates of jobs and the minimum makespan criterion is considered. The problem is known to be NP-hard, and the best-known approximation algorithms are those of Potts (Math. Oper. Res. 10 (1985) 576) with a worst-case performance ratio of 5/3 and running time O(n(3) log n), and a polynomial time approximation scheme of Hall (Proceedings of the 36th Annual Symposium on Foundations of Computer Science, IEEE Comput. Soc. press, Los Alamitos, 1995, pp. 82-91.) that can generate solutions arbitrary close to the optimum but with a high-time requirement. In this paper, we modify Potts' algorithm so that its worst-case performance ratio is reduced to 3/2, but its running time remains O(n(3) log n). (C) 2001 Elsevier Science B.V. All rights reserved.
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.
Given a directed graph G and an arc weight function w : E(G) --> R+, the maximum directed cut problem (MAX DICUT) is that of finding a directed cut delta (X) with maximum total weight. In this paper we consider a v...
详细信息
Given a directed graph G and an arc weight function w : E(G) --> R+, the maximum directed cut problem (MAX DICUT) is that of finding a directed cut delta (X) with maximum total weight. In this paper we consider a version of MAX DICUT-MAX DICUT with given sizes of parts or MAX DICUT WITH GSP-whose instance is that of MAX DICUT plus a positive integer p, and it is required to nd a directed cut delta (X) having maximum weight over all cuts delta (X) with |X| = p. Our main result is a 0.5-approximation algorithm for solving the problem. The algorithm is based on a tricky application of the pipage rounding technique developed in some earlier papers by two of the authors and a remarkable structural property of basic solutions to a linear relaxation. The property is that each component of any basic solution is an element of a set {0,delta ,1/2,1-delta ,1}, where delta is a constant that satisfies 0 < < 1/2 and is the same for all components.
Effective monitoring of network flow is a key enabling technology for networks and gains extensive attention of researcher. In this paper, we focus efficient monitoring by passive measurement for the network flow on r...
详细信息
ISBN:
(纸本)0780388364
Effective monitoring of network flow is a key enabling technology for networks and gains extensive attention of researcher. In this paper, we focus efficient monitoring by passive measurement for the network flow on reducing the generation overhead communication as more as possible. The problem of efficient monitoring for the network flow is regarded as the problem to find out the minimum flow partition marked set for a given graph, which is NP-hard by proof. approximation algorithm to find out the minimum flow partition marked set is presented with approximation ratio. Simulation results indicate that our proposed algorithms dramatically reduce monitoring nodes compared to scenarios in which vertex cover is employed.
In this paper, we show that blind separation of signals in given alphabets can be formulated into a quadratic optimization problem with integer constraints. Then, efficient c-approximation algorithms are applied to di...
详细信息
In this paper, we show that blind separation of signals in given alphabets can be formulated into a quadratic optimization problem with integer constraints. Then, efficient c-approximation algorithms are applied to directly estimate the transmitted signals. The proposed approach does not require any high order statistics. Moreover, the algorithms converge to an epsilon neighborhood of the global optimum with polynomial computational complexity. Simulations show that the algorithm achieves satisfactory performance using a short length of data.
We consider a new two-stage flexible flow shop in which there are twoparallel processors at stage 1 and only one burn-in processor with capacity of twoat stage 2. The problem is to determine an optimal schedule so as ...
详细信息
We consider a new two-stage flexible flow shop in which there are twoparallel processors at stage 1 and only one burn-in processor with capacity of twoat stage 2. The problem is to determine an optimal schedule so as to minimize themakespan. This scheduling problem is NP-hard, two approximation algorithms withworst-case performance ratio 5/2 are given.
We obtain a necessary and sufficient condition in terms of forbidden structures for tournaments to possess the min-max relation on packing and covering directed cycles, together with strongly polynomial time algorithm...
详细信息
We obtain a necessary and sufficient condition in terms of forbidden structures for tournaments to possess the min-max relation on packing and covering directed cycles, together with strongly polynomial time algorithms for the feedback vertex set problem and the cycle packing problem in this class of tournaments. Applying the local ratio technique of Bar-Yehuda and Even to the forbidden structures, we nd a 2.5-approximation polynomial time algorithm for the feedback vertex set problem in any tournament.
We study the approximability of the weighted edge-dominating set problem. Although even the unweighted case is NP-Complete, in this case a solution of size at most twice the minimum can be efficiently computed due to ...
详细信息
We study the approximability of the weighted edge-dominating set problem. Although even the unweighted case is NP-Complete, in this case a solution of size at most twice the minimum can be efficiently computed due to its close relationship with minimum maximal matching;however, in the weighted case such a nice relationship is not known to exist. In this paper, after showing that weighted edge domination is as hard to approximate as the well studied weighted vertex cover problem, we consider a natural strategy, reducing edge-dominating set to edge cover. Our main result is a simple 2 1/10-approximation algorithm for the weighted edge-dominating set problem, improving the existing ratio, due to a simple reduction to weighted vertex cover, of 2r(WVC), where r(WVC) is the approximation guarantee of any polynomial-time weighted vertex cover algorithm. The best value of r(WVC) currently stands at 2-log log |V|/2 log |V|. Furthermore we establish that the factor of 2 1/10 is tight in the sense that it coincides with the integrality gap incurred by a natural linear programming relaxation of the problem.
暂无评论