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

DOI10.1016/j.disopt.2014.12.001zbMath1387.90268OpenAlexW1989834081MaRDI QIDQ1751103

Nir Halman

Publication date: 24 May 2018

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2014.12.001

zbMATH Keywords

dynamic programmingapproximate binary searchproperty preserving reconstruction

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39) Approximation with constraints (41A29) Convexity of real functions in one variable, generalizations (26A51) Approximation algorithms (68W25)

Related Items (3)

Toward Breaking the Curse of Dimensionality: An FPTAS for Stochastic Dynamic Programs with Multidimensional Actions and Scalar States ⋮ Provably Near-Optimal Approximation Schemes for Implicit Stochastic and Sample-Based Dynamic Programs ⋮ A faster FPTAS for counting two-rowed contingency tables

Cites Work

• Unnamed Item
• Property-preserving data reconstruction
• Dynamic Programming Models and Algorithms for the Mutual Fund Cash Balance Problem
• Discrete Convex Analysis
• Fixed-Dimensional Stochastic Dynamic Programs: An Approximation Scheme and an Inventory Application
• Fully Polynomial Time Approximation Schemes for Stochastic Dynamic Programs
• Approximate Dynamic Programming
• Local Monotonicity Reconstruction
• On Minimizing Nonseparable Functions Defined on the Integers with an Inventory Application
• A Computationally Efficient FPTAS for Convex Stochastic Dynamic Programs

This page was built for publication: Approximating convex functions via non-convex oracles under the relative noise model