Fast Submodular Minimization for Represented Matroid Ranks

Definitions and mathematical statement

Let $K$ be a field and let $A=(a_v)_{v\in V}$ be an explicitly supplied matrix over $K$, with columns indexed by the ground set $V$. For the finite-input interpretation of the algorithmic question, take $V$ and the number of rows of $A$ to be finite; the source does not explicitly state this finiteness hypothesis. The represented matroid has rank function \[ r(S)=\dim_K\operatorname{span}_K\{a_v:v\in S\},\qquad S\subseteq V. \] Given $z:V\to{\mathbb{R}}$, define \[ z(S)=\sum_{v\in S}z(v),\qquad z(\varnothing)=r(\varnothing)=0. \] The computational task is to determine the value \[ \mu(A,z)=\min_{S\subseteq V}\left(r(S)-z(S)\right). \] The source asks whether the explicit linear representation can be exploited to compute this value more efficiently. This is an algorithmic research question rather than a specified complexity conjecture: the source supplies no target running time, precise comparison bound, field-operation model, encoding of the real weights, or deterministic versus randomized requirement. Those choices must be specified before a precise running-time claim can be formulated.

The supplied curation describes the problem as partially solved: it reports that strongly polynomial algorithms for general submodular-function minimization cover this objective, that later work improves general submodular-minimization bounds, and that a representation-specific improvement beyond those algorithms remains unresolved. These are supplied dated assessments, not independently verified conclusions of this draft.

Short English statement

Given an explicit matrix representing a matroid and real weights on its columns, minimize the rank of a selected set of columns minus its total weight. The question asks whether using the matrix directly yields a faster algorithm. The intended computational model and the quantitative meaning of "faster" remain unspecified.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $30004005$, titled "Fast Submodular Minimization for Represented Matroid Ranks," in the Oberwolfach Reports Open Problems collection; exact source problem code catalogue entry. The record gives proposed year 2018 and supplies no named proposer.
• Supplied report citation: Combinatorial Optimization (2019), Oberwolfach Reports, DOI 10.4171/owr/2018/50, pp. 2969--3023. https://doi.org/10.4171/owr/2018/50. The supplied background describes these reports as documentation of mathematical workshops and their open-problem discussions.
• Supplied literature source: Convex Minimization with Integer Minima in O-tilde(n4) Time. https://arxiv.org/abs/2304.03426.
• Supplied literature source: Oberwolfach Report 50/2018. https://ems.press/content/serial-article-files/46772.
• Literature assessment checked on 2026-08-21, according to the supplied record: status "partially solved"; general strongly polynomial submodular-minimization algorithms are reported to cover the objective, later work is reported to improve general bounds, and improvement specific to the representation is reported as unresolved. This is supplied dated curation derived from the supplied OWR curation, not independently verified literature assessment; its status and cited claims require independent verification.