TY - GEN
T1 - An FPTAS for a General Class of Parametric Optimization Problems
AU - Bazgan, Cristina
AU - Herzel, Arne
AU - Ruzika, Stefan
AU - Thielen, Clemens
AU - Vanderpooten, Daniel
N1 - Publisher Copyright:
© Springer Nature Switzerland AG 2019.
PY - 2019
Y1 - 2019
N2 - 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 assignment problem, 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-parametric problem is solvable in polynomial time, and (iii) the slopes and intercepts of the value functions of the feasible solutions are nonnegative, 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.
AB - 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 assignment problem, 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-parametric problem is solvable in polynomial time, and (iii) the slopes and intercepts of the value functions of the feasible solutions are nonnegative, 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.
KW - Approximation scheme
KW - Parametric assignment problem
KW - Parametric minimum-cost flow problem
KW - Parametric optimization
KW - Parametric shortest path problem
UR - http://www.scopus.com/inward/record.url?scp=85070190024&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-26176-4_3
DO - 10.1007/978-3-030-26176-4_3
M3 - Conference contribution
AN - SCOPUS:85070190024
SN - 9783030261757
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 25
EP - 37
BT - Computing and Combinatorics - 25th International Conference, COCOON 2019, Proceedings
A2 - Du, Ding-Zhu
A2 - Duan, Zhenhua
A2 - Tian, Cong
PB - Springer Verlag
T2 - 25th International Computing and Combinatorics Conference, COCOON 2019
Y2 - 29 July 2019 through 31 July 2019
ER -