Loading...
Please wait, while we are loading the content...
Algorithms and Lower Bounds for Submodular Cuts and Approximating Submodular Functions (Combinatorial Optimization and Discrete Algorithms)
| Content Provider | Semantic Scholar |
|---|---|
| Author | Svitkina, Zoya Fleischer, Lisa |
| Copyright Year | 2010 |
| Abstract | We study the submodular sparsest cut problem, which is a generalization of the classical sparsest cut problem obtained by replacing the graph cut function with a general submodular function, and establish matching upper and lower bounds for its approximability. Then we apply the approximation algorithm for submodular sparsest cut to obtain bicriteria approximation results for a related problem, submodular balanced cut, which generalizes the balanced cut problem on graphs. We also give an improved lower bound for the problem of approximating a monotone submodular function everywhere. Then we present an algorithm for approximating monotone submodular functions with special structure, called two-partition functions. This algorithm’s guarantee is close to the lower bound, which uses two-partition functions, and therefore applies even in this special case. |
| Starting Page | 213 |
| Ending Page | 232 |
| Page Count | 20 |
| File Format | PDF HTM / HTML |
| Volume Number | 23 |
| Alternate Webpage(s) | http://www.kurims.kyoto-u.ac.jp/~kenkyubu/bessatsu/open/B23/pdf/B23_011.pdf |
| Alternate Webpage(s) | https://core.ac.uk/download/pdf/39302830.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
