Cover Image

Linear Equations with Min and Max Operators: Computational Complexity

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Chatterjee, Krishnendu, Luo, Ruichen, Saona, Raimundo, Svoboda, Jakub
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity Artificial Intelligence Optimization and Control
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Value Iteration with Guessing for Markov Chains and Markov Decision Processes
by: Chatterjee, Krishnendu, et al.
Published: (2025)

Revealing POMDPs: Qualitative and Quantitative Analysis for Parity Objectives
by: Asadi, Ali, et al.
Published: (2025)

Uniform Value and Decidability in Ergodic Blind Stochastic Games
by: Chatterjee, Krishnendu, et al.
Published: (2024)

Second-Order Min-Max Optimization with Lazy Hessians
by: Chen, Lesi, et al.
Published: (2024)

Approximating the Uniform Value in Hidden Stochastic Games with Doeblin Conditions
by: Chatterjee, Krishnendu, et al.
Published: (2026)

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

Limit-sure reachability for small memory policies in POMDPs is NP-complete
by: Asadi, Ali, et al.
Published: (2024)

Tight Time Complexities in Parallel Stochastic Optimization with Arbitrary Computation Dynamics
by: Tyurin, Alexander
Published: (2024)

Unified Projection-Free Algorithms for Adversarial DR-Submodular Optimization
by: Pedramfar, Mohammad, et al.
Published: (2024)

Stronger Approximation Guarantees for Non-Monotone γ-Weakly DR-Submodular Maximization
by: Jadav, Hareshkumar, et al.
Published: (2026)

A direct optimization algorithm for input-constrained MPC
by: Wu, Liang, et al.
Published: (2023)

Min-Max Optimization Requires Exponentially Many Queries
by: Bernasconi, Martino, et al.
Published: (2026)

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

The Complexity of Recognizing Facets for the Knapsack Polytope
by: Chen, Rui, et al.
Published: (2022)

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

On the Computational Complexity of Multi-Objective Ordinal Unconstrained Combinatorial Optimization
by: Figueira, José Rui, et al.
Published: (2024)

The Computational Complexity of Finding Stationary Points in Non-Convex Optimization
by: Hollender, Alexandros, et al.
Published: (2023)

Benchmarking of Quantum and Classical Computing in Large-Scale Dynamic Portfolio Optimization Under Market Frictions
by: Chen, Ying, et al.
Published: (2025)

Benign landscape for Burer-Monteiro factorizations of MaxCut-type semidefinite programs
by: Endor, Faniriana Rakoto, et al.
Published: (2024)

The Complexity of Finding Local Optima in Contrastive Learning
by: Yan, Jingming, et al.
Published: (2025)

Strongly Polynomial Time Complexity of Policy Iteration for $L_\infty$ Robust MDPs
by: Asadi, Ali, et al.
Published: (2026)

Monotone Near-Zero-Sum Games: A Generalization of Convex-Concave Minimax
by: Luo, Ruichen, et al.
Published: (2025)

Optimal Sensor and Actuator Selection for Factored Markov Decision Processes: Complexity, Approximability and Algorithms
by: Bhargav, Jayanth, et al.
Published: (2024)

Concurrent Stochastic Games with Stateful-discounted and Parity Objectives: Complexity and Algorithms
by: Asadi, Ali, et al.
Published: (2024)

Properties of Fixed Points of Generalised Extra Gradient Methods Applied to Min-Max Problems
by: Farzin, Amir Ali, et al.
Published: (2025)

Intrinsic Sequentiality in P: Causal Limits of Parallel Computation
by: Wei, Jing-Yuan
Published: (2026)

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

Avoiding Deadlocks via Weak Deadlock Sets
by: Oriolo, Gianpaolo, et al.
Published: (2024)

A System-Dynamic Based Simulation and Bayesian Optimization for Inventory Management
by: Maitra, Sarit
Published: (2024)

Learning complexity of gradient descent and conjugate gradient algorithms
by: Jiao, Xianqi, et al.
Published: (2024)

Geometric and computational hardness of bilevel programming
by: Bolte, Jérôme, et al.
Published: (2024)

Reduction from the partition problem: Dynamic lot sizing problem with polynomial complexity
by: Sim, Chee-Khian
Published: (2024)

A parallel framework for graphical optimal transport
by: Fan, Jiaojiao, et al.
Published: (2024)

Hardness of some optimization problems over correlation polyhedra
by: Caprara, Alberto, et al.
Published: (2026)

On the Induced Norms of Matrices and Grothendieck problems
by: Truong, Lan V., et al.
Published: (2026)

Efficient LP warmstarting for linear modifications of the constraint matrix
by: Derval, Guillaume, et al.
Published: (2025)

Constrained Nonnegative Gram Feasibility is $\exists\mathbb{R}$-Complete
by: Majumdar, Angshul
Published: (2026)

On the Degree Automatability of Sum-of-Squares Proofs
by: Bortolotti, Alex, et al.
Published: (2025)

Parameterized complexity of scheduling unit-time jobs with generalized precedence constraints
by: Büsing, Christina, et al.
Published: (2025)

Counterfactual Explanations for Integer Optimization Problems
by: Engelhardt, Felix, et al.
Published: (2025)