Metraipolis › archive › dc_eaae1f524a47
Approximation Algorithms for Right-Hand-Side Parametric Linear Programming Problems — arXiv:2611.09378
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.09378
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-09T22:42:33.431Z
- SHA-256 of the archived text
cd730ba935fedffb459c4b965250dafb2d73b86f44870c4a08307fe0df1b4280- Stable URL of this page
https://metraipolis.com/documento/dc_eaae1f524a47
How to cite
Approximation Algorithms for Right-Hand-Side Parametric Linear Programming Problems — arXiv:2611.09378 — arXiv (en), https://arxiv.org/abs/2611.09378 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_eaae1f524a47 (Metraipolis archive dc_eaae1f524a47, sha256 cd730ba935fedffb459c4b965250dafb2d73b86f44870c4a08307fe0df1b4280)
BibTeX
@misc{dceaae1f524a47,
title = {Approximation Algorithms for Right-Hand-Side Parametric Linear Programming Problems — arXiv:2611.09378},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.09378},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_eaae1f524a47; sha256 cd730ba935fedffb459c4b965250dafb2d73b86f44870c4a08307fe0df1b4280},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.09378. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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. Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.OC, nuovi lavori del giorno). Categorie arXiv: Optimization and Control (math.OC). Pagina del lavoro: https://arxiv.org/abs/2611.09378 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-11-09T22:35:32.260Z dalla pagina https://arxiv.org/list/math.OC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).