EconPapers    
Economics at your fingertips  
 

Approximating Combinatorial Optimization Problems with Uncertain Costs and the OWA Criterion

Adam Kasperski and Paweł Zieliński ()
Additional contact information
Paweł Zieliński: Wrocław University of Technology

A chapter in Operations Research Proceedings 2012, 2014, pp 141-146 from Springer

Abstract: 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.

Keywords: Uncertain Costs; Class Combinatorial Optimization Problems; Cost Vector; Network Problems; Fully Polynomial Time Approximation Scheme (FPTAS) (search for similar items in EconPapers)
Date: 2014
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:spr:oprchp:978-3-319-00795-3_21

Ordering information: This item can be ordered from
http://www.springer.com/9783319007953

DOI: 10.1007/978-3-319-00795-3_21

Access Statistics for this chapter

More chapters in Operations Research Proceedings from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().

 
Page updated 2025-04-01
Handle: RePEc:spr:oprchp:978-3-319-00795-3_21