The Price of Feasibility: Greedy Approximation Bounds for String Supermodular Optimization over Oracle-Conditioned Greedoids

Joan Vendrell Gallart, Russell Bent, Solmaz Kia

Greedy algorithms efficiently approximate combinatorial optimization problems, but their guarantees weaken when feasibility couples combinatorial structure with global physical con…