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

DOI10.1007/S10559-011-9366-7MaRDI QIDQ464980zbMATH OpenOpenAlexFDO

Authors 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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• General approach to estimating the complexity of postoptimality analysis for discrete optimization problems
• An approach to estimating the complexity of probabilistic procedures for the postoptimality analysis of discrete optimization problems
• On estimates of the complexity of numerical characteristics of postoptimality analysis for discrete optimization problems
• On the complexity of postoptimality analysis of \(0/1\) programs
• scientific article; zbMATH DE number 808811

Cites work

• scientific article; zbMATH DE number 3187993 (Why is no real title available?)
• Average Case Complete Problems
• Average case completeness
• Exceptional Paper—Parametric and Postoptimality Analysis in Integer Linear Programming
• General approach to estimating the complexity of postoptimality analysis for discrete optimization problems
• On estimates of the complexity of numerical characteristics of postoptimality analysis for discrete optimization problems
• On the theory of average case complexity
• Postoptimality analysis in zero‐one programming by implicit enumeration
• Stability, parametric, and postoptimality analysis of discrete optimization problems

Cited in

(5)

• On estimates of the complexity of numerical characteristics of postoptimality analysis for discrete optimization problems
• Analysis-aware defeaturing: Problem setting and a posteriori estimation
• On the complexity of postoptimality analysis of \(0/1\) programs
• An approach to estimating the complexity of probabilistic procedures for the postoptimality analysis of discrete optimization problems
• General approach to estimating the complexity of postoptimality analysis for discrete optimization problems

This page was built for publication: An approach to estimating the average-case complexity of postoptimality analysis of discrete optimization problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q464980)