Probabilistic analysis of the greedy algorithm.

Probabilistic analysis of the greedy algorithm.

N.N. Kuzjurin.

Аннотация

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.

Издание

Труды Института системного программирования РАН, том 6, 2004, стр. 101-108.

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

Для цитирования

N.N. Kuzjurin. Probabilistic analysis of the greedy algorithm. . Труды Института системного программирования РАН, том 6, 2004, стр. 101-108. .

Полный текст статьи в формате pdf Вернуться к содержанию тома