Buchumschlag

On a class of interdiction problems with partition matroids: complexity and polynomial-time algorithms

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Ketkov, Sergey S., Prokopyev, Oleg A.
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Computational Complexity Optimization and Control
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

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

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

A Note on the Complexity of Bilevel Linear Programs in Fixed Dimensions
von: Ketkov, Sergey S., et al.
Veröffentlicht: (2025)

Reduction from the partition problem: Dynamic lot sizing problem with polynomial complexity
von: Sim, Chee-Khian
Veröffentlicht: (2024)

On the completeness of several fortification-interdiction games in the Polynomial Hierarchy
von: Tomasaz, Alberto Boggio, et al.
Veröffentlicht: (2024)

Learning complexity of gradient descent and conjugate gradient algorithms
von: Jiao, Xianqi, et al.
Veröffentlicht: (2024)

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

On the Induced Norms of Matrices and Grothendieck problems
von: Truong, Lan V., et al.
Veröffentlicht: (2026)

Hardness of some optimization problems over correlation polyhedra
von: Caprara, Alberto, et al.
Veröffentlicht: (2026)

A note on the complexity of the picker routing problem in multi-block warehouses and related problems
von: Prunet, Thibault, et al.
Veröffentlicht: (2023)

A study of distributionally robust mixed-integer programming with Wasserstein metric: on the value of incomplete data
von: Ketkov, Sergey S.
Veröffentlicht: (2023)

Avoiding Deadlocks via Weak Deadlock Sets
von: Oriolo, Gianpaolo, et al.
Veröffentlicht: (2024)

A System-Dynamic Based Simulation and Bayesian Optimization for Inventory Management
von: Maitra, Sarit
Veröffentlicht: (2024)

Geometric and computational hardness of bilevel programming
von: Bolte, Jérôme, et al.
Veröffentlicht: (2024)

Tight Time Complexities in Parallel Stochastic Optimization with Arbitrary Computation Dynamics
von: Tyurin, Alexander
Veröffentlicht: (2024)

A parallel framework for graphical optimal transport
von: Fan, Jiaojiao, et al.
Veröffentlicht: (2024)

On the Complexity of p-Order Cone Programs
von: Blanco, Víctor, et al.
Veröffentlicht: (2025)

Efficient LP warmstarting for linear modifications of the constraint matrix
von: Derval, Guillaume, et al.
Veröffentlicht: (2025)

Constrained Nonnegative Gram Feasibility is $\exists\mathbb{R}$-Complete
von: Majumdar, Angshul
Veröffentlicht: (2026)

On the Degree Automatability of Sum-of-Squares Proofs
von: Bortolotti, Alex, et al.
Veröffentlicht: (2025)

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

Counterfactual Explanations for Integer Optimization Problems
von: Engelhardt, Felix, et al.
Veröffentlicht: (2025)

Policy Gradient Algorithms in Average-Reward Multichain MDPs
von: Lee, Jongmin, et al.
Veröffentlicht: (2026)

A parameterized linear formulation of the integer hull
von: Eisenbrand, Friedrich, et al.
Veröffentlicht: (2025)

The Complexity of Computing KKT Solutions of Quadratic Programs
von: Fearnley, John, et al.
Veröffentlicht: (2023)

Iterative Optimization of Multidimensional Functions on Turing Machines under Performance Guarantees
von: Boche, Holger, et al.
Veröffentlicht: (2025)

The Complexity of Recognizing Facets for the Knapsack Polytope
von: Chen, Rui, et al.
Veröffentlicht: (2022)

Information Redistribution Under Reductions in NP Search
von: Wei, Jing-Yuan
Veröffentlicht: (2026)

Centrality of shortest paths: Algorithms and complexity results
von: Phosavanh, Johnson, et al.
Veröffentlicht: (2024)

Turing in the shadows of Nobel and Abel: an algorithmic story behind two recent prizes
von: Gamarnik, David
Veröffentlicht: (2025)

Optimal Sensor and Actuator Selection for Factored Markov Decision Processes: Complexity, Approximability and Algorithms
von: Bhargav, Jayanth, et al.
Veröffentlicht: (2024)

Query-Efficient Zeroth-Order Algorithms for Nonconvex Constrained Optimization
von: Jin, Ruiyang, et al.
Veröffentlicht: (2025)

A direct optimization algorithm for input-constrained MPC
von: Wu, Liang, et al.
Veröffentlicht: (2023)

Real Stability and Log Concavity are coNP-Hard
von: Chin, Tracy
Veröffentlicht: (2024)

Two Choices are Enough for P-LCPs, USOs, and Colorful Tangents
von: Borzechowski, Michaela, et al.
Veröffentlicht: (2024)

Solving The Travelling Salesman Problem Using A Single Qubit
von: Goswami, Kapil, et al.
Veröffentlicht: (2024)

Linear Equations with Min and Max Operators: Computational Complexity
von: Chatterjee, Krishnendu, et al.
Veröffentlicht: (2024)

From Linear to Linearizable Optimization: A Novel Framework with Applications to Stationary and Non-stationary DR-submodular Optimization
von: Pedramfar, Mohammad, et al.
Veröffentlicht: (2024)

Benign landscape for Burer-Monteiro factorizations of MaxCut-type semidefinite programs
von: Endor, Faniriana Rakoto, et al.
Veröffentlicht: (2024)

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