Approximate counting of common integer polymatroid bases

The explanation

Three workers need three jobs, A, B and C. Worker 1 can do A or B. Worker 2 can do any of the three. Worker 3 can do B or C. Each worker gets one job, and every job gets filled. Checking all six orderings shows that exactly three assignments work. Small cases like this are easy to list. Large ones are not. If 100 workers can each do any of 100 jobs, there are 100 factorial assignments, about 9.3 × 10^157.

This puzzle is one case of a general question about matroids. A matroid is a rule that says which groups of items are allowed together. Here the items are the seven allowed worker–job pairs. One rule says no worker appears twice. A second rule says no job appears twice. A basis is a largest allowed group. A common basis is a group that is a basis under both rules. In this example, the common bases are exactly the three full assignments.

Counting common bases exactly is often out of reach, so the goal is a close estimate. The standard target has a long name: a fully polynomial randomized approximation scheme, or FPRAS. Ask for 1 percent accuracy, and the answer lands between 0.99 and 1.01 times the true count. It may fail, but only with a small chance you choose in advance. Its cost must grow like a fixed power of the input size and of 1/accuracy. Here the method may only query an independence oracle. That is a black box that says whether a given group is allowed.

Pieces of this were known. In 2004, Jerrum, Sinclair and Vigoda gave an FPRAS for the permanent. That covers the worker–job case. Anari, Liu, Oveis Gharan and Vinzant later gave an independence-oracle FPRAS for the bases of one matroid. For two matroids, Anari, Oveis Gharan and Vinzant had an estimate whose running time grows exponentially with the basis size. Kuikui Liu's 2023 dissertation recorded the two-matroid question as an open problem.

The first paper proves an FPRAS for common bases of any two equal-rank matroids (Lean proof listed)Source 1. Rank means the size of a basis. The method takes a random walk among candidate answers, as in the permanent algorithm. The obstacle is that the walk must pass through rare in-between statesSource 2. The paper adds slightly broken states and learns how much weight to give each kindSource 3. The result also covers common allowed groups of any fixed size, even when the two ranks differSource 4.

The second paper claims to extend this from yes-or-no choices to whole-number amounts. Picture a 3 × 3 table of whole numbers. Every row and every column must add up to 1,000,000. Writing down these rules takes six seven-digit numbers. Yet the number of such tables is 125,000,750,001,875,002,250,001, about 1.25 × 10^23. Such tables are one example of common integer bases of two polymatroids. A polymatroid is a rule that gives every group of cells a ceiling on its total. Here one rule caps groups by their rows, the other by their columns.

Large numbers were the obstacle. The classical trick replaces a capacity of a million by a million labelled copies of one unit. That makes the problem as large as the capacity itself, not its number of digits. It also counts each table many times, once per labellingSource 5. The paper avoids the copiesSource 6. It keeps only a few totals that take a modest number of values. It treats the rest like a smooth shape whose volume can be estimatedSource 7. Large expansions appear only inside the proof, never in what the algorithm runsSource 8.

So for the table above, the cost is claimed to grow with the seven digits, not with the million. The answer is still an estimate, not an exact count, and it uses random choices. The paper also warns that its polynomial has large fixed exponentsSource 9. The point is how cost grows with the input, not a fast program.

How sure is this? A computer proof checker called Lean has checked a formal version of the two-matroid theorem. The scope note links a fixed reference statement for a tool called Comparator. The polymatroid paper with large capacities is outside that check. So is the result on common allowed groups of other sizes. No specialist review of either paper has been published.

What it doesn't show. This does not give exact counts or a practically fast program; the paper says its polynomial has large fixed exponents.