Pith. sign in

REVIEW 4 major objections 3 minor 38 references

On the Complexity of Recoverable Robust Optimization in the Polynomial Hierarchy

T0 review · 4 major / 3 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read For 24 classic problems, recoverable robust optimization is Sigma-3-p-complete

desk verdict A genuinely useful framework with a mostly coherent core reduction, but the full 24-problem completeness list is not proven: several appendix reductions violate the blow-up-preserving premise, and Theorem 10's cost-reduction argument has a gap. read the letter →

arxiv 2411.18590 v1 pith:CCUD3UNR submitted 2024-11-27 cs.CC cs.DMmath.OC

Christoph Grüne , Lasse Wulf This is my paper · ORCID
classification cs.CCcs.DMmath.OC MSC 68Q1768Q1590C27
keywords recoverablerobustoptimizationpolynomialhierarchySigma-3-completenessdiscretebudgeteduncertaintymin-max-minproblemscompactintegerprogrammingSSPreductionstwo-stage
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper claims that for each of 24 classic NP-complete problems—satisfiability, vertex cover, dominating set, subset sum, TSP, Steiner tree, and others—the recoverable robust optimization problem under discrete budgeted uncertainty is $\Sigma^p_3$-complete (complete for the third level of the polynomial hierarchy). This holds for all three standard distance measures: $\kappa$-addition, $\kappa$-deletion, and Hamming. The result matters because a $\Sigma^p_3$-complete problem admits no compact (polynomial-size) integer programming formulation unless $\mathrm{NP} = \Sigma^p_3$, so these models are fundamentally hard to express. The paper's main contribution is showing that all these problems are hard 'for the same reason': they satisfy an abstract property that forces their recoverable robust counterparts to be $\Sigma^p_3$-complete.

What carries the argument

The load-bearing device is the blow-up SSP reduction: an SSP reduction from 3-SAT to a problem $\Pi$ that, for a chosen set $L_b$ of literals closed under negation, builds an instance with a polynomial blow-up factor $\beta$ such that two solutions have distance at most $\beta$ iff they agree on the image of $L_b$. Because blow-up SSP reductions are not transitive, the paper adds the blow-up preserving SSP reduction, which only introduces elements that are always or never in solutions, preserving distances exactly. These two gadgets compose into a reduction tree rooted at 3-SAT and yield $\Sigma^p_3$-hardness of the combinatorial recoverable robust problem, which a short reduction converts into completeness for the cost-based recoverable robust problem.

What would settle it

Inspect the reductions labelled blow-up preserving in the paper's own presentation. For the Subset Sum-to-Partition reduction, take any small instance and check whether the element 'sum of all numbers + 1 minus M' belongs to every balanced partition; a single balanced partition omitting it refutes the 'always-in' classification. For the Vertex Cover-to-Dominating Set reduction, check whether any added edge vertex can belong to a dominating set of size k'; if so, the 'never-in-solution' classification fails.

Watch

Extended reading notes

Core claim

On its own terms, the central claim is that the recoverable robust version of every listed nominal problem is $\Sigma^p_3$-complete under discrete budgeted uncertainty, for each of the three distance measures. More generally, the paper identifies a sufficient abstract condition: if an SSP problem is blow-up SSP reducible from 3-SAT and the reduction chain can be extended by blow-up preserving SSP reductions, then the combinatorial recoverable robust problem is $\Sigma^p_3$-hard; a short cost-gadget reduction transfers this hardness to the standard linear recoverable robust problem. The paper proves this transfer and applies it to 24 problems, thereby unifying and extending known $\Sigma^p_3$-completeness results for clique/independent set, TSP, shortest path, and others.

Load-bearing premise

The argument rests on every reduction chain beyond the first blow-up reduction being a blow-up preserving SSP reduction: each newly introduced universe element is either in every solution or in no solution, so the distance between solutions is unchanged; if one of the listed reductions violates this partition property, the hardness proof for that problem does not go through.

Editorial extensions

If this is right

  • Every one of the 24 recoverable robust problems listed in the paper, with any of the three distance measures, is $\Sigma^p_3$-complete under discrete budgeted uncertainty.
  • None of these problems admits a compact integer programming formulation unless $\mathrm{NP} = \Sigma^p_3$, so exact solution via standard compact IP models is inherently blocked.
  • The framework supplies a reusable certificate: a new nominal problem only needs to be shown blow-up SSP reducible from 3-SAT, or blow-up preserving reducible from an already classified problem, to inherit $\Sigma^p_3$-completeness.
  • The three distance measures are covered by a single mechanism because the blow-up gadget is compatible with $\kappa$-addition, $\kappa$-deletion, and Hamming distances.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the reduction premises are repaired for the affected problems, the same abstract property would likely apply to further NP-complete problems beyond the 24 listed, since only a handful of base reductions are needed.
  • The result suggests that recoverable robust versions of even polynomial-time nominal problems, such as shortest path, may be $\Sigma^p_3$-complete when a distance constraint is added; the paper cites one such case, and the framework's logic points to more.
  • The near-absence of compact IP formulations for these problems redirects practical research toward approximation algorithms, heuristics, or restricted uncertainty sets rather than exact compact modeling.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 3 minor

Summary. The paper develops an abstract framework for proving Σ3^p-completeness of recoverable robust optimization problems with discrete budgeted uncertainty. It formalizes linear optimization problems, SSP problems, SSP reductions, blow-up SSP reductions, and blow-up-preserving SSP reductions. The main reduction (Theorem 9) goes from R-Adj-Sat to the combinatorial recoverable robust problem of any SSP-NP-hard problem admitting a blow-up SSP reduction from 3Sat, and Theorem 10 transfers the hardness to the cost-based recoverable robust problem. Section 5.1 presents a blow-up SSP reduction from 3Sat to Vertex Cover and states analogous reductions for independent set, subset sum, directed Hamiltonian path, two directed disjoint paths, and Steiner tree. Section 6 and Appendix B then use blow-up-preserving reductions to extend the result to a list of 24 nominal problems and three distance measures: κ-addition, κ-deletion, and Hamming distance.

Significance. If the framework and the reduction list are correct, the paper would be a substantial unification: it would show that recoverable robust versions of many unrelated NP-complete problems are Σ3^p-complete for the same structural reason, and it would rule out compact IP formulations for all of them under NP ≠ Σ3^p. The main reduction in Theorem 9 is conceptually clean and mostly correct, and the blow-up gadget in Section 5.1 is a useful reusable device. However, the claimed full list is not currently established: three of the preserving reductions — Dominating Set, Partition, and Feedback Arc Set — violate Definition 13, and the consequences for Scheduling via Partition are also unsupported. The significance of the paper therefore hinges on repairing or removing these reductions.

major comments (4)
  1. [Section 6.1, Claim 19] The reduction from Vertex Cover to Dominating Set is claimed to be blow-up preserving with Uoff equal to the set of added edge vertices. This is false. In the instance consisting of a single edge {u,v} with k=1, the added vertex w_{uv}^1 alone dominates u', v', and itself, so it is a dominating set of size 1. Thus added edge vertices do occur in valid solutions, contradicting the definition of Uoff. Moreover, the SSP equality in Claim 18 fails for this instance: the dominating set {w_{uv}^1} has empty intersection with f(V), which is not a vertex cover of the original graph, violating Eq. (1). Consequently, Theorem 14 cannot be applied, and the Σ3^p-hardness of recoverable robust Dominating Set is not established.
  2. [Appendix B, Partition] The reduction from Subset Sum to Partition declares Uon = {Σa_i + 1 − M} and Uoff = {M + 1}. For the Subset Sum instance {1,5} with M=1, the constructed Partition instance has total sum 14 and target 7; the set {5,2} is a valid side of a partition. Its intersection with f(U) = {1,5} is {5}, whose sum is not M, so Eq. (1) fails. The element x = Σa_i + 1 − M = 6 is not in every partition solution, and y = M + 1 = 2 is in this particular solution, so both Uon and Uoff are false. Therefore the blow-up-preserving chain from Subset Sum to Partition, and then to Two-Machine Scheduling, is unsupported, and RR-Partition and RR-Scheduling are not covered by Theorem 17.
  3. [Appendix B, Feedback Arc Set] The reduction from Vertex Cover to Feedback Arc Set puts all subdivided arcs between v'_1 and w'_0, and between w'_1 and v'_0, into Uoff. For a single-edge vertex-cover instance with k=1, the constructed directed graph has one directed cycle v'_0 → v'_1 → w'_0 → w'_1 → v'_0 (with subdivisions). Deleting a single subdivision arc on the path v'_1 → w'_0 makes the graph acyclic, giving a feedback arc set of size 1 whose intersection with f(V) is empty. Such a solution does not correspond to a vertex cover, so Eq. (1) fails and the subdivided arcs are not in Uoff. Thus the claimed blow-up-preserving reduction is invalid, and RR-Feedback Arc Set is not covered.
  4. [Theorem 10] The reduction from Comb.RR-Π' to RR-Π sets the upper cost of every u ∈ B to 2t(I)+1 and the threshold to t' = 2t(I). For this to make blocked elements prohibitively expensive, one needs 2t(I)+1 ≥ d(I)(u) for every blocked u, together with suitable nonnegativity assumptions; otherwise the 'blocked' upper bound can be lower than the nominal cost, and the simulation of blockers fails. The proof neither states nor derives such a condition. This gap is patchable, for instance by defining the upper cost as max(d(I)(u), 2t(I)+1) and adjusting the threshold, but as written Theorem 10 is not fully proved for arbitrary LOP problems.
minor comments (3)
  1. [Theorem 9, reverse direction] The line 'we have S1 ∩ fφ(Y) = S2 ∩ fφ(Y) by the property of a blow-up reduction' should refer to fφ(LX), not fφ(Y), because the blow-up property is defined for Lb = LX. The subsequent notation A2 ∩ (X ∪ X) = AX is also confusing and should be written in terms of LX.
  2. [Claim 19] Claim 19 is titled 'The reduction from above from Vertex Cover to Dominating Set is an SSP reduction', but the intended statement is that the reduction is blow-up preserving; the wording duplicates Claim 18 and should be corrected.
  3. [Appendix B, Set Cover definition] The SSP definition of Set Cover declares the universe to be {S_i | i = 1,...,n}, but the solution set is then defined as subsets S ⊆ ⋃_i S_i. A set cover solution should be a subfamily of the sets {S_i}; as written, the formal definition is inconsistent with the mapping f(v) = S_v used in the reduction.

Circularity Check

1 steps flagged · score 4.0 of 10

Self-citation carries the Dominating Set link; Partition and Feedback-Arc-Set Uon/Uoff classifications are asserted, not derived. The core framework itself is not circular.

  1. self citation load bearing [Section 6.1, Claims 18-19 (Vertex Cover to Dominating Set); relied on by Theorem 17.]
    "The correctness proof of the reduction itself is presented in [21]. ; Moreover, all vertices of {vwi :{v,w}∈ E, 1≤i≤|V| + 1} are never part of a solution of size k′."

    Dominating Set's Sigma_3^p-completeness in Theorem 17 requires the VC-to-DS map to be a blow-up preserving SSP reduction, so every added edge-vertex must lie in Uoff, i.e. in no solution. Claim 18 writes the target SSP equality {v′ : v∈S} = {S′∩f(V) : S′∈S_DS} as if it were the proof, and Claim 19 asserts the Uoff classification without derivation. The only external justification offered is [21], a preprint by the same two authors. The classification is false: for a one-edge graph and k=1, a single edge-vertex is a dominating set of size 1. Thus this entry's derivation reduces to an unverified self-citation plus a by-fiat partition rather than to an independent argument.

full rationale

The main derivation is not circular: Theorems 9, 10, and 14 are direct proofs, and the reduction source R-Adj-Sat [19] is a published, externally checkable result, not a smuggled premise. The blow-up reductions in Section 5.1 construct gadgets and verify their beta_I thresholds explicitly. Reusing definitions and transitivity lemmas from [21] is ordinary self-citation and does not by itself carry the framework. The Dominating Set entry is different: Claim 18's formal equality is essentially the SSP condition restated, Claim 19 asserts the required Uoff partition without proof, and the cited correctness proof is the authors' own earlier work. That is load-bearing self-citation, and the asserted partition is false. Separately, the appendix reductions for Partition and Feedback Arc Set contain unsupported Uon/Uoff classifications; for example, Partition says 'we have f(a)=a, Uon={Σ_i a_i + 1−M}, and Uoff={M+1}' without proving those elements have the defining always/never-in-solution property, and for {a_i}={1,5}, M=1 the valid partition {5,2} omits the alleged Uon element. These are non-circular correctness gaps in specific applications, not additional circularity, so they do not raise the score beyond the self-citation issue. Overall the framework has independent content; score 4.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central claim rests on standard complexity assumptions (polynomial hierarchy, NP != Sigma-3-p for the compact IP corollary), the known completeness of R-Adj-Sat used as the reduction source, and the paper's own definitions of blow-up reductions which serve as sufficient conditions. No numeric parameters are fitted to data. The main unstated domain assumption is nonnegativity of costs in Theorem 10.

assumptions (4)
  • standard math R-Adj-Sat is Sigma-3-p-complete
    The reduction in Theorem 9 starts from R-Adj-Sat, a result proven in [19], which is co-authored by Wulf. The current paper only sketches the argument and does not re-prove it.
  • standard math SSP-NP-completeness framework from [21]
    Definitions of LOP, SSP, SSP reductions and transitivity are taken from the authors' earlier paper [21]; the paper reuses them without proof.
  • domain assumption Nonnegative costs for LOP problems in Theorem 10
    The proof that a feasible pair (S1,S2) with c1(S1)+c2(S2) <= 2t implies S1,S2 in S(I) requires d(u) >= 0; the LOP definition allows arbitrary integer d, and this is not stated as an assumption.
  • domain assumption Distance measures satisfy invariance under injective maps and union
    The transitivity proof (Theorem 14) uses these properties of the three distance measures; the paper verifies them informally in Definition 5.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On the Complexity of Recoverable Robust Optimization in the Polynomial Hierarchy." pith.science (2026). https://pith.science/paper/CCUD3UNR

@misc{pith2026241118590,
  author       = {Pith},
  title        = {Pith review of: On the Complexity of Recoverable Robust Optimization in the Polynomial Hierarchy},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CCUD3UNR}},
  note         = {Machine review of arXiv:2411.18590}
}
abstract

Recoverable robust optimization is a popular multi-stage approach, in which it is possible to adjust a first-stage solution after the uncertain cost scenario is revealed. We consider recoverable robust optimization in combination with discrete budgeted uncertainty. In this setting, it seems plausible that many problems become $\Sigma^p_3$-complete and therefore it is impossible to find compact IP formulations of them (unless the unlikely conjecture NP $= \Sigma^p_3$ holds). Even though this seems plausible, few concrete results of this kind are known. In this paper, we fill that gap of knowledge. We consider recoverable robust optimization for the nominal problems of Sat, 3Sat, vertex cover, dominating set, set cover, hitting set, feedback vertex set, feedback arc set, uncapacitated facility location, $p$-center, $p$-median, independent set, clique, subset sum, knapsack, partition, scheduling, Hamiltonian path/cycle (directed/undirected), TSP, $k$-disjoint path ($k \geq 2$), and Steiner tree. We show that for each of these problems, and for each of three widely used distance measures, the recoverable robust problem becomes $\Sigma^p_3$-complete. Concretely, we show that all these problems share a certain abstract property and prove that this property implies that their robust recoverable counterpart is $\Sigma^p_3$-complete. This reveals the insight that all the above problems are $\Sigma^p_3$-complete 'for the same reason'. Our result extends a recent framework by Gr\"une and Wulf.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

38 extracted references · 26 canonical work pages

  1. [1]

    Computational Complexity - A Modern Approach

    Sanjeev Arora and Boaz Barak. Computational Complexity - A Modern Approach . Cambridge University Press, 2009. URL: http://www.cambridge.org/catalogue/catalogue.asp?isbn=9780521424264

    2009

  2. [2]

    Robust Optimization , volume 28 of Princeton Series in Applied Mathematics

    Aharon Ben - Tal, Laurent El Ghaoui, and Arkadi Nemirovski. Robust Optimization , volume 28 of Princeton Series in Applied Mathematics . Princeton University Press, 2009. https://doi.org/10.1515/9781400831050 doi:10.1515/9781400831050

    doi:10.1515/9781400831050 2009

  3. [3]

    Robust discrete optimization and network flows

    Dimitris Bertsimas and Melvyn Sim. Robust discrete optimization and network flows. Math. Program. , 98(1-3):49--71, 2003. URL: https://doi.org/10.1007/s10107-003-0396-4, https://doi.org/10.1007/S10107-003-0396-4 doi:10.1007/S10107-003-0396-4

    work page doi:10.1007/s10107-003-0396-4 2003

  4. [4]

    Investigating the recoverable robust single machine scheduling problem under interval uncertainty

    Matthew Bold and Marc Goerigk. Investigating the recoverable robust single machine scheduling problem under interval uncertainty. Discret. Appl. Math. , 313:99--114, 2022. https://doi.org/10.1016/j.dam.2022.02.005 doi:10.1016/j.dam.2022.02.005

    doi:10.1016/j.dam.2022.02.005 2022

  5. [5]

    Recoverable robustness in combinatorial optimization

    Christina B \"u sing. Recoverable robustness in combinatorial optimization . Cuvillier Verlag, 2011

    work page 2011

  6. [6]

    Recoverable robust shortest path problems

    Christina B \" u sing. Recoverable robust shortest path problems. Networks , 59(1):181--189, 2012. https://doi.org/10.1002/net.20487 doi:10.1002/net.20487

    work page doi:10.1002/net.20487 2012

  7. [7]

    Christina B \" u sing, Sebastian Goderbauer, Arie M. C. A. Koster, and Manuel Kutschka. Formulations and algorithms for the recoverable \( \) -robust knapsack problem. EURO J. Comput. Optim. , 7(1):15--45, 2019. https://doi.org/10.1007/s13675-018-0107-9 doi:10.1007/s13675-018-0107-9

    work page doi:10.1007/s13675-018-0107-9 2019

  8. [8]

    Christina B \" u sing, Arie M. C. A. Koster, and Manuel Kutschka. Recoverable robust knapsacks: \( \) -scenarios. In Julia Pahl, Torsten Reiners, and Stefan Vo , editors, Network Optimization - 5th International Conference, INOC 2011, Hamburg, Germany, June 13-16, 2011. Proceedings , volume 6701 of Lecture Notes in Computer Science , pages 583--588. Sprin...

    work page doi:10.1007/978-3-642-21527-8 2011

Show all 38 references
  1. [9]

    Christina B \" u sing, Arie M. C. A. Koster, and Manuel Kutschka. Recoverable robust knapsacks: the discrete scenario case. Optim. Lett. , 5(3):379--392, 2011. https://doi.org/10.1007/s11590-011-0307-1 doi:10.1007/s11590-011-0307-1

    2011 doi

  2. [10]

    Chassein and Marc Goerigk

    Andr \' e B. Chassein and Marc Goerigk. On the recoverable robust traveling salesman problem. Optim. Lett. , 10(7):1479--1492, 2016. https://doi.org/10.1007/s11590-015-0949-5 doi:10.1007/s11590-015-0949-5

    2016 doi

  3. [11]

    Chassein, Marc Goerigk, Adam Kasperski, and Pawel Zielinski

    Andr \' e B. Chassein, Marc Goerigk, Adam Kasperski, and Pawel Zielinski. On recoverable and two-stage robust selection problems with budgeted uncertainty. Eur. J. Oper. Res. , 265(2):423--436, 2018. https://doi.org/10.1016/j.ejor.2017.08.013 doi:10.1016/j.ejor.2017.08.013

    2018 doi

  4. [12]

    The uncapicitated facility location problem

    G \'e rard Cornu \'e jols, George Nemhauser, and Laurence Wolsey. The uncapicitated facility location problem. Technical report, Cornell University Operations Research and Industrial Engineering, 1983

    1983

  5. [13]

    Robust recoverable perfect matchings

    Mitre Costa Dourado, Dirk Meierling, Lucia Draque Penso, Dieter Rautenbach, F \' a bio Protti, and Aline Ribeiro de Almeida. Robust recoverable perfect matchings. Networks , 66(3):210--213, 2015. https://doi.org/10.1002/net.21624 doi:10.1002/net.21624

    2015 doi

  6. [14]

    Hartmann, Stefan Lendl, and Gerhard J

    Dennis Fischer, Tim A. Hartmann, Stefan Lendl, and Gerhard J. Woeginger. An investigation of the recoverable robust assignment problem. In Petr A. Golovach and Meirav Zehavi, editors, 16th International Symposium on Parameterized and Exact Computation, IPEC 2021, September 8-1...

    2021 doi

  7. [15]

    Hopcroft, and James Wyllie

    Steven Fortune, John E. Hopcroft, and James Wyllie. The directed subgraph homeomorphism problem. Theor. Comput. Sci. , 10:111--121, 1980. https://doi.org/10.1016/0304-3975(80)90009-2 doi:10.1016/0304-3975(80)90009-2

    1980 doi

  8. [16]

    M. R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness . W. H. Freeman, 1979

    1979

  9. [17]

    An Introduction to Robust Combinatorial Optimization , volume 361 of International Series in Operations Research & Management Science

    Marc Goerigk and Michael Hartisch. An Introduction to Robust Combinatorial Optimization , volume 361 of International Series in Operations Research & Management Science . Springer, 2024

    2024

  10. [18]

    Recoverable robust representatives selection problems with discrete budgeted uncertainty

    Marc Goerigk, Stefan Lendl, and Lasse Wulf. Recoverable robust representatives selection problems with discrete budgeted uncertainty. Eur. J. Oper. Res. , 303(2):567--580, 2022. https://doi.org/10.1016/j.ejor.2022.03.001 doi:10.1016/j.ejor.2022.03.001

    2022 doi

  11. [19]

    On the complexity of robust multi-stage problems with discrete recourse

    Marc Goerigk, Stefan Lendl, and Lasse Wulf. On the complexity of robust multi-stage problems with discrete recourse. Discret. Appl. Math. , 343:355--370, 2024. URL: https://doi.org/10.1016/j.dam.2023.10.018, https://doi.org/10.1016/J.DAM.2023.10.018 doi:10.1016/J.DAM.2023.10.018

    2024 doi

  12. [20]

    The complexity classes of hamming distance recoverable robust problems

    Christoph Gr \" u ne. The complexity classes of hamming distance recoverable robust problems. In Jos \' e A. Soto and Andreas Wiese, editors, LATIN 2024: Theoretical Informatics - 16th Latin American Symposium, Puerto Varas, Chile, March 18-22, 2024, Proceedings, Part I , volu...

    2024 doi

  13. [21]

    Completeness in the polynomial hierarchy for many natural problems in bilevel and robust optimization

    Christoph Gr \" u ne and Lasse Wulf. Completeness in the polynomial hierarchy for many natural problems in bilevel and robust optimization. CoRR , abs/2311.10540, 2023. URL: https://doi.org/10.48550/arXiv.2311.10540, http://arxiv.org/abs/2311.10540 arXiv:2311.10540 , https://d...

    2023 doi

  14. [22]

    Recoverable robust optimization with commitment

    Felix Hommelsheim, Nicole Megow, Komal Muluk, and Britta Peis. Recoverable robust optimization with commitment. CoRR , abs/2306.08546, 2023. URL: https://doi.org/10.48550/arXiv.2306.08546, http://arxiv.org/abs/2306.08546 arXiv:2306.08546 , https://doi.org/10.48550/ARXIV.2306.0...

    2023 doi arXiv

  15. [23]

    Recoverable robust spanning tree problem under interval uncertainty representations

    Mikita Hradovich, Adam Kasperski, and Pawel Zielinski. Recoverable robust spanning tree problem under interval uncertainty representations. J. Comb. Optim. , 34(2):554--573, 2017. https://doi.org/10.1007/s10878-016-0089-6 doi:10.1007/s10878-016-0089-6

    2017 doi

  16. [24]

    The recoverable robust spanning tree problem with interval costs is polynomially solvable

    Mikita Hradovich, Adam Kasperski, and Pawel Zielinski. The recoverable robust spanning tree problem with interval costs is polynomially solvable. Optim. Lett. , 11(1):17--30, 2017. URL: https://doi.org/10.1007/s11590-016-1057-x, https://doi.org/10.1007/S11590-016-1057-X doi:10...

    2017 doi

  17. [25]

    Computational complexity of the recoverable robust shortest path problem with discrete recourse

    Marcel Jackiewicz, Adam Kasperski, and Pawel Zielinski. Computational complexity of the recoverable robust shortest path problem with discrete recourse. CoRR , abs/2403.20000, 2024. URL: https://doi.org/10.48550/arXiv.2403.20000, http://arxiv.org/abs/2403.20000 arXiv:2403.2000...

    2024 doi arXiv

  18. [26]

    Recoverable robust shortest path problem under interval uncertainty representations

    Marcel Jackiewicz, Adam Kasperski, and Pawel Zielinski. Recoverable robust shortest path problem under interval uncertainty representations. CoRR , abs/2401.05715, 2024. URL: https://doi.org/10.48550/arXiv.2401.05715, http://arxiv.org/abs/2401.05715 arXiv:2401.05715 , https://...

    2024 doi

  19. [27]

    Jeroslow

    Robert G. Jeroslow. The polynomial hierarchy and a simple model for competitive analysis. Math. Program. , 32(2):146--164, 1985. https://doi.org/10.1007/BF01586088 doi:10.1007/BF01586088

    1985 doi

  20. [28]

    New classes of complete problems for the second level of the polynomial hierarchy

    Berit Johannes. New classes of complete problems for the second level of the polynomial hierarchy. 2011

    2011

  21. [29]

    Richard M. Karp. Reducibility among combinatorial problems. In Raymond E. Miller and James W. Thatcher, editors, Proceedings of a symposium on the Complexity of Computer Computations, held March 20-22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New Yo...

    1972 doi

  22. [30]

    Robust recoverable and two-stage selection problems

    Adam Kasperski and Pawel Zielinski. Robust recoverable and two-stage selection problems. Discret. Appl. Math. , 233:52--64, 2017. https://doi.org/10.1016/j.dam.2017.08.014 doi:10.1016/j.dam.2017.08.014

    2017 doi

  23. [31]

    Robust discrete optimization and its applications , volume 14

    Panos Kouvelis and Gang Yu. Robust discrete optimization and its applications , volume 14. Springer Science & Business Media, 2013

    2013

  24. [32]

    Woeginger

    Thomas Lachmann, Stefan Lendl, and Gerhard J. Woeginger. A linear time algorithm for the robust recoverable selection problem. Discret. Appl. Math. , 303:94--107, 2021. https://doi.org/10.1016/j.dam.2020.08.012 doi:10.1016/j.dam.2020.08.012

    2021 doi

  25. [33]

    Matroid bases with cardinality constraints on the intersection

    Stefan Lendl, Britta Peis, and Veerle Timmermans. Matroid bases with cardinality constraints on the intersection. Math. Program. , 194(1):661--684, 2022. URL: https://doi.org/10.1007/s10107-021-01642-1, https://doi.org/10.1007/S10107-021-01642-1 doi:10.1007/S10107-021-01642-1

    2022 doi

  26. [34]

    u bbecke, Rolf H. M \

    Christian Liebchen, Marco E. L \" u bbecke, Rolf H. M \" o hring, and Sebastian Stiller. The concept of recoverable robustness, linear programming recovery, and railway applications. In Ravindra K. Ahuja, Rolf H. M \" o hring, and Christos D. Zaroliagis, editors, Robust and On...

    2009 doi

  27. [35]

    Papadimitriou

    Christos H. Papadimitriou. Computational complexity . Addison-Wesley, 1994

    1994

  28. [36]

    Introduction to the theory of computation

    Michael Sipser. Introduction to the theory of computation . PWS Publishing Company, 1997

    1997

  29. [37]

    Stockmeyer

    Larry J. Stockmeyer. The polynomial-time hierarchy. Theor. Comput. Sci. , 3(1):1--22, 1976. https://doi.org/10.1016/0304-3975(76)90061-X doi:10.1016/0304-3975(76)90061-X

    1976 doi

  30. [38]

    Woeginger

    Gerhard J. Woeginger. The trouble with the second quantifier. 4OR , 19(2):157--181, 2021. https://doi.org/10.1007/s10288-021-00477-y doi:10.1007/s10288-021-00477-y

    2021 doi

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.