A computational study of approximation algorithms for a minmax resource allocation problem

Bogusz Przybysławski () and Adam Kasperski

Operations Research and Decisions, 2012, vol. 22, issue 2, 35-43

Abstract: A basic resource allocation problem with uncertain costs has been discussed. The problem is to minimize the total cost of choosing exactly p items out of n available. The uncertain item costs are specified as a discrete scenario set and the minmax criterion is used to choose a solution. This problem is known to be NP-hard, but several approximation algorithms exist. The aim of this paper is to investigate the quality of the solutions returned by these approximation algorithms. According to the results obtained, the randomized algorithms described are fast and output solutions of good quality, even if the problem size is large.

Keywords: discrete optimization; robust optimization; resource allocation; approximation algorithms (search for similar items in EconPapers)
Date: 2012
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://ord.pwr.edu.pl/assets/papers_archive/1022%20-%20published.pdf (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:wut:journl:v:2:y:2012:p:35-43:id:1022

DOI: 10.5277/ord120203

Access Statistics for this article

More articles in Operations Research and Decisions from Wroclaw University of Science and Technology, Faculty of Management Contact information at EDIRC.
Bibliographic data for series maintained by Adam Kasperski ().