| We give a quasi-polynomial-time incremental algorithm for enumerating all minimal solutions to a system of integer-valued monotone submodular inequalities fix1,&ldots;,xn ≥ti, i=1,&ldots;,r, where x1,…,x n are integer or binary variables, each function f i is defined by an evaluation oracle and the right-hand sides t1,…,tr are bounded by a quasi-polynomial in the dimension of the system: t 1,…,tr ≤ 2polylog( nr). The latter condition can be dropped for systems of linear inequalities, but is necessary in general, unless all problems in NP can be solved in quasipolynomial time. Our enumeration algorithm provides a partial answer to the conjecture of Lawler, Lenstra and Rinnooy Kan (1980) that all minimal integer solutions to a system of non-negative linear inequalities cannot be enumerated efficiently, unless P = NP. It also implies an incremental quasi-polynomial-time algorithm for enumerating all maximal independent sets in r matroids defined by independence oracles on a common ground set. This improves on the previously known exponential bound on the complexity of the matroid intersection problem. Other special cases of our general result include the generation of minimal infrequent sets of a database (data mining), minimal space-spanning collections of subspaces from a given list, and minimal connectivity ensuring collections of subgraphs from a given list (reliability theory).; Our proofs are based on two key facts. We first show that the number of maximal infeasible solutions to any system of monotone submodular inequalities can be bounded by a quasi-polynomial in n, r, and the number of minimal feasible solutions. We also give stronger bounds for some special cases, as well as some generalizations, of polymatroid functions, including 2-monotonic functions, k-smooth polymatroid functions and functions with non-negative Möbius coefficients. Examples are also given to demonstrate that our bounds are reasonably sharp. Second, we extend the known quasi-polynomial bound on the complexity of the hypergraph dualization problem to families of vectors defined on products of chains (or more generally, on products of lattices of bounded width).; Finally, we show that for hypergraphs of bounded edge size, the problem of extending a given list of transversals (equivalently, maximal independent sets) can be solved efficiently in parallel. |
