TY - GEN

T1 - Piecewise-linear approximations of uncertain functions

AU - Abam, M.A.

AU - Berg, de, M.T.

AU - Khosravi Dehkordi, A.

PY - 2011

Y1 - 2011

N2 - 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) .

AB - 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) .

U2 - 10.1007/978-3-642-22300-6_1

DO - 10.1007/978-3-642-22300-6_1

M3 - Conference contribution

SN - 978-3-642-22299-3

T3 - Lecture Notes in Computer Science

SP - 1

EP - 12

BT - Algorithms and Data Structures (12th International Workshop, WADS 2011, Brooklyn NY, USA, August 15-17, 2011. Proceedings)

A2 - Dehne, F.

A2 - Iacono, J.

A2 - Sack, J.R.

PB - Springer

CY - Berlin

ER -