登入選單

返回Google圖書搜尋

A Note on the Budgeted Maximization of Submodular Functions

Andreas Krause

出版	Carnegie Mellon University. Center for Automated Learning and Discovery, 2005
URL	http://books.google.com.hk/books?id=MBH6PgAACAAJ&hl=&source=gbs_api

註釋

Abstract: "Many set functions F in combinatorial optimization satisfy the diminishing returns property F(A [union of] X) - F(A) [> or =] F(A' [union of] X) - F(A') for A [element of] A'. Such functions are called submodular. A result from Nemhauser et.al. states that the problem of selecting k-element subsets maximizing a nondecreasing submodular function can be approximated with a constant factor (1 - 1/e) performance guarantee. Khuller et.al. showed that for the special submodular function involved in the MAX-COVER problem, this approximation result generalizes to a budgeted setting under linear nonnegative cost-functions. In this note, we extend this result to general submodular functions. Motivated by the problem of maximizing entropy in discrete graphical models, where the submodular objective cannot be evaluated exactly, we generalize our result to account for absolute errors."