Metraipolis › archive › dc_5dde65eedbac
The Price of Feasibility: Greedy Approximation Bounds for String Supermodular Optimization over Oracle-Conditioned Greedoids — arXiv:2609.07787
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.07787
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T14:29:40.409Z
- SHA-256 of the archived text
858930e1cd34e294dc09d5f59897af03c2cf04cddb394ddbd124a60c35702021- Stable URL of this page
https://metraipolis.com/documento/dc_5dde65eedbac
How to cite
The Price of Feasibility: Greedy Approximation Bounds for String Supermodular Optimization over Oracle-Conditioned Greedoids — arXiv:2609.07787 — arXiv (en), https://arxiv.org/abs/2609.07787 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_5dde65eedbac (Metraipolis archive dc_5dde65eedbac, sha256 858930e1cd34e294dc09d5f59897af03c2cf04cddb394ddbd124a60c35702021)
BibTeX
@misc{dc5dde65eedbac,
title = {The Price of Feasibility: Greedy Approximation Bounds for String Supermodular Optimization over Oracle-Conditioned Greedoids — arXiv:2609.07787},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.07787},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_5dde65eedbac; sha256 858930e1cd34e294dc09d5f59897af03c2cf04cddb394ddbd124a60c35702021},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.07787. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Greedy algorithms efficiently approximate combinatorial optimization problems, but their guarantees weaken when feasibility couples combinatorial structure with global physical constraints. We study monotone nondecreasing supermodular minimization over the bases of a graphic greedoid under physics-induced constraints. We model physics-informed selection using a look-ahead oracle that identifies candidates extendable to a feasible basis, yielding the Conditioned Sequential Greedy Algorithm. We derive a closed-form approximation bound, which we call the price of feasibility, based on the variability of oracle-restricted candidate sets and a probabilistic correction for unobserved elements. As a case study, we show that FORWARD, an algorithm for multi-source radial network reconfiguration, instantiates this framework. Numerical results demonstrate the tightness of the bound and quantify the feasibility-optimality trade-off. Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-09 in math.OC). Categorie arXiv: Optimization and Control (math.OC) ; Combinatorics (math.CO). Pagina del lavoro: https://arxiv.org/abs/2609.07787 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-16T14:09:21.700Z dalla pagina https://arxiv.org/catchup/math.OC/2026-09-09?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).