pith. sign in

arxiv: 2606.17552 · v1 · pith:XHZK4CSJnew · submitted 2026-06-16 · 🧮 math.OC · cs.DM

An Adaptive Algorithm for the Approximation of General Linear-Parametric Optimization Problems

Levin Nemesch , Stefan Ruzika , Clemens Thielen , Alina Wittmann This is my paper

Pith reviewed 2026-06-26 23:58 UTC · model grok-4.3

classification 🧮 math.OC cs.DM
keywords parametric optimizationapproximation algorithmsmulti-parametric problemslinear optimizationadaptive algorithmsparameter setsmulti-objective optimization
0
0 comments X

The pith

A new adaptive algorithm approximates linear-multi-parametric optimization problems with negative parameter dependencies and arbitrary parameter sets.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes a new adaptive algorithm for computing approximation sets, and in some cases exact solution sets, for linear-multi-parametric optimization problems. Previous methods were restricted to non-negative parameter dependencies and the positive orthant; the new procedure removes these limits by generalizing techniques from both parametric optimization and multi-objective optimization. A reader would care because the broader applicability covers realistic cases where parameters can decrease objective values or range over any set. The work also supplies structural results on transforming parameter sets and shows that assuming non-negative optimal objective values over the entire parameter set fails to guarantee approximability for maximization problems.

Core claim

By generalizing existing algorithms from parametric and multi-objective optimization, the authors obtain an adaptive procedure that computes approximation sets for linear-multi-parametric problems under general parameter dependencies and arbitrary parameter sets. The procedure requires no additional restrictions beyond those of the source algorithms. Structural results on parameter-set transformations are derived, and it is shown that non-negative optimal objective values over the parameter set do not suffice for approximability in the maximization case.

What carries the argument

An adaptive approximation algorithm obtained by generalizing existing parametric and multi-objective optimization algorithms, extended to negative dependencies and general parameter sets.

If this is right

  • Approximation sets can be computed for problems that include negative parameter dependencies.
  • The algorithm applies to parameter sets not restricted to the positive orthant.
  • Structural results on transforming parameter sets become available for use in algorithm design.
  • Non-negative optimal objective values over the parameter set do not ensure approximability for maximization problems.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same adaptive framework may serve as an exact solver when the underlying non-parametric problem admits exact solution in polynomial time.
  • The structural results on parameter-set transformations could be used to reduce new problem families to already-solved ones.

Load-bearing premise

That generalizing the source algorithms from parametric and multi-objective optimization does not introduce restrictions that block application to problems with negative dependencies and arbitrary parameter sets.

What would settle it

A concrete linear-multi-parametric instance with a negative parameter dependency on which the algorithm produces an approximation set that misses an approximate solution for some parameter vector would falsify the claim.

Figures

Figures reproduced from arXiv: 2606.17552 by Alina Wittmann, Clemens Thielen, Levin Nemesch, Stefan Ruzika.

Figure 1
Figure 1. Figure 1: A single refining step in Algorithm 1 (for a 1-parametric problem with Λ = [λmin, λmax]): The two solutions x 0 and x 1 are already known and the intersection of their halfspaces H(x 0 ) and H(x 1 ) bounds the polyhedron A({x 0 , x1}). Algorithm 1 picks the vertex (λ, z) of A({x 0 , x1}) and, through Algα , computes an α-approximate solution x 2 ∈ Xpol for Π(λ). If (1 + ε) · Fλ(x 2 ) < z, the halfspace H(x… view at source ↗
Figure 2
Figure 2. Figure 2: An example for a 2-dimensional parameter set Λ and a possible triangulation. This section consists of two parts. We provide an overview before going into more detail. In the first part, we construct an intermediary problem instance ΠW where the parameter set W is a cone, the so-called homogenization [32] of Λ. Furthermore, we show that, for every ε ≥ 0 and α ≥ 0, • every (1 + ε)-approximation set for ΠW is… view at source ↗
Figure 3
Figure 3. Figure 3: The set W is a (polyhedral) cone and, since we assume Λ to be p-dimensional, W is (p + 1)-dimensional. As notational shorthand, we define the function L: R p+1 → R p , L(w) = L(w1, . . . , wp+1) := (w1, . . . , wp). For the homogenization W, there exist generators V = {v 1 , . . . , vs} ⊆ Qp+1 and R = {r 1 , . . . , rt} ⊆ Qp+1 such that v i p+1 = 1 for i = 1, . . . , s and r j p+1 = 0 for j = 1, . . . , t,… view at source ↗
Figure 3
Figure 3. Figure 3: Geometric interpretation of the homogenization W of the parameter set Λ = {λ ∈ R : λ ≥ λmin}. The set Λ is a 1-dimensional polyhedron in R, and W is a 2-dimensional cone in R 2 . The intersection of W and the “ξ = 1”-plane is exactly the set Λ × {1} = {(λ, 1) : λ ∈ Λ}. For each point (λ, 1) ∈ Λ × {1}, W contains all points a · (λ, 1) with a ≥ 0. In addition, W contains the closure of the set of all these p… view at source ↗
Figure 4
Figure 4. Figure 4: Geometric interpretation of the construction of P (for the example from [PITH_FULL_IMAGE:figures/full_fig_p025_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: An example of the sets Y 1 and Y 2 for MOP1 and MOP2 , respectively. The non-dominated extreme points y 0 , . . . , yN are ordered by increasing first components. denote the determinant of the square matrix consisting of only the first two entries of y i and y j . Due to the ordering of y 1 , . . . , yN , it holds that det(y i , yj ) < 0 for 1 ≤ i < j. Furthermore, for every choice of i, j, ℓ with 1 ≤ i < … view at source ↗
Figure 6
Figure 6. Figure 6: A geometric representation of the optimality regions for Π2 and for ∆(3) from the proof of Lemma 13. The optimality region Λ(x) for a solution x is the set {λ ∈ Λ : Fλ(x) = F ∗ (λ)}. Optimality regions are polyhedra and can only intersect at their boundaries (see [42]). The set ∆(i) is a subset of the set Λ(x i ), and the point λ i can be seen as the intersection of the lines containing the edges between Λ… view at source ↗
Figure 7
Figure 7. Figure 7: Graphical interpretation of the proof of Lemma 15: The parallelepipeds spanned by y i−1 −3 , yi −3  , and y i −3 , yi+1 are drawn with thin edges, and the parallelepiped spanned by y i−1 −3 , yi+1 −3  is drawn with thick edges. The dashed lines indicate the separation of the parallelepipeds into two halves each. volume of the parallelepiped spanned by the points y i −3 ) and y j −3 , i.e., det(y j , yi … view at source ↗
read the original abstract

Linear-multi-parametric optimization problems are a widely studied class of optimization problems. The objective function in such a problem is affine linear dependent on a parameter vector, and the goal is to compute a set of solutions that contains an optimal solution for every fixed parameter vector. However, this is known to be computationally challenging: The underlying non-parametric problem might be NP-hard, and, in addition, optimal solution sets might have exponential cardinality. Parametric approximation aims at providing polynomial-time algorithms that overcome these challenges. Instead of computing an optimal solution set, the goal is to compute an approximation set that contains only an approximate solution for every fixed parameter vector. Several new parametric approximation algorithms have been developed in recent literature. However, all of these share a common set of assumptions, which limits the class of parametric optimization problems that can be approximated. Namely, they do not allow negative parameter dependencies and have their parameter sets fixed to the positive orthant. We present a new adaptive approximation (and, also, exact) algorithm that can be applied to a wider class of linear-multi-parametric optimization problems. Our algorithm builds upon existing algorithms from both the fields of parametric and multi-objective optimization and generalizes these algorithms. In addition, we provide structural results for the transformation of parameter sets, and demonstrate that, for linear-multi-parametric maximization problems, the assumption of non-negative optimal objective values over the whole parameter set is not sufficient to ensure approximability.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper claims to introduce a new adaptive approximation (and exact) algorithm for linear-multi-parametric optimization problems that applies to a wider class, including negative parameter dependencies and general (not necessarily positive orthant) parameter sets. It generalizes existing algorithms from parametric and multi-objective optimization, provides structural results on parameter-set transformations, and demonstrates that non-negative optimal objective values are insufficient to ensure approximability for maximization problems.

Significance. If the central claims hold, the work would meaningfully broaden the scope of polynomial-time parametric approximation beyond the restrictive assumptions in prior literature, with potential applications in robust and multi-objective optimization. The structural transformation results, if rigorous and approximation-ratio preserving, represent a concrete technical contribution that could be reused.

major comments (2)
  1. [structural results section] The structural results on parameter-set transformations (the section presenting the lemmas that extend from the positive orthant to general sets with sign flips) must explicitly verify that the approximation guarantees of the combined parametric/multi-objective construction are retained. The abstract's own observation that non-negativity is insufficient for maximization approximability indicates that any such lemmas are load-bearing; without a direct argument ruling out the implied counter-examples, the extension to the wider class is not yet secured.
  2. [algorithm construction section] The adaptive algorithm construction (the section describing how the new algorithm is obtained by generalizing prior methods) needs to include a formal argument that the generalization introduces no hidden restrictions that would prevent application to arbitrary parameter sets or negative dependencies. The central claim of applicability to the wider class rests on this step.
minor comments (2)
  1. [abstract] Clarify in the abstract and introduction whether the exact version of the algorithm applies under the same widened assumptions or only in special cases.
  2. [preliminaries] Ensure all notation for parameter sets (e.g., the definition of the general parameter domain) is introduced before its first use in the structural results.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful review and constructive comments on our manuscript. The points raised identify areas where additional explicit arguments will strengthen the rigor of the structural results and algorithm generalization. We address each major comment below and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: [structural results section] The structural results on parameter-set transformations (the section presenting the lemmas that extend from the positive orthant to general sets with sign flips) must explicitly verify that the approximation guarantees of the combined parametric/multi-objective construction are retained. The abstract's own observation that non-negativity is insufficient for maximization approximability indicates that any such lemmas are load-bearing; without a direct argument ruling out the implied counter-examples, the extension to the wider class is not yet secured.

    Authors: We agree that the structural results require an explicit verification that approximation guarantees are retained. In the revised manuscript we will insert a new lemma (or proposition) immediately following the existing transformation lemmas. This lemma will prove that the sign-flip and general-set transformations preserve the approximation ratio of the combined parametric/multi-objective construction, and will contain a direct argument showing why the non-negativity counter-examples for maximization problems do not arise under our transformation rules. revision: yes

  2. Referee: [algorithm construction section] The adaptive algorithm construction (the section describing how the new algorithm is obtained by generalizing prior methods) needs to include a formal argument that the generalization introduces no hidden restrictions that would prevent application to arbitrary parameter sets or negative dependencies. The central claim of applicability to the wider class rests on this step.

    Authors: We acknowledge the need for a formal argument confirming the absence of hidden restrictions. The revised algorithm-construction section will contain an additional proposition that formally states the conditions under which the generalized adaptive algorithm inherits correctness and approximation properties from the cited parametric and multi-objective methods, together with a short proof that no further restrictions on the parameter set or sign pattern are introduced. revision: yes

Circularity Check

0 steps flagged

No circularity: generalization rests on independent prior algorithms and new structural results

full rationale

The paper derives its adaptive algorithm by explicitly combining and generalizing techniques from prior parametric approximation literature and multi-objective optimization, without defining any quantity in terms of itself or renaming fitted inputs as predictions. Structural results on parameter-set transformations are presented as new contributions rather than imported via self-citation chains. The explicit demonstration that non-negative objective values do not suffice for approximability in maximization cases is an independent negative result. No load-bearing step reduces to a self-defined quantity or unverified self-citation; the central claim remains externally grounded in the cited independent algorithms.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Based on abstract only; no free parameters, invented entities, or non-standard axioms are mentioned. The work relies on standard mathematical assumptions from linear and multi-objective optimization.

axioms (1)
  • standard math Standard assumptions underlying linear-multi-parametric optimization and multi-objective optimization algorithms
    The new algorithm builds upon existing algorithms from parametric and multi-objective optimization.

pith-pipeline@v0.9.1-grok · 5791 in / 1190 out tokens · 24556 ms · 2026-06-26T23:58:20.518032+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

48 extracted references · 43 canonical work pages

  1. [1]

    An approximation algorithm for a general class of parametric optimization problems

    C. Bazgan, A. Herzel, S. Ruzika, C. Thielen, and D. Vanderpooten. “An approximation algorithm for a general class of parametric optimization problems.” In:Journal of Combi- natorial Optimization43.5 (2022), pp. 1328–1358.doi:10.1007/s10878-020-00646-5. 32

    work page doi:10.1007/s10878-020-00646-5 2022

  2. [2]

    Finding minimal triangulations of convex 3-polytopes is NP-hard

    A. Below, J. De Loera, and J. Richter-Gebert. “Finding minimal triangulations of convex 3-polytopes is NP-hard.” In:Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 2000, pp. 65–66.url: https://dl.acm.org/doi/10.5555/ 338219.338235

    arXiv 2000

  3. [3]

    Output-sensitive complexity of multiobjective combinatorial optimization problems with an application to the multiobjective shortest path problem

    F. B¨ okler. “Output-sensitive complexity of multiobjective combinatorial optimization problems with an application to the multiobjective shortest path problem.” PhD thesis. Technische Universit¨ at Dortmund, 2018.doi:10.17877/DE290R-19130

    work page doi:10.17877/de290r-19130 2018

  4. [4]

    Output-sensitive algorithms for enumerating the extreme nondominated points of multiobjective combinatorial optimization problems

    F. B¨ okler and P. Mutzel. “Output-sensitive algorithms for enumerating the extreme nondominated points of multiobjective combinatorial optimization problems.” In:Pro- ceedings of the 23rd European Symposium on Algorithms (ESA). 2015, pp. 288–299.doi: 10.1007/978-3-662-48350-3_25

    work page doi:10.1007/978-3-662-48350-3_25 2015

  5. [5]

    PaMILO: a solver for multi-objective mixed integer linear optimization and beyond

    F. B¨ okler, L. Nemesch, and M. H. Wagner. “PaMILO: a solver for multi-objective mixed integer linear optimization and beyond.” In:Operations Research Proceedings 2022. 2023, pp. 163–170.doi:10.1007/978-3-031-24907-5_20

    work page doi:10.1007/978-3-031-24907-5_20 2022

  6. [6]

    PolySCIP

    R. Bornd¨ orfer, S. Schenker, M. Skutella, and T. Strunk. “PolySCIP.” In:Proceedings of the 5th International Congres on Mathematical Software (ICMS). 2016, pp. 259–264.doi: 10.1007/978-3-319-42432-3_32

    work page doi:10.1007/978-3-319-42432-3_32 2016

  7. [7]

    Complexity of some parametric integer and network programming prob- lems

    P. J. Carstensen. “Complexity of some parametric integer and network programming prob- lems.” In:Mathematical Programming26 (1983), pp. 64–75.doi:10.1007/BF02591893

    work page doi:10.1007/bf02591893 1983

  8. [8]

    An optimal convex hull algorithm in any fixed dimension

    B. Chazelle. “An optimal convex hull algorithm in any fixed dimension.” In:Discrete & Computational Geometry10 (1993), pp. 377–409.doi:10.1007/BF02573985

    work page doi:10.1007/bf02573985 1993

  9. [9]

    Inner approximation algorithm for solving linear multiobjective optimization problems

    L. Csirmaz. “Inner approximation algorithm for solving linear multiobjective optimization problems.” In:Optimization70.7 (2021), pp. 1487–1511.doi: 10.1080/02331934.2020. 1737692

    work page doi:10.1080/02331934.2020 2021

  10. [10]

    How good is the chord algorithm?

    C. Daskalakis, I. Diakonikolas, and M. Yannakakis. “How good is the chord algorithm?” In:SIAM Journal on Computing45.3 (2016), pp. 811–858.doi:10.1137/13093875X

    work page doi:10.1137/13093875x 2016

  11. [11]

    J. A. De Loera, J. Rambau, and F. Santos.Triangulations: Structures for Algorithms and Applications. 1st ed. Springer, 2010.doi:10.1007/978-3-642-12971-1

    work page doi:10.1007/978-3-642-12971-1 2010

  12. [12]

    Approximation of multiobjective optimization problems

    I. Diakonikolas. “Approximation of multiobjective optimization problems.” PhD thesis. Graduate School of Arts and Sciences, Columbia University, 2011.doi: 10.7916/D80K2GR9

    work page doi:10.7916/d80k2gr9 2011

  13. [13]

    Succinct approximate convex Pareto curves

    I. Diakonikolas and M. Yannakakis. “Succinct approximate convex Pareto curves.” In: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 2008, pp. 74–83

    2008

  14. [14]

    Multicriteria Optimization

    M. Ehrgott.Multicriteria Optimization. 2nd ed. Springer Berlin, Heidelberg, 2005.doi: 10.1007/3-540-27659-9

    work page doi:10.1007/3-540-27659-9 2005

  15. [15]

    A dual variant of Benson’s “outer approximation algorithm

    M. Ehrgott, A. L¨ ohne, and L. Shao. “A dual variant of Benson’s “outer approximation algorithm” for multiple objective linear programming.” In:Journal of Global Optimization 52.4 (2012), pp. 757–778.doi:10.1007/s10898-011-9709-y. 33

    work page doi:10.1007/s10898-011-9709-y 2012

  16. [16]

    An Approximation Algorithm for Convex Multi-Objective Pro- gramming Problems,

    M. Ehrgott, L. Shao, and A. Sch¨ obel. “An approximation algorithm for convex multi- objective programming problems.” In:Journal of Global Optimization50.3 (2011), pp. 397– 416.doi:10.1007/s10898-010-9588-7

    work page doi:10.1007/s10898-010-9588-7 2011

  17. [17]

    Mathematical techniques for efficient record segmen- tation in large shared databases

    M. J. Eisner and D. G. Severance. “Mathematical techniques for efficient record segmen- tation in large shared databases.” In:Journal of the ACM23.4 (1976), pp. 619–635.doi: 10.1145/321978.321982

    work page doi:10.1145/321978.321982 1976

  18. [18]

    Parametric multiple sequence alignment and phylogeny construction

    D. Fern´ andez-Baca, T. Sepp¨ al¨ ainen, and G. Slutzki. “Parametric multiple sequence alignment and phylogeny construction.” In:Journal of Discrete Algorithms2.2 (2004), pp. 271–287.doi:10.1016/S1570-8667(03)00078-9

    work page doi:10.1016/s1570-8667(03)00078-9 2004

  19. [19]

    Constructing the minimization diagram of a two-parameter problem

    D. Fern´ andez-Baca and S. Srinivasan. “Constructing the minimization diagram of a two-parameter problem.” In:Operations Research Letters10.2 (1991), pp. 87–93.doi: 10.1016/0167-6377(91)90092-4

    work page doi:10.1016/0167-6377(91)90092-4 1991

  20. [20]

    Approximation schemes for the parametric knapsack problem

    A. Giudici, P. Halffmann, S. Ruzika, and C. Thielen. “Approximation schemes for the parametric knapsack problem.” In:Information Processing Letters120 (2017), pp. 11–15. doi:10.1016/j.ipl.2016.12.003

    work page doi:10.1016/j.ipl.2016.12.003 2017

  21. [21]

    Approximability and hardness in multi-objective optimization

    C. Glaßer, C. Reitwießner, H. Schmitz, and M. Witek. “Approximability and hardness in multi-objective optimization.” In:Proceedings of the 6th Conference on Computability in Europe (CiE). 2010, pp. 180–189.doi:10.1007/978-3-642-13962-8_20

    work page doi:10.1007/978-3-642-13962-8_20 2010

  22. [22]

    Secure two- party quantum evaluation of unitaries against specious adversaries,

    M. Gr¨ otschel, L. Lov´ asz, and A. Schrijver. “Rational polyhedra.” In:Geometric Algorithms and Combinatorial Optimization. Springer, 1988, pp. 157–196.doi: 10.1007/978-3-642- 97881-4_7

    work page doi:10.1007/978-3-642- 1988

  23. [23]

    An FPTAS for the knapsack problem with parametric weights

    N. Halman, M. Holzhauser, and S. O. Krumke. “An FPTAS for the knapsack problem with parametric weights.” In:Operations Research Letters46.5 (2018), pp. 487–491.doi: 10.1016/j.orl.2018.07.005

    work page doi:10.1016/j.orl.2018.07.005 2018

  24. [24]

    Benson type algorithms for linear vector optimization and applications

    A. H. Hamel, A. L¨ ohne, and B. Rudloff. “Benson type algorithms for linear vector optimization and applications.” In:Journal of Global Optimization59.4 (2014), pp. 811– 836.doi:10.1007/s10898-013-0098-2

    work page doi:10.1007/s10898-013-0098-2 2014

  25. [25]

    An approximation algorithm for a general class of multi-parametric optimization problems

    S. Helfrich, A. Herzel, S. Ruzika, and C. Thielen. “An approximation algorithm for a general class of multi-parametric optimization problems.” In:Journal of Combinatorial Optimization44 (2022), pp. 1459–1494.doi:10.1007/s10878-022-00902-w

    work page doi:10.1007/s10878-022-00902-w 2022

  26. [26]

    K., Singh, A., Singh, B., et al

    S. Helfrich, S. Ruzika, and C. Thielen. “Efficiently constructing convex approximation sets in multiobjective optimization problems.” In:INFORMS Journal on Computing37.5 (2025), pp. 1223–1241.doi:10.1287/ijoc.2023.0220

    work page doi:10.1287/ijoc.2023.0220 2025

  27. [27]

    Approximation methods for multiobjective optimiza- tion problems: a survey

    A. Herzel, S. Ruzika, and C. Thielen. “Approximation methods for multiobjective optimiza- tion problems: a survey.” In:INFORMS Journal on Computing33.4 (2021), pp. 1284–1299. doi:10.1287/ijoc.2020.1028

    work page doi:10.1287/ijoc.2020.1028 2021

  28. [28]

    Geometric duality in multiple objective linear programming

    F. Heyde and A. L¨ ohne. “Geometric duality in multiple objective linear programming.” In:SIAM Journal on Optimization19.2 (2008), pp. 836–845.doi:10.1137/060674831. 34

    work page doi:10.1137/060674831 2008

  29. [29]

    An FPTAS for the parametric knapsack problem

    M. Holzhauser and S. O. Krumke. “An FPTAS for the parametric knapsack problem.” In: Information Processing Letters126 (2017), pp. 43–47.doi: 10.1016/j.ipl.2017.06.006

    work page doi:10.1016/j.ipl.2017.06.006 2017

  30. [30]

    The enumeration of the set of all efficient solutions for a linear multiple objective program

    H. Isermann. “The enumeration of the set of all efficient solutions for a linear multiple objective program.” In:Journal of the Operational Research Society28.3 (1977), pp. 711– 725.doi:10.1057/jors.1977.147

    work page doi:10.1057/jors.1977.147 1977

  31. [31]

    On generating all maximal independent sets

    D. S. Johnson, M. Yannakakis, and C. H. Papadimitriou. “On generating all maximal independent sets.” In:Information Processing Letters27.3 (1988), pp. 119–123.doi: 10.1016/0020-0190(88)90065-8

    work page doi:10.1016/0020-0190(88)90065-8 1988

  32. [32]

    Basic polyhedral theory

    V. Kaibel. “Basic polyhedral theory.” In:Wiley Encyclopedia of Operations Research and Management Science. John Wiley & Sons, Ltd, 2011.doi: https://doi.org/10.1002/ 9780470400531.eorms0091

    2011

  33. [33]

    A parametric characterization and an ε-approximation scheme for the minimization of a quasiconcave program

    N. Katoh and T. Ibaraki. “A parametric characterization and an ε-approximation scheme for the minimization of a quasiconcave program.” In:Discrete Applied Mathematics17.1 (1987), pp. 39–66.doi:10.1016/0166-218X(87)90006-0

    work page doi:10.1016/0166-218x(87)90006-0 1987

  34. [34]

    Subdivisions and triangulations of polytopes

    C. W. Lee and F. Santos. “Subdivisions and triangulations of polytopes.” In:Handbook of Discrete and Computational Geometry. 3rd ed. CRC Press, 2017. Chap. 16, pp. 415–447. doi:10.1201/9781315119601

    work page doi:10.1201/9781315119601 2017

  35. [35]

    Primal and dual algorithms for optimization over the efficient set

    Z. Liu and M. Ehrgott. “Primal and dual algorithms for optimization over the efficient set.” In:Optimization67.10 (2018), pp. 1661–1686.doi:10.1080/02331934.2018.1484922

    work page doi:10.1080/02331934.2018.1484922 2018

  36. [36]

    Primal and Dual Approximation Algorithms for Convex Vector Optimization Problems,

    A. L¨ ohne, B. Rudloff, and F. Ulus. “Primal and dual approximation algorithms for convex vector optimization problems.” In:Journal of Global Optimization60 (2014), pp. 713–736. doi:10.1007/s10898-013-0136-0

    work page doi:10.1007/s10898-013-0136-0 2014

  37. [37]

    The vector linear program solverBensolve– notes on theoretical background

    A. L¨ ohne and B. Weißing. “The vector linear program solverBensolve– notes on theoretical background.” In:European Journal of Operational Research260.3 (2017), pp. 807–813. doi:10.1016/j.ejor.2016.02.039

    work page doi:10.1016/j.ejor.2016.02.039 2017

  38. [38]

    Computational complexity of parametric linear programming

    K. G. Murty. “Computational complexity of parametric linear programming.” In:Mathe- matical Programming19.1 (1980), pp. 213–219.doi:10.1007/BF01581642

    work page doi:10.1007/bf01581642 1980

  39. [39]

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

    L. Nemesch, S. Ruzika, C. Thielen, and A. Wittmann. “A survey of exact and approxi- mation algorithms for linear-parametric optimization problems.” In:Journal of Global Optimization93 (2025), pp. 299–333.doi:10.1007/s10898-025-01512-6

    work page doi:10.1007/s10898-025-01512-6 2025

  40. [40]

    A polynomial-time inner approxi- mation algorithm for multiobjective and parametric optimization

    L. Nemesch, S. Ruzika, C. Thielen, and A. Wittmann. “A polynomial-time inner approxi- mation algorithm for multiobjective and parametric optimization.” In:INFORMS Journal on Computing(2026).doi:10.1287/ijoc.2025.1308

    work page doi:10.1287/ijoc.2025.1308 2026

  41. [41]

    On the approximability of trade-offs and optimal access of web sources

    C. Papadimitriou and M. Yannakakis. “On the approximability of trade-offs and optimal access of web sources.” In:Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS). 2000, pp. 86–92.doi:10.1109/SFCS.2000.892068. 35

    work page doi:10.1109/sfcs.2000.892068 2000

  42. [42]

    A recursive algorithm for finding all nondominated extreme points in the outcome set of a multiobjective integer programme

    A. Przybylski, X. Gandibleux, and M. Ehrgott. “A recursive algorithm for finding all nondominated extreme points in the outcome set of a multiobjective integer programme.” In:INFORMS Journal on Computing22.3 (2009), pp. 371–386.doi: 10.1287/ijoc.1090. 0342

    work page doi:10.1287/ijoc.1090 2009

  43. [43]

    Complexity results for multicriterial and parametric network flows using a pathological graph of Zadeh

    G. Ruhe. “Complexity results for multicriterial and parametric network flows using a pathological graph of Zadeh.” In:Zeitschrift f¨ ur Operations Research32 (1988), pp. 9–27. doi:10.1007/BF01920568

    work page doi:10.1007/bf01920568 1988

  44. [44]

    Schrijver.Theory of Linear and Integer Programming

    A. Schrijver.Theory of Linear and Integer Programming. Wiley, 1998.isbn: 978-0-471- 98232-6

    1998

  45. [45]

    The upper bound theorem for polytopes: an easy proof of its asymptotic version

    R. Seidel. “The upper bound theorem for polytopes: an easy proof of its asymptotic version.” In:Computational Geometry5.2 (1995), pp. 115–116.doi: 10 . 1016 / 0925 - 7721(95)00013-Y

    1995

  46. [46]

    R. J. Valenza.Linear Algebra. Springer, 1993.doi:10.1007/978-1-4612-0901-0

    work page doi:10.1007/978-1-4612-0901-0 1993

  47. [47]

    V. V. Vazirani.Approximation Algorithms. first. Springer, 2003.doi: 10.1007/978-3- 662-04565-7

    work page doi:10.1007/978-3- 2003

  48. [48]

    G. M. Ziegler.Lectures on Polytopes. 1st ed. Springer, 1995.doi: 10.1007/978-1-4613- 8431-1. Appendix A Number of Parameters in the Input Example 1.In this example, we demonstrate that, if p is not considered to be constant, we can construct a family of parametric minimization problems where the cardinality of every(1 +ε)-approximation set grows super-pol...

    work page doi:10.1007/978-1-4613- 1995