arXiv preprint ·
Symmetric Submodular Minimization from Comparisons
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
Given value-oracle access to a symmetric submodular function $f:2^V\to\mathbb{R}$ with $|V|=n$, a nontrivial minimizer can be found using $O(n^3)$ value queries. We study the weaker comparison model, in which a query on $S,T\subseteq V$ reveals only whether $f(S)$ is smaller than, equal to, or larger than $f(T)$. We give a deterministic polynomial-time algorithm that finds a nontrivial minimizer of any symmetric submodular function using $O(n^3)$ comparisons, matching the best-known deterministic value-oracle bound despite not knowing the function values. More generally, the same $O(n^3)$-comparison bound holds for minimization over the nonempty members of any downward-closed family. Our algorithm combines the minimum-capacity ordering recently introduced by Iwata and Konno with the contraction framework of Goemans and Soto. Applying this result to weighted graph cut functions resolves the main open question of Cohen-Addad et al., who gave an $\widetilde{O}(n^3)$-comparison algorithm that runs in exponential time and asked whether a weighted minimum cut can be found in polynomial time using comparisons. For graphs with $m$ edges of integer weight at most $B$, we also give a deterministic polynomial-time algorithm that finds a minimum cut using \[ \widetilde{O}\!\left(n^2+\min\!\left\{mB,\,nB^2\right\}\right) \] comparisons, improving on the $O(n^3)$ bound when $B$ is small. Finally, we show that every randomized algorithm that outputs a minimum cut with probability at least $2/3$ makes $Ω(n \log n)$ expected comparisons in the worst case. Under the stronger assumption that all edge weights are polynomially bounded integers, we obtain an $Ω(n \log \log n)$ expected comparison lower bound. These bounds contrast with the value-oracle model, where no $ω(n)$ lower bound is known even for deterministic algorithms.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Generating cyclic pivot Gray codes for well-ordered $k$-degenerate graphs in constant amortized time
Tight Bounds for Equivalence Testing with Non-Adaptive Conditional Samples
Envy-free Allocations with Individual Payments
Tight bounds and output sensitive algorithms for maximal clique enumeration in link streams
Almost Optimal Constant-Round Approximation of Dominating Set in Graph Classes with Excluded Minors
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.