Combinatorial Optimization using Comparison Oracles
Vincent Cohen-Addad, Tommaso d’Orsi, Anupam Gupta, Guru Guruganesh, Euiwoong Lee, Renato Paes Leme, Debmalya Panigrahi, Madhusudhan Reddy Pittu, Jon Schneider, David P. Woodruff · 2025
Read Combinatorial Optimization using Comparison Oracles by Vincent Cohen-Addad, Tommaso d’Orsi, Anupam Gupta, Guru Guruganesh, Euiwoong Lee, Renato Paes Leme, Debmalya Panigrahi, Madhusudhan Reddy Pittu, Jon Schneider, David P. Woodruff (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-15142.txt.
Introduction
Vincent Cohen-Addad, Tommaso d'Orsi, and eight co-authors study optimization when the only feedback is which of two candidate solutions costs less. In the classic setup, exact weights are known or can be queried directly. A comparison oracle is weaker and more realistic for settings driven by pairwise preferences: it answers only whether one set beats another, ties, or loses.
Three results anchor the study. First, the number of comparisons needed over any set system grows only modestly with problem size, even though computing the optimum can still be hard, a clean split between information and computation. Further results cover efficient algorithms in this model. The work speaks to ranking, voting, and preference-driven design.
Catalog record
| CREATOR | Vincent Cohen-Addad, Tommaso d’Orsi, Anupam Gupta, Guru Guruganesh, Euiwoong Lee, Renato Paes Leme, Debmalya Panigrahi, Madhusudhan Reddy Pittu, Jon Schneider, David P. Woodruff |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 124 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-15142
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Combinatorial Optimization using Comparison Oracles Vincent Cohen-Addad, Tommaso d’Orsi, Anupam Gupta, Guru Guruganesh, Euiwoong Lee, Renato Paes Leme, Debmalya Panigrahi, Madhusudhan Reddy Pittu, Jon Schneider, David P. Woodruff Abstract In a linear combinatorial optimization problem, we are given a family ℱ ⊆ 2 U \mathcal{F}\subseteq 2^{U} of feasible subsets of a ground set U U of n n elements, and our goal is to find S ∗ = arg min S ∈ ℱ ⟨ w , 𝟙 S ⟩ S^{*}=\arg\min_{S\in\mathcal{F}}\langle w,\mathbbm{1}_{S}\rangle . 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 , 𝟙 S ⟩ w(S):=\langle w,\mathbbm{1}_{S}\rangle for any S ∈ ℱ S\in\mathcal{F} . Motivated by recent practical interest in solving problems via pairwise comparisons, and also by the intrinsic theoretical quest to understand fundamental computational models, we consider the weaker and more robust comparison oracle , which for any two feasible sets S , T ∈ ℱ S,T\in\mathcal{F} , reveals only if w ( S ) w(S) is less than/equal to/greater than w ( T ) w(T) . We ask: When can we find the optimal feasible set S ∗ = arg min S ∈ ℱ w ( S ) S^{*}=\arg\min_{S\in\mathcal{F}}w(S) using a small number of comparison queries? If so, when can we do this efficiently? We present three main contributions: 1. Our first main 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 ℱ ⊆ 2 U \mathcal{F}\subseteq 2^{U} is O ~ ( n 2 ) \widetilde{O}(n^{2}) . This result leverages the inference dimension framework, and demonstrates a fundamental separation between information complexity and computational complexity, as the runtime may still be exponential for NP-hard problems (assuming the Exponential Time Hypothesis). 2. Having resolved the query complexity, we turn to the algorithmic question. Our second result is a novel Global Subspace Learning (GSL) framework tailored for objective functions with discrete integer weights bounded by B B . We give an algorithm to sort all feasible sets by objective value using only O ( n B log ( n B ) ) O(nB\log(nB)) queries, improving upon the O ~ ( n 2 ) \widetilde{O}(n^{2}) bound when B = o ( n ) B=o(n) . Moreover, we show that this framework can be efficiently implemented for linear matroids using algebraic techniques, yielding efficient algorithms with improved query complexity for problems such as k k -SUM, SUBSET-SUM, and A + B A{+}B sorting. 3. Our third set of results give 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 s - t t paths. Our work provides the first general query complexity bounds and efficient algorithmic results for this fundamental model, opening new directions for comparison-based optimization, and suggests many directions for future research. 1 Introduction In a (linear) combinatorial optimization problem, we are given a family \mathcal{F}\subseteq 2^{U} of feasible subsets of a ground set U of n elements, and our goal is to find S^{*}=\arg\min_{S\in\mathcal{F}}\langle w,\mathbbm{1}_{S}\rangle . Traditionally, we are either given the weight vector w explicitly, or else we are given a value oracle which allows us to evaluate w(S):=\langle w,\mathbbm{1}_{S}\rangle for any S\in\mathcal{F} . In this work, we pose the question: Which combinatorial optimization problems can we efficiently solve if we are only allowed pairwise comparisons between feasible solutions? That is, we are given access to a comparison oracle that takes two feasible sets S,T\in\mathcal{F} , and outputs whether w(S) is less than/equal to/greater than w(T) . This comparison query model is perhaps the weakest feedback model where we can hope to optimize efficiently. 1 1 1 One can consider more general objective functions, such as XOS, submodular, subadditive, etc., where the function w(\cdot) is typically exponential-sized, and hence we can only access it via value or demand oracles. Our question—what can you do with just comparison queries—is interesting in these settings as well, but we focus on linear optimization for now. As a concrete question, consider the min-cut problem in this model. Specifically: We are given an undirected simple graph G=(V,E) . In each query, we can compare any two (edge) cuts to each other. Can we efficiently find a minimum cut in this graph? The min-cut problem has been intensively studied in the value-query model in recent years, leading to new insights and algorithms: can we replicate this success in the comparison-query model? More generally, our high-level motivation for the model comes from recent interest in applications (e.g., from crowdsourcing, recommendation systems, and most recently, RLHF) which solicit feedback from users only via comparison queries. In these settings, users’ notions of quality/utility is often difficult to quantify, or noisy, or only partially consistent, and hence they are asked to give relative preferences —choosing one alternative over another—rather than assigning precise numerical values. While these practical settings do not seek to solve precise optimization problems (like min-cuts or spanning trees), they do motivate the particularly clean query model we investigate in this work. 1.1 Our Results 1.1.1 Query Complexity We first focus on the query complexity of the problem: how many comparison queries give us enough information to solve the problem, without worrying about computation? Recall that we can only query pairs of feasible solutions, so it is completely unclear whether we can identify the optimal solution using much less than |\mathcal{F}| queries. For this query complexity question, we show a surprisingly general positive result: we can optimize over all Boolean families with a small number of queries! Theorem 1.1 (Boolean Linear Optimization) . For any family \mathcal{F}\subseteq 2^{U} and unknown weight function w^{*}:U\rightarrow\mathbb{R} , we can solve \arg\min_{S\in\mathcal{F}}\sum_{e\in S}w^{*}_{e} using O(n\log^{2}n\cdot\log|\mathcal{F}|)=\widetilde{O}(n^{2}) comparison queries, where n=|U| . We find Theorem 1.1 remarkable: it shows that the number of comparison queries required to find the optimal solution is only \widetilde{O}(n^{2}) , regardless of the complexity of the set system \mathcal{F} . Indeed, we could consider \mathcal{F} to represent set covers, independent sets, cliques, or other NP-hard problems for which finding the optimal set is believed to be computationally hard—nonetheless, the number of comparisons required is still nearly quadratic! Indeed, while the query complexity of the procedure in Theorem 1.1 is polynomial, its running time could be exponential (under standard complexity-theoretic assumptions). This shows a large gap between the information complexity and the computational complexity in this model. Problem Past Work Our Results Any Boolean - O(n^{2}\log^{2}n) optimization problem - O(nB\log(nB)) Table 1 : Our general results for query complexity. The second row is when weights are integers in [-B,B] . The key to proving Theorem 1.1 is to approach this query-complexity question from the correct perspective: we adapt the powerful active classification framework of [ KLMZ17 ] to the optimization setting. We show how to use their classification framework to also optimize over arbitrary point sets (and not just Boolean point sets) in \mathbb{R}^{d} , with