Image de couverture de livre

Completeness in the Polynomial Hierarchy for many natural Problems in Bilevel and Robust Optimization

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Grüne, Christoph, Wulf, Lasse
Format:	Preprint
Publié:	2023
Sujets:	Computational Complexity Discrete Mathematics Optimization and Control F.2.2
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

On the Complexity of Recoverable Robust Optimization in the Polynomial Hierarchy
par: Grüne, Christoph, et autres
Publié: (2024)

The Complexity of Blocking All Solutions
par: Grüne, Christoph, et autres
Publié: (2025)

A Compendium of Subset Search Problems and Reductions relating to the Parsimonious Property
par: Bartlett, Celina Janet
Publié: (2025)

NP-Completeness of the Combinatorial Distance Matrix Realisation Problem
par: Fairbairn, David L., et autres
Publié: (2024)

Towards Geometry-Preserving Reductions Between Constraint Satisfaction Problems (and other problems in NP)
par: Istrate, Gabriel
Publié: (2024)

A Decomposition Approach to the Weighted $k$-server Problem
par: Ayyadevara, Nikhil, et autres
Publié: (2024)

On Minimum Maximal Distance-k Matchings
par: Kartynnik, Yury, et autres
Publié: (2016)

The Gallai Vertex Problem is $Θ_2^p$-Complete
par: Nikabadi, Amir, et autres
Publié: (2026)

Complexity of Firefighting on Graphs
par: Althoetmar, Julius, et autres
Publié: (2025)

On Finding Randomly Planted Cliques in Arbitrary Graphs
par: Agrimonti, Francesco, et autres
Publié: (2025)

On the Complexity of Problems on Graphs Defined on Groups
par: Das, Bireswar, et autres
Publié: (2025)

Diffusion-Robust Optimization over Graphs
par: Aolaritei, Liviu, et autres
Publié: (2026)

Generalizing Brooks' theorem via Partial Coloring is Hard Classically and Locally
par: Bok, Jan, et autres
Publié: (2025)

Relaxation strength for multilinear optimization: McCormick strikes back
par: Schutte, Emily, et autres
Publié: (2023)

On the complexity of a maintenance problem for hierarchical systems
par: Schulz, Andreas S., et autres
Publié: (2023)

The Banach-Butterfly Invariant: Influence-Adaptive Walsh Geometry for Ternary Polynomial Threshold Functions
par: Pavlov, Gorgi
Publié: (2026)

On the Computational Complexity of Multi-Objective Ordinal Unconstrained Combinatorial Optimization
par: Figueira, José Rui, et autres
Publié: (2024)

Induced Disjoint Paths Without an Induced Minor
par: Aboulker, Pierre, et autres
Publié: (2025)

On the complexity of Sandwich Problems for $M$-partitions
par: Barsukov, Alexey, et autres
Publié: (2026)

On the hull and interval numbers of oriented graphs
par: Araujo, J., et autres
Publié: (2022)

Lasserre Hierarchy for Graph Isomorphism and Homomorphism Indistinguishability
par: Roberson, David E., et autres
Publié: (2023)

Prophet Inequalities: Separating Random Order from Order Selection
par: Giambartolomei, Giordano, et autres
Publié: (2023)

APTAS for bin packing with general cost structures
par: Jaykrishnan, G., et autres
Publié: (2024)

IID Prophet Inequality with Random Horizon: Going Beyond Increasing Hazard Rates
par: Giambartolomei, Giordano, et autres
Publié: (2024)

Revealing POMDPs: Qualitative and Quantitative Analysis for Parity Objectives
par: Asadi, Ali, et autres
Publié: (2025)

The connected Grundy coloring problem: Formulations and a local-search enhanced biased random-key genetic algorithm
par: Silva, Mateus C., et autres
Publié: (2024)

Sum-of-squares lower bounds for Non-Gaussian Component Analysis
par: Diakonikolas, Ilias, et autres
Publié: (2024)

Gromov's Approximating Tree and the All-Pairs Bottleneck Paths Problem
par: Cornect, Anders, et autres
Publié: (2024)

The vehicle routing problem with synchronization constraints and support vehicle-dependent service times
par: Wittwer, David, et autres
Publié: (2024)

Approximate Graph Colouring and the Crystal with a Hollow Shadow
par: Ciardo, Lorenzo, et autres
Publié: (2022)

Completeness in the Polynomial Hierarchy and PSPACE for many natural problems derived from NP
par: Grüne, Christoph, et autres
Publié: (2026)

Mim-Width is paraNP-complete
par: Bergougnoux, Benjamin, et autres
Publié: (2025)

Answering Related Questions
par: Bonnet, Édouard
Publié: (2025)

Treewidth Inapproximability and Tight ETH Lower Bound
par: Bonnet, Édouard
Publié: (2024)

Rankwidth of Graphs with Balanced Separations: Expansion for Dense Graphs
par: Anand, Emile
Publié: (2025)

Coloring Hardness on Low Twin-Width Graphs
par: Bonnet, Édouard
Publié: (2025)

A Parametrized Complexity View on Robust Scheduling with Budgeted Uncertainty
par: Goldberg, Noam, et autres
Publié: (2026)

Neural Networks and (Virtual) Extended Formulations
par: Hertrich, Christoph, et autres
Publié: (2024)

Price Optimal Routing in Public Transportation
par: Euler, Ricardo, et autres
Publié: (2022)

Arithmetic Circuits and Neural Networks for Regular Matroids
par: Hertrich, Christoph, et autres
Publié: (2025)