Name
Abstract | ||
|---|---|---|
We investigate a new optimization problem involving minimizing the Ratio of two Submodular (RS) functions. We argue that this problem occurs naturally in several real world applications. We then show the connection between this problem and several related problems including minimizing the difference between submodular functions (Iyer u0026 Bilmes, 2012b; Narasimhan u0026 Bilmes, 2005), and to submodular optimization subject to submodular constraints (Iyer u0026 Bilmes, 2013). We show that RS optimization can be solved with bounded approximation factors. We also provide a hardness bound and show that our tightest algorithm matches the lower bound up to a log factor. Finally, we empirically demonstrate the performance and good scalability properties of our algorithms. |
Year | Venue | Field |
|---|---|---|
2016 | ICML | Discrete mathematics,Mathematical optimization,Computer science,Upper and lower bounds,Submodular set function,Algorithm,Optimization problem,Scalability,Bounded function |
DocType | Citations | PageRank |
Conference | 2 | 0.40 |
References | Authors | |
19 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Wenruo Bai | 1 | 6 | 2.92 |
| Rishabh K. Iyer | 2 | 34 | 8.80 |
| Kai Wei | 3 | 3 | 1.10 |
| Jeff A. Bilmes | 4 | 278 | 16.88 |