Optimization Online


Approximating Convex Functions By Non-Convex Oracles Under The Relative Noise Model

Nir Halman (halman***at***huji.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 L-approximation 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) L-approximation 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 Non-Convex Oracles Under The Relative Noise Model, Discrete Optimization 16, pp. 1-16, 2015.


Entry Submitted: 02/02/2014
Entry Accepted: 02/02/2014
Entry Last Modified: 06/08/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society