A survey of exact and approximation algorithms for linear-parametric optimization problems

Levin Nemesch (), Stefan Ruzika (), Clemens Thielen () and Alina Wittmann ()
Additional contact information
Levin Nemesch: RPTU Kaiserslautern-Landau
Stefan Ruzika: RPTU Kaiserslautern-Landau
Clemens Thielen: Technical University of Munich
Alina Wittmann: Technical University of Munich

Journal of Global Optimization, 2025, vol. 93, issue 1, No 10, 299-333

Abstract: Abstract Linear-parametric optimization, where multiple objectives are combined into a single objective using linear combinations with parameters as coefficients, has numerous links to other fields in optimization and a wide range of application areas. In this survey, we provide a comprehensive overview of structural results and algorithmic strategies for solving linear-parametric optimization problems exactly and approximately. Transferring concepts from related areas such as multi-objective optimization provides further relevant results. The survey consists of two parts: First, we list strategies that work in a general fashion and do not rely on specific problem structures. Second, we look at well-studied parametric optimization problems and cover both important theoretical results and specialized algorithmic approaches for these problems. Among these problems are parametric variants of shortest path problems, minimum cost flow and maximum flow problems, spanning tree problems, the knapsack problem, and matching problems. Overall, we cover the results from 128 publications (and refer to 35 supplemental works) published between 1963 and 2024.

Keywords: Parametric optimization; Parametric programming; Approximation algorithms; Combinatorial optimization; Survey (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-025-01512-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:93:y:2025:i:1:d:10.1007_s10898-025-01512-6

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-025-01512-6

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().