Robust Combinatorial Optimization under Decision Dependent Interval Uncertainty

Hande Yaman Paternotte and Ali Irfan Mahmutogullari

No 664956, Working Papers of Department of Decision Sciences and Information Management, Leuven from KU Leuven, Faculty of Economics and Business (FEB), Department of Decision Sciences and Information Management, Leuven

Abstract: We consider robust combinatorial optimization problems with interval uncertainty where the decision maker is allowed to alter the uncertainty of some objective function coefficients. We present complexity results for the absolute robust and the robust deviation counterparts of two well-known combinatorial optimization problems: maximization over a uniform matroid and the shortest path problem. We prove that both problems can be solved in polynomial time under absolute robustness. With the robust deviation criterion, the shortest path problem becomes NP-hard where maximization over a uniform matroid remains polynomially solvable.

Date: 2020
References: Add references at CitEc
Citations:

Downloads: (external link)
https://lirias.kuleuven.be/retrieve/597627 Submitted version (application/pdf)
KU Leuven intranet only, request a copy at https://lirias.kuleuven.be/handle/123456789/664956

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ete:kbiper:664956

Access Statistics for this paper

More papers in Working Papers of Department of Decision Sciences and Information Management, Leuven from KU Leuven, Faculty of Economics and Business (FEB), Department of Decision Sciences and Information Management, Leuven
Bibliographic data for series maintained by library EBIB ().