Combinatorial Optimization using Comparison Oracles

In linear combinatorial optimization, we aim to find S^* = argminS ∈ F langle w,1S rangle for a family F subseteq 2U over a ground set U of n elements. Traditionally, w is known or accessible via a value oracle. Motivated by practical applications involving pairwise preferences, we study the weaker and more robust comparison oracle, which for any S, T ∈ F reveals only if w(S) <, =, or > w(T). We investigate the query complexity and computational efficiency of optimizing in this model. We present three main contributions. (1) Query Complexity: We establish that the query complexity over any arbitrary set system F subseteq 2U is tildeO(n2). This demonstrates a fundamental separation between information and computational complexity, as the runtime may still be exponential for NP-hard problems. (2) Algorithmic Frameworks: We develop two general tools. First, a Dual Ellipsoid framework establishes an efficient reduction from optimization to certification. It shows that to optimize efficiently, it suffices to efficiently certify a candidate's optimality using only comparisons. Second, Global Subspace Learning (GSL) sorts all feasible sets using O(nB log(nB)) queries for integer weights bounded by B. We efficiently implement GSL for linear matroids, yielding improved query complexities for problems like k-SUM, SUBSET-SUM, and A+B sorting. (3) Combinatorial Applications: We give the first polynomial-time, low-query algorithms for classic problems, including minimum cuts, minimum weight spanning trees (and matroid bases), bipartite matching (and matroid intersection), and shortest s-t paths. Our work provides the first general query complexity bounds and efficient algorithmic results for this fundamental model.