Paperlane

no. 11 · Monday 9 November 2026

Approximation Algorithms for Right-Hand-Side Parametric Linear Programming Problems

Levin Nemesch, Stefan Ruzika, Clemens Thielen and Alina Wittmann

math.OC

Abstract

In parametric linear optimization problems, the objective function or the feasible set depends linearly on one or several real-valued parameters. The goal is to provide an optimal solution set, i.e., a set containing an optimal solution for each non-parametric problem induced by a particular choice of parameter values. In this paper, we consider right-hand-side single-parametric linear programming problems (RHS-PLPPs) that are usually very difficult to solve exactly. An optimal solution set of minimum cardinality can be infinite, while a representation by optimal bases may still require super-polynomially many different bases. Hence, we develop approximation methods for RHS-PLPPs that compute approximation sets of polynomially bounded cardinality, each containing, for every parameter value, a feasible solution whose objective value is at most a prescribed multiplicative factor times the optimum. Our first approach constructs an approximation set using a greedy staircase procedure and yields an FPTAS under general sufficient conditions. We show that these conditions hold for some important classes of RHS-PLPPs. For monotone instances, in which the feasible sets are nested as the parameter varies, our algorithm yields an approximation set of minimum cardinality. Beyond monotonicity, we establish near-minimum cardinality guarantees under more general sufficient conditions. Finally, we introduce a dual approximation algorithm that returns solutions with objective value no greater than the optimum while allowing a controlled multiplicative violation of the parameter-dependent right-hand sides.

comments
This research was funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) - Project number 508981269, and GRK 2982, 516090167 "Mathematics of Interdisciplinary Multiobjective Optimization"
fields
Optimization and Control
pdf ↗ page arXiv:2611.09378 ↗