Timezone: »

 
Poster
Maximization of Approximately Submodular Functions
Thibaut Horel · Yaron Singer

Wed Dec 07 09:00 AM -- 12:30 PM (PST) @ Area 5+6+7+8 #139
in Wednesday Posters »
We study the problem of maximizing a function that is approximately submodular under a cardinality constraint. Approximate submodularity implicitly appears in a wide range of applications as in many cases errors in evaluation of a submodular function break submodularity. Say that $F$ is $\eps$-approximately submodular if there exists a submodular function $f$ such that $(1-\eps)f(S) \leq F(S)\leq (1+\eps)f(S)$ for all subsets $S$. We are interested in characterizing the query-complexity of maximizing $F$ subject to a cardinality constraint $k$ as a function of the error level $\eps > 0$. We provide both lower and upper bounds: for $\eps > n^{-1/2}$ we show an exponential query-complexity lower bound. In contrast, when $\eps < {1}/{k}$ or under a stronger bounded curvature assumption, we give constant approximation algorithms.
Keywords: Combinatorial Optimization
[ PDF] 

Author Information

Thibaut Horel (Harvard University)
Yaron Singer (Harvard University)

More from the Same Authors