A modified fast approximation algorithm for the 0-1 knapsack problem with improved complexity is presented, based on the schemes of lbarra, Kim and Babat. By using a new partition of items, the algorithm solves the n-...
详细信息
A modified fast approximation algorithm for the 0-1 knapsack problem with improved complexity is presented, based on the schemes of lbarra, Kim and Babat. By using a new partition of items, the algorithm solves the n-item 0-1 knapsack problem to any relative error tolerance epsilon > 0 in the scaled profit space P*/K = O(1/epsilon(1+delta)) with time O(n log(l/s) + 1/epsilon(2+2delta)) and space O(n + 1/epsilon(2+delta)), where P* and b are the maximal profit and the weight capacity of the knapsack problem, respectively, K is a problem-dependent scaling factor, delta = alpha/(1 + alpha) and alpha = O(log b). This algorithm reduces the exponent of the complexity bound in [5].
作者：
Liu, XiaofeiLi, WeidongPeking Univ
Sch Elect Engn & Comp Sci Beijing 100871 Peoples R China Yunnan Univ
Sch Math & Stat Kunming 650504 Yunnan Peoples R China Yunnan Univ
Dianchi Coll Kunming 650000 Yunnan Peoples R China
In this paper, we introduce the multicut problem in trees with submodular penalties, which generalizes the prize-collecting multicut problem in trees and vertex cover with submodular penalties. We present a combinator...
详细信息
ISBN:
(数字)9783030271954
ISBN:
(纸本)9783030271954;9783030271947
In this paper, we introduce the multicut problem in trees with submodular penalties, which generalizes the prize-collecting multicut problem in trees and vertex cover with submodular penalties. We present a combinatorial 3-approximation algorithm, based on the primal-dual scheme for the multicut problem in trees.
We present a combinatorial primal-dual 7-approximation algorithm for the k-level stochastic facility location problem, the stochastic counterpart of the standard k-level facility location problem. This approximation r...
详细信息
ISBN:
(纸本)9783642143540
We present a combinatorial primal-dual 7-approximation algorithm for the k-level stochastic facility location problem, the stochastic counterpart of the standard k-level facility location problem. This approximation ratio is slightly worse than that of the primal-dual 6-approximation for the standard k-level facility location problem [3] because of the extra stochastic assumption. This new result complements the recent non-combinatorial 3-approximation algorithm for the same problem by Wang et al [21].
We consider the following single-machine scheduling problem, which is often denoted 1 || Sigma f(j): we are given n jobs to be scheduled on a single machine, where each job j has an integral processing time p(j), and ...
详细信息
We consider the following single-machine scheduling problem, which is often denoted 1 || Sigma f(j): we are given n jobs to be scheduled on a single machine, where each job j has an integral processing time p(j), and there is a nondecreasing, nonnegative cost function f(j)(C-j)that specifies the cost of finishing j at time C-j;the objective is to minimize Sigma(n)(j=1) f(j)(C-j). Bansal and Pruhs recently gave the first constant approximation algorithm with a performance guarantee of 16. We improve on this result by giving a primal-dual pseudo-polynomial-time algorithm based on the recently introduced knapsack-cover inequalities. The algorithm finds a schedule of cost at most four times the constructed dual solution. Although we show that this bound is tight for our algorithm, we leave open the question of whether the integrality gap of the linear program is less than 4. Finally, we show how the technique can be adapted to yield, for any epsilon > 0, a polynomial time (4 + epsilon)-approximation algorithm for this problem.
In single machine scheduling with release times and job delivery, jobs are processed on single machine and then delivered by a capacitated vehicle to a single customer. Only one vehicle is employed to deliver these jo...
详细信息
In single machine scheduling with release times and job delivery, jobs are processed on single machine and then delivered by a capacitated vehicle to a single customer. Only one vehicle is employed to deliver these jobs. The vehicle can deliver at most c jobs in a shipment. The delivery completion time of a job is defined as the time in which the delivery batch containing the job is delivered to the customer and the vehicle returns to the machine. The objective is to minimize the makespan, i.e., the maximum delivery completion time of the jobs. We provide an approximation algorithm for this problem which is better than that given in the literature, improving the performance ratio from 5/3 to 3/2. (C) 2010 Elsevier B.V. All rights reserved.
A new efficient two-dimensional warping algorithm is presented, in which sub-optimal warping is attained by iterating DP-based local optimization of warp on partially overlapping subplane sequence. From an experimenta...
详细信息
A new efficient two-dimensional warping algorithm is presented, in which sub-optimal warping is attained by iterating DP-based local optimization of warp on partially overlapping subplane sequence. From an experimental comparison with a conventional approximation algorithm based on beam search DP, relative superiority of the proposed algorithm is established.
The constrained minimum vertex cover problem on bipartite graphs (the Min-CVCB problem) is an important NP-complete problem. This paper presents a polynomial time approximation algorithm for the problem based on the t...
详细信息
The constrained minimum vertex cover problem on bipartite graphs (the Min-CVCB problem) is an important NP-complete problem. This paper presents a polynomial time approximation algorithm for the problem based on the technique of chain implication. For any given constant ??>?0, if an instance of the Min-CVCB problem has a minimum vertex cover of size (k_ u , k _l ), our algorithm constructs a vertex cover of size (k~* _u , k~* _l ), satisfying max {k~ *_u /k _u , k ~*_ l /k_ l }?≤?1?+??. Electronic supplementary material The online version of this article (doi: 10.1007/s11390-008-9180-5) contains supplementary material, which is available to authorized users.
This paper is aimed to present the solution to vertex cover problem by means of an approximation solution. As it is NP complete problem, we can have an approximate time algorithm to solve the vertex cover problem. We ...
详细信息
ISBN:
(纸本)9788132221265;9788132221258
This paper is aimed to present the solution to vertex cover problem by means of an approximation solution. As it is NP complete problem, we can have an approximate time algorithm to solve the vertex cover problem. We will modify the algorithm to have an algorithm which can be solved in polynomial time and which will give near to optimum solution. It is a simple algorithm which will be based on articulation point. Articulation point can be found using the Depth First Search algorithm.
The Capacitated Multicast Tree Routing Problem is considered, in which only a limited number of destination nodes are allowed to receive data in one routing tree and multiple routing trees are needed to send data from...
详细信息
ISBN:
(纸本)9783540850960
The Capacitated Multicast Tree Routing Problem is considered, in which only a limited number of destination nodes are allowed to receive data in one routing tree and multiple routing trees are needed to send data from the source node to all destination nodes. The goal is to minimize the total cost of these routing trees. An improved approximation algorithm is presented, which has a worst case performance ratio of 8/5 + 5/4 rho. Here rho denotes the best approximation ratio for the Steiner Minimum Tree problem, and it is about 1.55 at the writing of the paper. This improves upon the previous best having a performance ratio of 2+rho.
In this paper, we consider the dynamic k-level facility location problem, which is a generalization of the uncapacitated k-level facility location problem when considering time factor. We present a combinatorial prima...
详细信息
ISBN:
(纸本)9783030271954;9783030271947
In this paper, we consider the dynamic k-level facility location problem, which is a generalization of the uncapacitated k-level facility location problem when considering time factor. We present a combinatorial primal-dual approximation algorithm for the problem which finds a solution within 6 times the optimum. This approximation ratio under a dynamic setting coincides with that of the simple dual ascent 6-approximation algorithm for the (static) multilevel facility location problem (Bumb, 2001) with a weak triangle inequality property.
暂无评论