Approximating convex functions via non-convex oracles under the relative noise model

作     者：Halman, Nir 

作者机构：Hebrew Univ Jerusalem IL-91905 Jerusalem Israel 

出 版 物：《DISCRETE OPTIMIZATION》 (离散优化)

年 卷 期：2015年第16卷

页      面：1-16页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070102[理学-计算数学] 0701[理学-数学] 

基　　金：European Community Recanati Fund of the School of Business Administration, the Hebrew University of Jerusalem 

主　　题：Approximate binary search Dynamic programming Property preserving reconstruction 

摘      要：We study succinct representations of a convex univariate function phi over a finite domain. We show how to construct a succinct representation, namely a piecewise-linear function (phi) over bar approximating phi when given a black box access to an L-approximation oracle (phi) over tilde of phi (the oracle value is always within a multiplicative factor L from the true value). The piecewise linear function (phi) over bar has few breakpoints (poly-logarithmic in the size of the domain and the function values) and approximates the true function phi up to a (1+epsilon)L-2 multiplicative factor point-wise, for any epsilon 0. This function (phi) over bar is also convex so it can be used as a replacement for the original function and be plugged in algorithms in a black box fashion. Finally, we give positive and negative results for multivariate convex functions. (C) 2014 Elsevier B.V. All rights reserved.