Common Optimal Supports and Bottleneck Hierarchies in Truncated Cones
Abstract
{Let K⊆ℝ+E be a closed convex cone and P=K∩[0,1]E. For a linear objective with positive optimum, we study the intersection of the coordinate supports of all optimal solutions.} We prove that this common support is a transversal of a natural clutter associated with the positive directions of the cone and introduce a decreasing hierarchy of bottleneck families that stabilizes after at most |E|−1 levels. In the polyhedral setting, the first level consists exactly of the sets carrying feasible upper-bound dual multipliers, while every set carrying an optimal multiplier belongs to the stabilized family. {The breadth of the join-semilattice generated under union by the zero sets of the nonzero vertices gives an objective-independent upper bound on the universal stabilization depth;} this bound is exact for simplicial truncations. Every possible depth occurs, and the |E|−1 bound is sharp. Membership in the second level is co-NP-complete and fixed-parameter tractable in the size of the candidate bottleneck. Under upper-box-integrality and the integer decomposition property, the hierarchy collapses at level two, and its stabilized members are exactly the carriers of optimal upper-bound multipliers. When P is integral, the common optimal support is the union of the supports of all optimal dual solutions. Applications include bipartite matchings, maximum-order cycle subdigraphs, binary circulations, balanced hypergraph matchings, interval hypergraphs, and maximum-weight closures.
Related
- Extension on the convergence rates of moment-SOS hierarchies via approximation of truncated moment sequences
- Competing coherence geometries in positive maps: positivity hierarchies, atomicity, and optimal entanglement witnesses
- Optimal Multitask Representations Under a Rate Constraint: An Information Bottleneck Analysis
- On the Cardinality of Optimal Representations in the Binary-Source Information Bottleneck
- Truncated ℋ2 Optimal Model Order Reduction for Bilinear Quadratic Output Systems
BibTeX
@misc{benameur2026common,
title = {{Common Optimal Supports and Bottleneck Hierarchies in Truncated Cones}},
author = {Walid Ben-Ameur and Alessandro Maddaloni},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.37589},
eprint = {2609.37589},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.37589},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Common Optimal Supports and Bottleneck Hierarchies in Truncated Cones
AU - Walid Ben-Ameur
AU - Alessandro Maddaloni
PY - 2026
DA - 2026/09/29
PB - arXiv
DO - 10.48550/arxiv.2609.37589
UR - https://arxiv.org/abs/2609.37589
AB - {Let K⊆ℝ_+^E be a closed convex cone and P=K∩[0,1]^E. For a linear objective with positive optimum, we study the intersection of the coordinate supports of all optimal solutions.} We prove that this common support is a transversal of a natural clutter associated with the positive directions of the cone and introduce a decreasing hierarchy of bottleneck families that stabilizes after at most |E|−1 levels. In the polyhedral setting, the first level consists exactly of the sets carrying feasible upper-bound dual multipliers, while every set carrying an optimal multiplier belongs to the stabilized family. {The breadth of the join-semilattice generated under union by the zero sets of the nonzero vertices gives an objective-independent upper bound on the universal stabilization depth;} this bound is exact for simplicial truncations. Every possible depth occurs, and the |E|−1 bound is sharp. Membership in the second level is co-NP-complete and fixed-parameter tractable in the size of the candidate bottleneck. Under upper-box-integrality and the integer decomposition property, the hierarchy collapses at level two, and its stabilized members are exactly the carriers of optimal upper-bound multipliers. When P is integral, the common optimal support is the union of the supports of all optimal dual solutions. Applications include bipartite matchings, maximum-order cycle subdigraphs, binary circulations, balanced hypergraph matchings, interval hypergraphs, and maximum-weight closures.
ER -