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)


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 languageEnglish
Title of host publicationAlgorithms and Data Structures (12th International Workshop, WADS 2011, Brooklyn NY, USA, August 15-17, 2011. Proceedings)
EditorsF. Dehne, J. Iacono, J.R. Sack
Place of PublicationBerlin
ISBN (Print)978-3-642-22299-3
Publication statusPublished - 2011

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743


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

Cite this