Polyhedral results for two classes of submodular sets with GUB constraints
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}'