An extended model of the assignmentproblem is considered whose cost is a two dimensional vector. This problem belongs to the class NP-hard, and it is difficult to obtain the optimal solution. In the present paper an ...
详细信息
ISBN:
(纸本)1932415610
An extended model of the assignmentproblem is considered whose cost is a two dimensional vector. This problem belongs to the class NP-hard, and it is difficult to obtain the optimal solution. In the present paper an algorithm based on parametric analysis is presented for quasi optimal solution. Results of numerical experiments are shown, and it is concluded that the algorithm. gives a satisfactory solution, even when the correlation coefficient is near to 1.
In a (linear) parametric optimization problem, the objective value of each feasible solution is an affine function of a real-valued parameter and one is interested in computing a solution for each possible value of th...
详细信息
In a (linear) parametric optimization problem, the objective value of each feasible solution is an affine function of a real-valued parameter and one is interested in computing a solution for each possible value of the parameter. For many important parametric optimization problems including the parametric versions of the shortest path problem, the assignmentproblem, and the minimum cost flow problem, however, the piecewise linear function mapping the parameter to the optimal objective value of the corresponding non-parametric instance (the optimal value function) can have super-polynomially many breakpoints (points of slope change). This implies that any optimal algorithm for such a problem must output a super-polynomial number of solutions. We provide a method for lifting approximation algorithms for non-parametric optimization problems to their parametric counterparts that is applicable to a general class of parametric optimization problems. The approximation guarantee achieved by this method for a parametricproblem is arbitrarily close to the approximation guarantee of the algorithm for the corresponding non-parametricproblem. It outputs polynomially many solutions and has polynomial running time if the non-parametric algorithm has polynomial running time. In the case that the non-parametricproblem can be solved exactly in polynomial time or that an FPTAS is available, the method yields an FPTAS. In particular, under mild assumptions, we obtain the first parametric FPTAS for each of the specific problems mentioned above and a (3/2+epsilon)-approximation algorithm for the parametric metric traveling salesman problem. Moreover, we describe a post-processing procedure that, if the non-parametricproblem can be solved exactly in polynomial time, further decreases the number of returned solutions such that the method outputs at most twice as many solutions as needed at minimum for achieving the desired approximation guarantee.
In a (linear) parametric optimization problem, the objective value of each feasible solution is an affine function of a real-valued parameter and one is interested in computing a solution for each possible value of th...
详细信息
ISBN:
(数字)9783030261764
ISBN:
(纸本)9783030261764;9783030261757
In a (linear) parametric optimization problem, the objective value of each feasible solution is an affine function of a real-valued parameter and one is interested in computing a solution for each possible value of the parameter. For many important parametric optimization problems including the parametric versions of the shortest path problem, the assignmentproblem, and the minimum cost flow problem, however, the piecewise linear function mapping the parameter to the optimal objective value of the corresponding non-parametric instance (the optimal value function) can have super-polynomially many breakpoints (points of slope change). This implies that any optimal algorithm for such a problem must output a super-polynomial number of solutions. We provide a (parametric) fully-polynomial time approximation scheme for a general class of parametric optimization problems for which (i) the parameter varies on the nonnegative real line, (ii) the non-parametricproblem is solvable in polynomial time, and (iii) the slopes and intercepts of the value functions of the feasible solutions are non-negative, integer values below a polynomial-time computable upper bound. In particular, under mild assumptions, we obtain the first parametric FPTAS for each of the specific problems mentioned above.
暂无评论