Combinatorial Optimization using Comparison Oracles
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917283571433472 |
|---|---|
| author | Cohen-Addad, Vincent d'Orsi, Tommaso Gupta, Anupam Guruganesh, Guru Lee, Euiwoong Leme, Renato Paes Panigrahi, Debmalya Pittu, Madhusudhan Reddy Schneider, Jon Woodruff, David P. |
| author_facet | Cohen-Addad, Vincent d'Orsi, Tommaso Gupta, Anupam Guruganesh, Guru Lee, Euiwoong Leme, Renato Paes Panigrahi, Debmalya Pittu, Madhusudhan Reddy Schneider, Jon Woodruff, David P. |
| contents | In linear combinatorial optimization, we aim to find $S^* = \arg\min_{S \in \mathcal{F}} \langle w,\mathbf{1}_S \rangle$ for a family $\mathcal{F} \subseteq 2^U$ 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 \in \mathcal{F}$ reveals only if $w(S) <, =, \text{ 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 $\mathcal{F} \subseteq 2^U$ is $\tilde{O}(n^2)$. 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_15142 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Combinatorial Optimization using Comparison Oracles Cohen-Addad, Vincent d'Orsi, Tommaso Gupta, Anupam Guruganesh, Guru Lee, Euiwoong Leme, Renato Paes Panigrahi, Debmalya Pittu, Madhusudhan Reddy Schneider, Jon Woodruff, David P. Data Structures and Algorithms In linear combinatorial optimization, we aim to find $S^* = \arg\min_{S \in \mathcal{F}} \langle w,\mathbf{1}_S \rangle$ for a family $\mathcal{F} \subseteq 2^U$ 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 \in \mathcal{F}$ reveals only if $w(S) <, =, \text{ 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 $\mathcal{F} \subseteq 2^U$ is $\tilde{O}(n^2)$. 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. |
| title | Combinatorial Optimization using Comparison Oracles |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2511.15142 |