An approximation algorithm for a general class of parametric optimization problems (Q2156299): Difference between revisions

The authors 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. Also, the authors address the issue of computing approximations for parametric optimization problems that are as small as possible in terms of cardinality. Finally, the authors show that their general results are applicable to the parametric versions of many well-known, classical optimization problems including the parametric shortest path problem, the parametric assignment problem, and to a general class of parametric mixed integer linear programs that includes the parametric minimum cost flow problem, and the parametric metric salesman problem.