Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Product Line Design with Pricing Kits Read chapter Read first chapter

2014 | OriginalPaper | Chapter

Approximating Combinatorial Optimization Problems with Uncertain Costs and the OWA Criterion

Authors : Adam Kasperski, Paweł Zieliński

Published in: Operations Research Proceedings 2012

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

In this paper a class combinatorial optimization problems with uncertain costs is discussed. This uncertainty is modeled by specifying a scenario set containing K distinct cost vectors. In order to choose a solution the Ordered Weighted Averaging aggregation operator (OWA) is used. For most classical problems, for example network problems, minimizing OWA is NP-hard even for two scenarios. In this paper some positive and negative approximation results for the problem are shown.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter How Does Network Topology Determine the Synchronization Threshold in a Network of Oscillators?
next chapter Recoverable Robust Combinatorial Optimization Problems
Literature
1.
Aissi, H., Bazgan, C., Vanderpooten, D.: General approximation schemes for minmax (regret) versions of some (pseudo-)polynomial problems. Discrete Optim. 7, 136–148 (2010)CrossRef
2.
Averbakh, I.: On the complexity of a class of combinatorial optimization problems with uncertainty. Math Program. 90, 263–272 (2001)CrossRef
3.
Kasperski, A., Zieliński, P.: On the approximability of minmax (regret) network optimization problems. Inf. Process. Lett. 109, 262–266 (2009)CrossRef
4.
Kasperski, A., Zieliński, P.: A randomized algorithm for the min-max selecting items problem with uncertain weights. Ann. Oper. Res. 172, 221–230 (2009)CrossRef
5.
Kohli, R., Krishnamurti, R., Mirchandani, P.: The minimum satisfiability problem. SIAM J. Discrete Math. 7, 275–283 (1994)CrossRef
6.
Kouvelis, P., Yu, G.: Robust Discrete Optimization and its applications. Kluwer Academic Publishers, Dordrecht (1997)
7.
Mittal, S., Schulz, A.S.: A general framework for designing approximation schemes for combinatorial optimization problems with many objectives combined into one. In: APPROX-RANDOM 2008, Lecture Notes in Computer Science, vol. 5171, pp. 179–192. Springer-Verlag (2008)
8.
Papadimitriou, C.H., Yannakakis, M.: On the Approximability of Trade-offs and Optimal Access of Web Sources. In: FOCS 2000, pp. 86–92 (2000)
9.
Yager, R.R.: On Ordered Weighted Averaging Aggregation Operators in Multi-Criteria Decision Making. IEEE Trans. Syst. Man Cybern. 18, 183–190 (1988)CrossRef
Metadata
Title
Approximating Combinatorial Optimization Problems with Uncertain Costs and the OWA Criterion
Authors
Adam Kasperski
Paweł Zieliński
Copyright Year
2014
Book
Operations Research Proceedings 2012

Print ISBN: 978-3-319-00794-6

Electronic ISBN: 978-3-319-00795-3

Copyright Year: 2014

DOI
https://doi.org/10.1007/978-3-319-00795-3_21

Premium Partner

    Image Credits