Approximating Submodular Functions Everywhere
URL to paper from conference site
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Society for Industrial and Applied Mathematics
2011
|
| Online Access: | http://hdl.handle.net/1721.1/60671 https://orcid.org/0000-0002-0520-1165 |
| _version_ | 1826205789953458176 |
|---|---|
| author | Goemans, Michel X. Harvey, Nicholas J. A. Iwata, Satoru Mirrokni, Vahab |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Goemans, Michel X. Harvey, Nicholas J. A. Iwata, Satoru Mirrokni, Vahab |
| author_sort | Goemans, Michel X. |
| collection | MIT |
| description | URL to paper from conference site |
| first_indexed | 2024-09-23T13:19:09Z |
| format | Article |
| id | mit-1721.1/60671 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T13:19:09Z |
| publishDate | 2011 |
| publisher | Society for Industrial and Applied Mathematics |
| record_format | dspace |
| spelling | mit-1721.1/606712022-10-01T14:28:03Z Approximating Submodular Functions Everywhere Goemans, Michel X. Harvey, Nicholas J. A. Iwata, Satoru Mirrokni, Vahab Massachusetts Institute of Technology. Department of Mathematics Goemans, Michel X. Goemans, Michel X. URL to paper from conference site Submodular functions are a key concept in combinatorial optimization. Algorithms that involve submodular functions usually assume that they are given by a (value) oracle. Many interesting problems involving submodular functions can be solved using only polynomially many queries to the oracle, e.g., exact minimization or approximate maximization. In this paper, we consider the problem of approximating a non-negative, monotone, submodular function f on a ground set of size n everywhere, after only poly(n) oracle queries. Our main result is a deterministic algorithm that makes poly(n) oracle queries and derives a function ^ f such that, for every set S, ^ f(S) approximates f(S) within a factor alpha(n), where alpha(n) = [sqrt]n + 1 for rank functions of matroids and alpha(n) = O( [sqrt]n log n) for general monotone submodular functions. Our result is based on approximately finding a maximum volume inscribed ellipsoid in a symmetrized polymatroid, and the analysis involves various properties of submodular functions and polymatroids. Our algorithm is tight up to logarithmic factors. Indeed, we show that no algorithm can achieve a factor better than Omega([sqrt]n= log n), even for rank functions of a matroid. National Science Foundation (U.S.) (CCF-0515221) National Science Foundation (U.S.) (CCF-0829878) United States. Office of Naval Research (N00014-05-1-0148) 2011-01-19T20:19:07Z 2011-01-19T20:19:07Z 2009-01 Article http://purl.org/eprint/type/ConferencePaper 1071-9040 http://hdl.handle.net/1721.1/60671 Goemans, Michel X. et al. "Approximating Submodular Functions Everywhere." ACM-SIAM Symposium on Discrete Algorithms, Jan. 4-6, 2009, New York, NY. © 2009 Society for Industrial and Applied Mathematics. https://orcid.org/0000-0002-0520-1165 en_US http://www.siam.org/proceedings/soda/2009/soda09.php Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009 (SODA'09) Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Society for Industrial and Applied Mathematics SIAM |
| spellingShingle | Goemans, Michel X. Harvey, Nicholas J. A. Iwata, Satoru Mirrokni, Vahab Approximating Submodular Functions Everywhere |
| title | Approximating Submodular Functions Everywhere |
| title_full | Approximating Submodular Functions Everywhere |
| title_fullStr | Approximating Submodular Functions Everywhere |
| title_full_unstemmed | Approximating Submodular Functions Everywhere |
| title_short | Approximating Submodular Functions Everywhere |
| title_sort | approximating submodular functions everywhere |
| url | http://hdl.handle.net/1721.1/60671 https://orcid.org/0000-0002-0520-1165 |
| work_keys_str_mv | AT goemansmichelx approximatingsubmodularfunctionseverywhere AT harveynicholasja approximatingsubmodularfunctionseverywhere AT iwatasatoru approximatingsubmodularfunctionseverywhere AT mirroknivahab approximatingsubmodularfunctionseverywhere |