{"id":"arxiv/2609.07787","url":"https://arxiv.org/abs/2609.07787","tags":["math.OC","math.CO"],"score":0,"title":"The Price of Feasibility: Greedy Approximation Bounds for String Supermodular Optimization over Oracle-Conditioned Greedoids","domain":"math.OC","source":"arxiv","authors":["Joan Vendrell Gallart","Russell Bent","Solmaz Kia"],"reviews":0,"subject":"math.OC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-07","reactions":{}}