English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

This paper introduces a framework to study discrete optimization problemswhich are parametric in the following sense: their constraint matricescorrespond to matrices over the ring $\mathbb{Z}[x]$ of polynomials in onevariable. We investigate in particular matrices whose subdeterminants all liein a fixed set $S\subseteq\mathbb{Z}[x]$. Such matrices, which we call totally$S$-modular matrices, are closed with respect to taking submatrices, so it isnatural to look at minimally non-totally $S$-modular matrices which we callforbidden minors for $S$. Among other results, we prove that if $S$ is finite,then the set of all determinants attained by a forbidden minor for $S$ is alsofinite. Specializing to the integers, we subsequently obtain the followingpositive complexity result: for all but finitely many values of$a\in\mathbb{Z}$, if a totally $\pm\{0,1,a,a+1,2a+1\}$-modular constraintmatrix has entries in $a$ and $a+1$, then the corresponding recognition problemand the integer linear optimization problem can be solved in polynomial time.

On Matrices over a Polynomial Ring with Restricted Subdeterminants