Complexity of determining exact tolerances for min-max combinatorial optimization problems
R. Ramaswamy,
N. Chakravarti and
Diptesh Ghosh ()
No 00A22, Research Report from University of Groningen, Research Institute SOM (Systems, Organisations and Management)
Abstract:
Suppose that we are given an instance of a combinatorial optimization problemwith min-max objective along with an optimal solution for it. Let the cost of asingle element be varied. We refer to the range of values of the element’s costfor which the given optimal solution remains optimal as its exact tolerance. Inthis paper we examine the problem of determining the exact tolerance of eachelement in combinatorial optimization problems with min-max objectives. Weshow that under very weak assumptions, the exact tolerance of each elementcan be determined in polynomial time if and only if the original optimizationproblem can be solved in polynomial time.
Date: 2000
References: View references in EconPapers View complete reference list from CitEc
Citations:
Downloads: (external link)
http://irs.ub.rug.nl/ppn/24056653X (application/pdf)
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:00a22
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 ().