Polynomial Matrices in Integer Programming With Restricted Subdeterminants
We introduce a framework for tackling questions in discrete optimization associated with parametric constraint matrices. More precisely, the constraint matrices have entries that are polynomials in one variable and all subdeterminants of these matrices are polynomials in a given prescribed set $S$. Two key problems arise in this context. The first is the recognition problem: can a matrix of this form be recognized in polynomial time? The second is the optimization problem: given an integer program whose constraint matrix is of this form, can it be solved in polynomial time? We answer both…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2607.08935
curl -X POST /api/v1/records/arxiv/2607.08935/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.08935/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'