On the complexity of determining tolerances for ->e--optimal solutions to min-max combinatorial optimization problems

Diptesh Ghosh () and G. Sierksma
Additional contact information
G. Sierksma: Groningen University

No 00A35, Research Report from University of Groningen, Research Institute SOM (Systems, Organisations and Management)

Abstract: Sensitivity analysis of e-optimal solutions is the problem of calculating the range within which a problem parameter may lie so that the given solution re-mains e-optimal. In this paper we study the sensitivity analysis problem for e-optimal solutions tocombinatorial optimization problems with min-max ob-jectives where e > 0. We show that the problem is easy if the original problem is easy. We also show that the converse is true under the assumption that it is possible to calculate an e-optimal solution to the problem in polynomial time.

Date: 2000
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://irs.ub.rug.nl/ppn/240570340 (application/pdf)
Our link check indicates that this URL is bad, the error code is: 403 Forbidden (http://irs.ub.rug.nl/ppn/240570340 [302 Found]--> https://irs.ub.rug.nl/ppn/240570340 [302 Found]--> https://www.rug.nl/research/portal/publications/pub(ffc140bc-5c73-4110-a7aa-b1eaa49742a1).html [301 Moved Permanently]--> https://research.rug.nl/en/publications/pub(ffc140bc-5c73-4110-a7aa-b1eaa49742a1).html [301 Moved Permanently]--> https://research.rug.nl/en/publications/on-the-complexity-of-determining-tolerances-for-gte-optimal-solut)

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:gro:rugsom:00a35

Access Statistics for this paper

More papers in Research Report from University of Groningen, Research Institute SOM (Systems, Organisations and Management) Contact information at EDIRC.
Bibliographic data for series maintained by Hanneke Tamling ().