An approach to estimating the average-case complexity of postoptimality analysis of discrete optimization problems

DOI10.1007/s10559-011-9366-7zbMath1358.68144OpenAlexW2025873233MaRDI QIDQ464980

Victor A. Mikhailyuk

Publication date: 30 October 2014

Published in: Cybernetics and Systems Analysis (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10559-011-9366-7

zbMATH Keywords

polynomiality on average with respect to \(\mu\)postoptimality analysis

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• On estimates of the complexity of numerical characteristics of postoptimality analysis for discrete optimization problems
• Average case completeness
• On the theory of average case complexity
• General approach to estimating the complexity of postoptimality analysis for discrete optimization problems
• Stability, parametric, and postoptimality analysis of discrete optimization problems
• Average Case Complete Problems
• Exceptional Paper—Parametric and Postoptimality Analysis in Integer Linear Programming
• Postoptimality analysis in zero‐one programming by implicit enumeration
• Unnamed Item