# Piecewise-linear approximations of uncertain functions

M.A. Abam, M.T. Berg, de, A. Khosravi Dehkordi

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

2 Citations (Scopus)

## Abstract

We study the problem of approximating a function F: R¿¿¿R by a piecewise-linear function [`(F)]F when the values of F at {x 1,…,x n } are given by a discrete probability distribution. Thus, for each x i we are given a discrete set yi,1,...,yi,miyi1yimi of possible function values with associated probabilities p i,j such that Pr[F(x i )¿=¿y i,j ]¿=¿p i,j . We define the error of [`(F)]F as error(F,[`(F)]) = maxi=1n E[|F(xi)-[`(F)](xi)|]\sl error(FF)=maxni=1E[F(xi)-F(xi)]. Let m=åi=1n mim=ni=1mi be the total number of potential values over all F(x i ). We obtain the following two results: (i) an O(m) algorithm that, given F and a maximum error e, computes a function [`(F)]F with the minimum number of links such that error(F,[`(F)]) £ e\sl error(FF) ; (ii) an O(n 4/3¿+¿d ¿+¿mlogn) algorithm that, given F, an integer value 1¿=¿k¿=¿n and any d¿>¿0, computes a function [`(F)]F of at most k links that minimizes error(F,[`(F)])\sl error(FF) .
Original language English Algorithms and Data Structures (12th International Workshop, WADS 2011, Brooklyn NY, USA, August 15-17, 2011. Proceedings) F. Dehne, J. Iacono, J.R. Sack Berlin Springer 1-12 978-3-642-22299-3 https://doi.org/10.1007/978-3-642-22300-6_1 Published - 2011

### Publication series

Name Lecture Notes in Computer Science 6844 0302-9743

## Fingerprint

Dive into the research topics of 'Piecewise-linear approximations of uncertain functions'. Together they form a unique fingerprint.