  


Approximating Convex Functions By NonConvex Oracles Under The Relative Noise Model
Nir Halman (halmanhuji.ac.il) Abstract: We study succinct approximation of functions that have noisy oracle access. Namely, construction of a succinct representation of a function, given oracle access to an Lapproximation of the function, rather than to the function itself. Specifically, we consider the question of the succinct representation of an approximation of a convex function v that cannot be accessed directly, but only via oracle calls to a general (i.e., not necessarily convex) Lapproximation v' of v. We efficiently construct such a succinct ((1+epsilon)L^2)approximation for a univariate convex v, for any epsilon>0. The algorithms designed in this paper can, and are used as subroutines (gadgets) within other approximation algorithms. Keywords: Approximation schemes, discrete convexity Category 1: Combinatorial Optimization (Approximation Algorithms ) Citation: Approximating Convex Functions Via NonConvex Oracles Under The Relative Noise Model, Discrete Optimization 16, pp. 116, 2015. Download: Entry Submitted: 02/02/2014 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  