{"ID":2839391,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.15142","arxiv_id":"2511.15142","title":"Combinatorial Optimization using Comparison Oracles","abstract":"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) \u003c, =, \\text{ or } \u003e 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.","short_abstract":"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 pr...","url_abs":"https://arxiv.org/abs/2511.15142","url_pdf":"https://arxiv.org/pdf/2511.15142v2","authors":"[\"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\"]","published":"2025-11-19T05:39:33Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}