umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Extending Single Tolerances to Set Tolerances
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
2018 (English)In: Discrete Applied Mathematics, ISSN 0166-218X, E-ISSN 1872-6771, Vol. 247, p. 197-215Article in journal (Refereed) Published
Abstract [en]

The theory of single upper and lower tolerances for combinatorial minimization problems was formalized in 2005 for the three types of cost functions sum, product, and maximum, and since then it has shown to be rather useful in creating heuristics and exact algorithms. However, such single tolerances are often used because the assessment of multiple cost changes is considered too complicated. This paper addresses that issue. In this paper we extend this theory from single to set tolerances for these three types of cost functions. In particular, we characterize specific values of set upper and lower tolerances as positive and infinite, and we show a criterion for the uniqueness of an optimal solution to a combinatorial minimization problem. Furthermore, we present one exact formula and several bounds for computing set upper and lower tolerances using the relation to their corresponding single tolerance counterparts. 

Place, publisher, year, edition, pages
Elsevier, 2018. Vol. 247, p. 197-215
Keywords [en]
Sensitivity analysis, Combinatorial optimization, Single tolerance, Set tolerance
National Category
Mathematics
Research subject
Mathematics
Identifiers
URN: urn:nbn:se:umu:diva-145877DOI: 10.1016/j.dam.2018.03.053ISI: 000444362700022OAI: oai:DiVA.org:umu-145877DiVA, id: diva2:1191768
Funder
The Kempe Foundations, SMK-1354Available from: 2018-03-20 Created: 2018-03-20 Last updated: 2018-10-04Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Authority records BETA

Jäger, Gerold

Search in DiVA

By author/editor
Jäger, Gerold
By organisation
Department of Mathematics and Mathematical Statistics
In the same journal
Discrete Applied Mathematics
Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 78 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf