On the complexity of calculating sensitivity parameters in Boolean programming problems

DOI10.1007/S10559-015-9763-4zbMATH Open1330.90054OpenAlexW2183497763MaRDI QIDQ904419FDOQ904419

Authors: N. V. Lishchuk, Victor A. Mikhailyuk 

Publication date: 13 January 2016

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

Full work available at URL: https://doi.org/10.1007/s10559-015-9763-4

Recommendations

• The stability of the approximate Boolean minimization of a linear form
• Calculation of stability radii for combinatorial optimization problems
• scientific article; zbMATH DE number 781252
• Publication:3479821
• Some Complexity Issues In A Class Of Knapsack Problems: What Makes A Knapsack Problem “Hard”?

zbMATH Keywords

complexity of sensitivity analysisstability ball of radius \(r\) for an \(\epsilon\)-approximate problem solutionstability radius of a problem

Mathematics Subject Classification ID

Sensitivity, stability, parametric optimization (90C31) Boolean programming (90C09)

Cites Work

• A Greedy Heuristic for the Set-Covering Problem
• General approach to estimating the complexity of postoptimality analysis for discrete optimization problems
• Reoptimization of max \(k\)-cover: approximation ratio threshold
• On the complexity of postoptimality analysis of \(0/1\) programs
• Sensitivity analysis for knapsack problems: Another negative result
• Sensitivity analysis for knapsack problems: A negative result
• Sensitivity analysis of the knapsack problem: a negative result
• Calculation of stability radii for combinatorial optimization problems
• The stability of the approximate Boolean minimization of a linear form
• Stability of solutions in problems of Boolean linear programming
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (3)

• Sensitivity analysis of efficient solution in vector MINMAX Boolean programming problem
• Title not available (Why is that?)
• Remarks on ‘equivalence of stability concepts for discrete time-varying systems’

This page was built for publication: On the complexity of calculating sensitivity parameters in Boolean programming problems

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