Combinatorial Optimization using Comparison Oracles
In a linear combinatorial optimization problem, we are given a family F C 2U of feasible subsets of a ground set U of n elements, and our goal is to find S∗ = argminSeF «w,1S . Traditionally, we are either given the weight vector up-front, or else we are given a value oracle which allows us to evaluate w(S) := «w, 1S »for any SeF. We consider the weaker and more robust comparison oracle, which for any two feasible sets S, TeF, reveals only if w(S) is less than/equal to/greater than w(T). We ask: When can we find the optimal feasible set S∗ = argminSeF w(S) using a small number of comparison queries? If so, when can we do this efficiently? We present three main contributions: Our first result is a surprisingly general answer to the query complexity. We establish that the query complexity for the above problem over any arbitrary set system F C 2U is (n2). This result uses the inference dimension framework, and shows a fundamental separation between information complexity and computational complexity, as the runtime may still be exponential for NP-hard problems. We then develop two general algorithmic frameworks: the first being Optimization from Certification, where we present a novel Dual Ellipsoid framework that establishes an efficient reduction from optimization to certification. This framework demonstrates that to optimize efficiently, it is sufficient to design an efficient certification for the optimality of a candidate set S∗ with the knowledge of w∗ using only comparisons between feasible sets. This framework also yields a deterministic low query complexity algorithm. The second framework is that of Global Subspace Learning (GSL), which is tailored for integer objective functions bounded by B. We sort all feasible sets using only O(nB log(nB)) queries, improving upon the (n2) bound when B=o(n). We efficiently implement this framework for linear matroids via algebraic techniques, yielding efficient algorithms with improved query complexity k-SUM, SUBSET-SUM, and A+B sorting. Our final set of results gives the first polynomial-time, low-query algorithms for several classic combinatorial problems. We develop such algorithms for finding minimum cuts in simple graphs, minimum weight spanning trees (and matroid bases in general), bipartite matching (and matroid intersection), and shortest s-t paths. A full version of this paper is available at https://arxiv.org/abs/2511.15142.
