Disjunctive Submodular Functions: Envelopes and Applications to Inventory and 0-1 Quadratic Optimization
This paper considers convex envelopes of disjunctive submodular functions---functions that are lattice family submodular over faces of a hypercube---and constructs the first strongly polynomial algorithm for their separation when there are two facial disjunctions. Submodular functions, whose convex envelopes are characterized by the Lovász extension, have occupied a fundamental role in constructing relaxations for combinatorial and nonlinear optimization problems. However, disjunctive submodular function envelopes have not been explored besides the use of ellipsoid algorithm, which remains…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.30712
curl -X POST /api/v1/records/arxiv/2609.30712/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.30712/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'