A Probabilistic Feasibility and Value Analysis of the Generalized Assignment Problem

H. Edwin Romeijn () and Nanda Piersma ()
Additional contact information
H. Edwin Romeijn: University of Florida
Nanda Piersma: Erasmus University Rotterdam

Journal of Combinatorial Optimization, 2000, vol. 4, issue 3, No 3, 325-355

Abstract: Abstract We study the generalized assignment problem, under a probabilistic model for its cost and requirement parameters. First we address the issue of feasibility by deriving a tight condition on the probabilistic model that ensures that the corresponding problem instances are feasible with probability one as the number of jobs goes to infinity. Then, under an additional condition on the parameters, we show that the optimal solution value, normalized by dividing by the number of jobs, converges with probability one to a constant, again as the number of jobs goes to infinity. Finally, we discuss various examples.

Keywords: generalized assignment problem; probabilistic model; empirical processes (search for similar items in EconPapers)
Date: 2000
References: Add references at CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1023/A:1009874227903 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:jcomop:v:4:y:2000:i:3:d:10.1023_a:1009874227903

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1023/A:1009874227903

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().