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.
Download Info
To download:
If you experience problems downloading a file, check if you have the
proper application to
view it first. Information about this may be contained
in the File-Format links below. In case of further problems read
the IDEAS help
page. Note that these files are not on the IDEAS
site. Please be patient as the files may be large.
Publisher Info
Paper provided by University of Groningen, Research Institute SOM (Systems, Organisations and Management) in its series Research Report with number
00A22.