Linear Programming with Inexact Data is NP‐Hard

DOI10.1002/ZAMM.19980781594zbMATH Open0915.90204OpenAlexW2004388087MaRDI QIDQ4228409FDOQ4228409

Authors: 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)

Cites Work

• Checking robust nonsingularity is NP-hard
• Title not available (Why is that?)
• Compatibility of approximate solution of linear equations with given error bounds for coefficients and right-hand sides
• Strong solvability of interval linear programming problems

Cited In (9)

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

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

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