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 -