EconPapers    
Economics at your fingertips  
 

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 ().

 
Page updated 2024-11-07
Handle: RePEc:gro:rugsom:00a22