|
|||||
|
|
On the ratio of optimal integral and fractional covers |
|
| Authors: | L. Lovász |
| Affiliation: | Eötvös L. University, Budapest, Hungary |
| Abstract: | It is shown that the ratio of optimal integral and fractional covers of a hypergraph does not exceed 1 + log d, where d is the maximum degree. This theorem may replace probabilistic methods in certain circumstances. Several applications are shown. |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ | |