Two remarks concerning balanced matroids
| dc.creator | Jerrum, Mark | |
| dc.date | 2004-04-09 | |
| dc.date.accessioned | 2026-07-07T05:07:19Z | |
| dc.date.available | 2026-07-07T05:07:19Z | |
| dc.description | The property of balance (in the sense of Feder and Mihail) is investigated in the context of paving matroids. The following examples are exhibited: (a) a class of ``sparse'' paving matroids that are balanced, but at the same time rich enough combinatorially to permit the encoding of hard counting problems; and (b) a paving matroid that is not balanced. The computational significance of (a) is the following. As a consequence of balance, there is an efficient algorithm for approximating the number of bases of a sparse paving matroid within specified relative error. On the other hand, determining the number of bases exactly is likely to be computationally intractable. | |
| dc.identifier | https://arxiv.org/abs/math/0404200 | |
| dc.identifier | http://arxiv.org/abs/math/0404200 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/70816 | |
| dc.subject | Combinatorics | |
| dc.subject | 05B35 (Primary), 52B40, 52B60, 68W20, 68W25 | |
| dc.title | Two remarks concerning balanced matroids | |
| dc.type | text |