Cover Image

A Note on the Complexity of Bilevel Linear Programs in Fixed Dimensions

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Ketkov, Sergey S., Prokopyev, Oleg A.
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

On Big-M Reformulations of Bilevel Linear Programs: Hardness of A Posteriori Verification
by: Ketkov, Sergey S., et al.
Published: (2026)

On a class of interdiction problems with partition matroids: complexity and polynomial-time algorithms
by: Ketkov, Sergey S., et al.
Published: (2024)

Data-driven interdiction with asymmetric cost uncertainty: a distributionally robust optimization approach
by: Ketkov, Sergey S., et al.
Published: (2025)

A Note on the Complexity of Defensive Domination
by: Chaplick, Steven, et al.
Published: (2025)

On the Complexity of Combinatorial Optimization on Fixed Structures
by: Megiddo, Nimrod
Published: (2024)

A Note on the Complexity of Directed Clique
by: Gutowski, Grzegorz, et al.
Published: (2026)

Automatizing Software Cognitive Complexity Reduction through Integer Linear Programming
by: Saborido, Rubén, et al.
Published: (2024)

A Note on the Complexity of the Spectral Gap Problem
by: Yirka, Justin
Published: (2025)

The Parameterized Complexity of Computing the Linear Vertex Arboricity
by: Erhardt, Alexander, et al.
Published: (2025)

Computational Complexity and Integer Programming Formulation of the Oredango Puzzle
by: Takahata, Takuma, et al.
Published: (2025)

Tensor Ranks and the Fine-Grained Complexity of Dynamic Programming
by: Alman, Josh, et al.
Published: (2023)

The Mystery Deepens: On the Query Complexity of Tarski Fixed Points
by: Chen, Xi, et al.
Published: (2026)

Proof Complexity of Linear Logics
by: Tabatabai, Amirhossein Akbar, et al.
Published: (2026)

Training Neural Networks is NP-Hard in Fixed Dimension
by: Froese, Vincent, et al.
Published: (2023)

Tighter Bounds for the Randomized Polynomial-Time Simplex Algorithm for Linear Programming
by: Gibor, Daniel
Published: (2025)

The Complexity of Drawing Graphs on Few Lines and Few Planes
by: Chaplick, Steven, et al.
Published: (2016)

Explicit Directional Affine Extractors and Improved Hardness for Linear Branching Programs
by: Li, Xin, et al.
Published: (2023)

Solving 4-Block Integer Linear Programs Faster Using Affine Decompositions of the Right-Hand Sides
by: Lassota, Alexandra, et al.
Published: (2026)

On the Complexity of Identification in Linear Structural Causal Models
by: Dörfler, Julian, et al.
Published: (2024)

On the Complexity of p-Order Cone Programs
by: Blanco, Víctor, et al.
Published: (2025)

The Randomized Query Complexity of Finding a Tarski Fixed Point on the Boolean Hypercube
by: Brânzei, Simina, et al.
Published: (2024)

The Complexity of Computing KKT Solutions of Quadratic Programs
by: Fearnley, John, et al.
Published: (2023)

One-Way Functions and Polynomial Time Dimension
by: Nandakumar, Satyadev, et al.
Published: (2024)

Canonization of a random graph by two matrix-vector multiplications
by: Verbitsky, Oleg, et al.
Published: (2023)

Canonization of a random circulant graph by counting walks
by: Verbitsky, Oleg, et al.
Published: (2023)

Counting Triangulations of Fixed Cardinal Degrees
by: Chambers, Erin, et al.
Published: (2025)

Fixed-parameter tractability of canonical polyadic decomposition over finite fields
by: Yang, Jason
Published: (2024)

Counting Martingales for Measure and Dimension in Complexity Classes
by: Hitchcock, John M., et al.
Published: (2025)

A Note on Fine-Grained Quantum Reductions for Linear Algebraic Problems
by: Doney, Kyle, et al.
Published: (2025)

A Brief Note on a Recent Claim About NP-Hard Problems and BQP
by: Chavrimootoo, Michael C.
Published: (2024)

New Limits on Distributed Quantum Advantage: Dequantizing Linear Programs
by: Balliu, Alkida, et al.
Published: (2025)

Pushing Blocks without Fixed Walls via Checkable Gizmos: Push-1 is PSPACE-Complete
by: MIT Hardness Group, et al.
Published: (2025)

$\#$W[1] = $\text{FPT}$: Fixed-Parameter Tractable Exact Algorithms for the $\#k$-Matching Problem
by: Yi, Yongming
Published: (2026)

Fine-Grained Equivalence for Problems Related to Integer Linear Programming
by: Rohwedder, Lars, et al.
Published: (2024)

A Cautionary Note on Quantum Oracles
by: Agarwal, Avantika, et al.
Published: (2025)

A Hierarchy for Constant Communication Complexity
by: Ambainis, Andris, et al.
Published: (2025)

Computational Complexity of UAP Reverse Engineering: A Formal Analysis of Automaton Identification and Data Complexity
by: Daghbouche, Karim
Published: (2025)

Structure in Communication Complexity and Constant-Cost Complexity Classes
by: Hatami, Hamed, et al.
Published: (2024)

An Overview of the Theory of Instances Computational Complexity
by: Jorge A. Ruiz-Vanoye
Published: (2011)

Fixed Parameter Tractable Linearizability Monitoring
by: Han, Lee Zheng, et al.
Published: (2025)