The Price of Feasibility: Greedy Approximation Bounds for String Supermodular Optimization over Oracle-Conditioned Greedoids
Abstract
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.
Related
- Rare subtree patterns in size-conditioned Bienaymé trees: Poisson approximation and declumping
- Two moments suffice for Bessel approximation: conditioned differences, contingency tables, and probabilistic divide-and-conquer
- Quantum Vehicle Routing Problem: a smart initialization strategy for ill-conditioned optimization landscapes
- From Variational Optimization to Flow-Based Transport: Posterior-Geometry Regularization for Ill-Conditioned Data Assimilation
- Microstructure-Conditioned Surrogate Models for Graded Multiscale Optimization of Mycelium Composites
BibTeX
@misc{gallart2026price,
title = {{The Price of Feasibility: Greedy Approximation Bounds for String Supermodular Optimization over Oracle-Conditioned Greedoids}},
author = {Joan Vendrell Gallart and Russell Bent and Solmaz Kia},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.07787},
eprint = {2609.07787},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.07787},
}
RIS
TY - UNPB
TI - The Price of Feasibility: Greedy Approximation Bounds for String Supermodular Optimization over Oracle-Conditioned Greedoids
AU - Joan Vendrell Gallart
AU - Russell Bent
AU - Solmaz Kia
PY - 2026
DA - 2026/09/07
PB - arXiv
DO - 10.48550/arxiv.2609.07787
UR - https://arxiv.org/abs/2609.07787
AB - 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.
ER -