Minimizing Submodular Functions over Hierarchical Families
This paper considers submodular function minimization (SFM) restricted to a family of subsets. We show that SFM over complements of families with certain hierarchical structures can be solved in polynomial-time. This yields a polynomial-time algorithm for SFM over complements of various families, such as intersecting families, crossing families, and the unions of lattices. Moreover, this tractability result partially settles the open question posed by Nägele, Sudakov, and Zenklusen on polynomial-solvability of SFM over the intersection of parity families. Furthermore, our tractability result…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2601.14805
curl -X POST /api/v1/records/arxiv/2601.14805/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2601.14805/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'