Complexity of necessary efficiency in interval linear programming and multiobjective linear programming

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F12%3A10125736" target="_blank" >RIV/00216208:11320/12:10125736 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1007/s11590-011-0315-1" target="_blank" >http://dx.doi.org/10.1007/s11590-011-0315-1</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/s11590-011-0315-1" target="_blank" >10.1007/s11590-011-0315-1</a>

Result language
angličtina
Original language name
Complexity of necessary efficiency in interval linear programming and multiobjective linear programming
Original language description
We present some complexity results on checking necessary efficiency in interval multiobjective linear programming. Supposing that objective function coefficients perturb within prescribed intervals, a feasible point x* is called necessarily efficient ifit is efficient for all instances of interval data. We show that the problem of checking necessary efficiency is co-NP-complete even for the case of only one objective. Provided that x* is a non-degenerate basic solution, the problem is polynomially solvable for one objective, but remains co-NP-hard in the general case. Some open problems are mentioned at the end of the paper.
Czech name
—
Czech description
—

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BD - Information theory
OECD FORD branch
—

Project
—
Continuities
Z - Vyzkumny zamer (s odkazem do CEZ)<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year
2012
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)