Combinatorial Optimization using Comparison Oracles

Vincent Cohen-Addad, Tommaso d'Orsi, Anupam Gupta +7

In linear combinatorial optimization, we aim to find $S^{\ast }=\arg {\min }_{S\in \mathcal{F}}⟨w,1_S⟩$ for a family $\mathcal{F}\subseteq 2^U$ over a ground set…