Preprint
Sep 2026
The Price of Feasibility: Greedy Approximation Bounds for String Supermodular Optimization over Oracle-Conditioned Greedoids
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....
Joan Vendrell Gallart, Russell Bent, S. Kia
· 0 citations