Polyhedral results for two classes of submodular sets with GUB constraints
Source: arxiv.org/abs/2601.18360
In this paper, we investigate the polyhedral structure of two submodular sets with generalized upper bound (GUB) constraints, which arise as important substructures in various real-world applications. We derive a class of strong valid inequalities for the two sets using sequential lifting techniques. The proposed lifted inequalities are facet-defining for the convex hulls of two sets and are stronger than the well-known extended polymatroid inequalities (EPIs). We provide a more compact characterization of these inequalities and show that each of them can be computed in linear time.…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2601.18360
curl -X POST /api/v1/records/arxiv/2601.18360/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2601.18360/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'