Kijima, Masaaki; Tamura, Akihisa 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 Keywords:matroid; stochastic spanning tree; greedy algorithm; stochastic orders PDFBibTeX XMLCite \textit{M. Kijima} and \textit{A. Tamura}, in: Stochastic modelling in innovative manufacturing. Selected papers of the UK-Japanese workshop, Cambridge, UK, July 20--21, 1995. Berlin: Springer. 19--29 (1997; Zbl 0878.90081)