Approximate counting of common integer polymatroid bases

← All digests

Family 114 · Theoretical computer science
Importance 3/5 · Provisional editorial rating
Sources consulted 2026-10-09

Many allocation problems impose two overlapping systems of capacity constraints. Finding one feasible allocation can be tractable while counting all feasible allocations is much harder. Family 114 claims randomized relative counting for common bases of two arbitrary matroids, then extends this to integer polymatroids with potentially enormous binary-encoded capacities.

1. The question

Suppose resources must be allocated among several coordinates. One system limits combinations of coordinates in one way, while a second system imposes different limits. The task is to count allocations satisfying both systems and using the required total amount.

Even when each system separately has a well-behaved exchange structure, their intersection need not retain it. Moving one unit or swapping one selected element can violate one of the two sets of constraints.

A second challenge is numerical size. A capacity of a billion needs only about thirty binary digits. An algorithm that creates one object per capacity unit is not polynomial in the encoded input length.

The manuscripts address both issues. M2 treats ordinary matroid bases; M1 treats integer allocations and explicitly counts each vector once, without weighting it by the number of ways to assign labels to its units.

2. Background and essential definitions

Matroids and common bases

A matroid is a finite set $E$ together with independent subsets. Independence is preserved by taking subsets, and any smaller independent set can be enlarged using an element of a larger one. Linear independence of vectors and cycle-free sets of graph edges are standard examples.

The rank $r(A)$ is the maximum size of an independent subset of $A$. A basis is a maximal independent subset of the full ground set; all bases have the same size.

For two matroids on the same ground set and of equal rank, a common basis is a set that is a basis in both. If the ground set is the edges of a bipartite graph, one matroid can allow at most one selected edge at each left vertex and the other at most one at each right vertex. Their common full-size bases are perfect matchings.

Polymatroids permit integer amounts

A polymatroid replaces zero–one selection by nonnegative quantities. Its capacity function $r$ assigns a nonnegative integer to every subset of $E$. It is normalized, meaning $r(\varnothing)=0$, nondecreasing, and submodular:

$$r(A)+r(B)\ge r(A\cup B)+r(A\cap B).$$

Submodularity expresses a diminishing-returns structure. The extra capacity associated with adding coordinates becomes smaller when more coordinates are already present.

For $x=(x_j)_{j\in E}$, write $x(A)=\sum_{j\in A}x_j$. Given two such functions $r_1,r_2$ with equal total rank $R$, the family of common integer bases is

$$\Omega=\{x\in\mathbb Z_{\ge0}^{E}:x(E)=R, \ x(A)\le r_i(A)\text{ for all }A\subseteq E,\ i=1,2\}.$$

Every distinct integer vector counts once. If the only constraint is allocating two units between two coordinates, the vectors $(2,0),(1,1),(0,2)$ are three objects. Giving the units distinct labels would represent the middle vector twice, changing the counting measure.

Oracle access and approximation

An exact rank-value oracle returns $r_i(A)$ when queried with a subset $A$. It avoids explicitly listing exponentially many inequalities. Oracle calls are counted separately from the algorithm’s other bit operations; the internal work of the oracle is not included.

An FPRAS, or fully polynomial randomized approximation scheme, estimates $Z=|\Omega|$ within relative error $\varepsilon$ with failure probability at most $\delta$, using polynomial resources in input length, $\varepsilon^{-1}$, and $\log(1/\delta)$.

3. Development history and previous partial results

Edmonds’s matroid intersection theory established a fundamental distinction: finding and optimizing common independent sets can be efficient through independence queries. Counting all solutions requires additional ideas.

For one matroid, Feder and Mihail obtained sampling and counting results for balanced matroids, using negative dependence. Later work treated strongly Rayleigh distributions, another structured class with strong algebraic properties.

Anari, Liu, Oveis Gharan, and Vinzant removed these special assumptions for counting bases of a single arbitrary matroid. Their high-dimensional walks use log-concave polynomials to control random movement among bases.

Intersections remained harder. Anari, Oveis Gharan, and Vinzant obtained an exponential-in-rank factor approximation in polynomial time and relative approximation with exponential-in-rank running time. The latter becomes fully polynomial for small logarithmic rank, but not for arbitrary rank.

The permanent FPRAS of Jerrum, Sinclair, and Vigoda already solves a special common-basis case arising from two partition matroids. Its strategy of balancing nearly feasible states is an important methodological predecessor.

For integer allocations, Brändén and Huh’s Lorentzian polynomial theory provides powerful concavity properties. However, a factorial-normalized generating polynomial weights integer vectors differently from a uniform count. Nor does good behavior for one polymatroid automatically transfer to the intersection of two.

M1 builds on M2 and on the cell-bounded contingency-table construction in family 115. Its added task is to handle arbitrary submodular rank constraints and large binary capacities while preserving the intended one-vector-one-vote count.

4. What the new manuscripts claim

M2 claims an FPRAS for common bases of two equal-rank matroids given only exact independence oracles. No matrix representation, graph representation, or generating-polynomial evaluation oracle is required.

It also derives counting schemes for common independent sets of prescribed, unrestricted, or maximum cardinality, including when the two matroid ranks differ. Its almost-uniform samplers always return feasible objects on nonempty instances and detect emptiness exactly.

M1 claims an FPRAS for the common integer bases defined above, with $R$ supplied in binary and exact rank-value oracles. It returns a nonnegative rational estimate satisfying

$$\Pr[(1-\varepsilon)Z\le\widehat Z\le(1+\varepsilon)Z]\ge1-\delta.$$

On every execution, the number of oracle calls and the bit work outside the oracles are bounded by a fixed polynomial in ground-set size, binary input length, $\varepsilon^{-1}$, and $\log(1/\delta)$.

An empty feasible set always produces zero. If $R=0$, the unique common base is the zero vector. Lower-dimensional feasible regions are included; the theorem does not require an interior in the ambient coordinate space.

The polynomials have large fixed exponents. The claimed contribution is polynomial dependence on the correct input encoding, rather than an optimized implementation.

5. Why the advance matters

Importance: 3/5, provisional. The family would provide a general counting framework for intersecting combinatorial capacity systems, substantially extending the cases addressed by single-matroid methods.

Its oracle formulation is broad: a rank function can describe a feasible system without revealing an explicit matrix or an exponentially long list of inequalities. The result makes clear which information the counting algorithm actually needs.

Binary capacities are equally substantive. A theorem polynomial in the numerical capacity can be exponential in the length of the input. M1 claims to avoid that blowup while also avoiding the counting bias introduced by labeled expansions.

These are structural and asymptotic guarantees. The score reflects a substantial advance within counting and discrete optimization, while recognizing its specialized input model and the lack of a practical runtime claim.

6. The main idea

Turn two matroids into a paired selection problem

M2 makes two copies of the ground set, pairing corresponding elements. It combines the first matroid with the dual of the second. A dual matroid has as bases the complements of the original bases.

Selecting exactly one element from every pair is called a transversal. With the combined matroid chosen as in the paper, a transversal is a basis exactly when it represents a common basis of the original two systems.

The algorithm gives a positive but small weight to rank-deficient transversals. It also permits temporary defects: one empty pair and one doubly selected pair. These extra states provide routes between feasible selections that might otherwise be far apart.

Learn how to balance defects

Different defect types can have very different total weights. Multipliers are learned during an annealing schedule to keep them from overwhelming the target transversals or becoming too rare to be useful.

Algebraic inequalities control transport between conditional distributions and variation in the observables the algorithm estimates. The manuscript deliberately distinguishes this from proving fast mixing for every fluctuation inside every defect class.

A trace chain records successive returns to transversals. Controlling that chain and the relevant frequency estimates is sufficient for the counting procedure. The analytical partition sums and flows are not extra oracles supplied to the implementation.

Keep large ranges implicit

M1 cannot expand a huge capacity into that many pairs. Instead it finds a rational center of the common-base region and identifies near-tight constraints. These define partitions whose part totals have only polynomially many relevant discrete values.

Large remaining ranges are treated through weighted integration over free coordinates. Soft penalties suppress violations of the original constraints. Convex-volume approximation supplies numerical estimates of the resulting weights.

Integration preserves an ordinary form of log concavity, but the discrete counting framework needs stronger quadratic inequalities. The manuscript smooths and adjusts the weights, controls the difference between discrete changes and continuous derivatives, and establishes the needed inequalities for its particular construction.

Only bounded-range variables are expanded into paired labels. Factorial corrections cancel the multiplicities on target transversals, restoring unit mass per original integer vector.

7. Scope, limitations, and open questions

The rank functions are promised to satisfy the polymatroid axioms and to be available through exact value queries. The theorem does not provide an efficient test that an arbitrary black box satisfies those promises, nor does it include the black box’s internal computational cost.

The main integer-base theorem assumes equal total ranks. M2’s unequal-rank consequences concern common independent sets and should not be substituted indiscriminately for that hypothesis.

Counting each integer vector once is part of the problem definition. Applications requiring distinguishable units, factorial weights, or a different probability law need their own translation.

The result leaves practical efficiency, sharper polynomial exponents, and extensions to broader non-submodular constraints as separate questions. Its methods exploit the particular exchange and concavity structure of matroids and polymatroids.

8. Sources and further reading

M2 gives the paired-matroid reduction and its independence-oracle guarantees. M1 states the binary-capacity theorem and identifies the exact companion inputs it uses. The primary historical papers linked above explain why optimization, single-system counting, and intersection counting require different levels of machinery.

Source manuscripts

• M1. OpenAI, An FPRAS for Common Integer Polymatroid Bases with Binary Capacities (October 5, 2026).
• M2. OpenAI, Approximate counting of common bases of two matroids (September 23, 2026).

Sources consulted on 9 October 2026 at repository revision fd4aeeb. Download the manuscript citations.