Computational Complexity of Some Problems in Parametric Discrete Programming. I

DOI10.1287/MOOR.11.2.241MaRDI QIDQ3793961zbMATH OpenOpenAlexFDO

Authors C. E. Blair, Robert G. Jeroslow

Publication date 1986

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1287/moor.11.2.241

zbMATH Keywords

computational complexityNP-completeNP-hardnesspolynomial-time decidableChvátal functionparametric linear and integer linear programming

Mathematics Subject Classification ID

Linear programming (90C05) Analysis of algorithms and problem complexity (68Q25) Sensitivity, stability, parametric optimization (90C31) Integer programming (90C10)

Recommendations

• Complexity of some parametric integer and network programming problems
• Parametric integer programming
• Parametric integer programming in fixed dimension
• scientific article; zbMATH DE number 1263257
• Linear programming with variable matrix entries

Cited in

(10)

• Complexity of some parametric integer and network programming problems
• A primal dual integer programming algorithm
• On the relative complexity of 15 problems related to~0/1-integer programming
• Parametric integer programming
• Linear programming with variable matrix entries
• Parameterisation algorithms for the integer linear programs in binary variables
• Parametric integer programming in fixed dimension
• Parametric simplex algorithms for a class of NP-complete problems whose average number of steps is polynomial
• On the complexity of a special basis problem in LP
• scientific article; zbMATH DE number 5799870 (Why is no real title available?)

This page was built for publication: Computational Complexity of Some Problems in Parametric Discrete Programming. I

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