Probabilistic analysis of the greedy algorithm.

News

02 August, 2019 OS DAY-2019. Cooperation among operating platform developers and the security of Russian software

10 April, 2019 Ivannikov Memorial Workshop has been supported by IEEE

14 March, 2019 The annual Ivannikov Memorial Workshop will take place on 13-14 September 2019

Probabilistic analysis of the greedy algorithm.

N.N. Kuzjurin.

Abstract

It is shown that the greedy algorithm in the average case (in some probabilistic model) finds almost minimum covers. It is shown also that in the average case the ratio of the size of minimum cover to the size of minimum fractional cover has logarithmic order in the size of the ground set.

Edition

Proceedings of the Institute for System Programming, vol. 6 (in Russian), 2004, Стр. 101-108.

ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

For citation

N.N. Kuzjurin. Probabilistic analysis of the greedy algorithm. . Proceedings of the Institute for System Programming, vol. 6 (in Russian), 2004, Стр. 101-108. .

Full text of the paper in pdf (in Russian)

Back to the contents of the volume