Linear Programming with Inexact Data is NP‐Hard

DOI10.1002/zamm.19980781594zbMath0915.90204OpenAlexW2004388087MaRDI QIDQ4228409

Jiří Rohn

Publication date: 2 February 1999

Published in: ZAMM - Journal of Applied Mathematics and Mechanics / Zeitschrift für Angewandte Mathematik und Mechanik (Search for Journal in Brave)

Full work available at URL: http://www.nusl.cz/ntk/nusl-33636

zbMATH Keywords

NP-hardinexact data

Mathematics Subject Classification ID

Linear programming (90C05)

Related Items (9)

Farkas-type conditions of general interval linear systems for AE solvability ⋮ Weak and strong solvability of interval linear systems of equations and inequalities ⋮ Optimal value bounds in interval fractional linear programming and revenue efficiency measuring ⋮ A Farkas-type theorem for interval linear inequalities ⋮ Letter to the editor ⋮ Complexity of necessary efficiency in interval linear programming and multiobjective linear programming ⋮ Interval systems of max-separable linear equations ⋮ Farkas-type theorems for interval linear systems ⋮ Checking solvability of systems of interval linear equations and inequalities via mixed integer programming

Cites Work

• Strong solvability of interval linear programming problems
• Checking robust nonsingularity is NP-hard
• Compatibility of approximate solution of linear equations with given error bounds for coefficients and right-hand sides
• Unnamed Item

This page was built for publication: Linear Programming with Inexact Data is NP‐Hard