×

On the greedy algorithm for stochastic optimization problems. (English) Zbl 0878.90081

Christer, Anthony H. (ed.) et al., Stochastic modelling in innovative manufacturing. Selected papers of the UK-Japanese workshop, Cambridge, UK, July 20–21, 1995. Berlin: Springer. Lect. Notes Eng. 445, 19-29 (1997).
Summary: It is well known that the greedy algorithm minimizes \(\sum_{i\in A}C_i\) subject to \(A\in{\mathcal B}\) where \({\mathcal B}\) is the set of bases of a matroid and \(C_i\) is the deterministic cost assigned to element \(i\). In this paper, we consider the case that \(C_i\) are random costs which are ordered with respect to some stochastic ordering relation. We will show that the optimality of the greedy algorithm holds for a broad class of stochastic orders.
For the entire collection see [Zbl 0855.00025].

MSC:

90C15 Stochastic programming
90C35 Programming involving graphs or networks
PDFBibTeX XMLCite