Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1007/s00493-006-0039-5 | Combinatorica |
Keywords | Field | DocType |
relative error | Matroid,Discrete mathematics,Combinatorics,Counting problem,Matroid partitioning,Graphic matroid,Approximation error,Mathematics,Encoding (memory) | Journal |
Volume | Issue | ISSN |
26 | 6 | 0209-9683 |
Citations | PageRank | References |
6 | 0.55 | 6 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| mark jerrum | 1 | 2755 | 564.62 |