Name
Title | ||
|---|---|---|
A Polynomial Lower Bound on the Number of Rounds for Parallel Submodular Function Minimization |
Abstract | ||
|---|---|---|
The problem of minimizing a submodular function (SFM) is a common generalization of several fundamental combinatorial optimization problems, including minimum $s-t$ cuts in graphs and matroid intersection. It is well-known that a submodular function can be minimized with only $\text{poly} (N)$ function evaluation queries where $N$ denotes the universe size. However... |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1109/FOCS52979.2021.00013 | 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) |
Keywords | DocType | ISSN |
Computer science,Minimization,Optimization | Conference | 0272-5428 |
ISBN | Citations | PageRank |
978-1-6654-2055-6 | 0 | 0.34 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Deeparnab Chakrabarty | 1 | 400 | 41.50 |
| Yu Chen | 2 | 0 | 6.76 |
| Sanjeev Khanna | 3 | 4403 | 319.91 |