Combinatorial optimization tolerances calculated in linear time

Boris Goldengorin and Gerard Sierksma
Additional contact information
Gerard Sierksma: Groningen University

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

Abstract: For a given optimal solution to a combinatorial optimization problem, we show, under very natural conditions, the equality of the minimal values of upper and lower tolerances, where the upper tolerances are calculated for the given optimal solution and the lower tolerances outside the optimal solution. As a consequence, the calculation of such tolerances can now be done in linear time, while all current methods use quadratic time.

Date: 2003
References: View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://irs.ub.rug.nl/ppn/252306341 (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:03a30

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 (h.g.tamling@rug.nl).