Combinatorial optimization with bounded subdeterminants
Source: arxiv.org/abs/2611.13065
We take a first step toward a broader study of classical combinatorial optimization problems through the maximum subdeterminants of their standard integer programming formulations, yielding new positive results for several famous (NP-hard) problems. An integer matrix is totally $Δ$-modular if every square submatrix has determinant of absolute value at most $Δ$. For every fixed $Δ$, it has been known that maximum clique, maximum stable set, and minimum vertex cover can be solved in polynomial time on instances for which the coefficient matrix of the natural formulation is totally $Δ$-modular.…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.13065
curl -X POST /api/v1/records/arxiv/2611.13065/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.13065/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'