Probabilistic analysis of the greedy algorithm.
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.
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Ivannikov Institute for System Programming of the Russian Academy of Sciences
2004-01-01
|
| Series: | Труды Института системного программирования РАН |
| Online Access: | https://www.ispras.ru/en/proceedings/isp_6_2004/isp_6_2004_101/ |
| _version_ | 1818665281465090048 |
|---|---|
| author | N.N. Kuzjurin |
| author_facet | N.N. Kuzjurin |
| author_sort | N.N. Kuzjurin |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-12-17T05:46:09Z |
| format | Article |
| id | doaj.art-07134486a0134ae39a23874d74371566 |
| institution | Directory Open Access Journal |
| issn | 2079-8156 2220-6426 |
| language | English |
| last_indexed | 2024-12-17T05:46:09Z |
| publishDate | 2004-01-01 |
| publisher | Ivannikov Institute for System Programming of the Russian Academy of Sciences |
| record_format | Article |
| series | Труды Института системного программирования РАН |
| spelling | doaj.art-07134486a0134ae39a23874d743715662022-12-21T22:01:18ZengIvannikov Institute for System Programming of the Russian Academy of SciencesТруды Института системного программирования РАН2079-81562220-64262004-01-016101108Probabilistic analysis of the greedy algorithm.N.N. KuzjurinIt 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.https://www.ispras.ru/en/proceedings/isp_6_2004/isp_6_2004_101/ |
| spellingShingle | N.N. Kuzjurin Probabilistic analysis of the greedy algorithm. Труды Института системного программирования РАН |
| title | Probabilistic analysis of the greedy algorithm. |
| title_full | Probabilistic analysis of the greedy algorithm. |
| title_fullStr | Probabilistic analysis of the greedy algorithm. |
| title_full_unstemmed | Probabilistic analysis of the greedy algorithm. |
| title_short | Probabilistic analysis of the greedy algorithm. |
| title_sort | probabilistic analysis of the greedy algorithm |
| url | https://www.ispras.ru/en/proceedings/isp_6_2004/isp_6_2004_101/ |
| work_keys_str_mv | AT nnkuzjurin probabilisticanalysisofthegreedyalgorithm |