We study the stochastic versions of a broad class of combinatorial problems where the weights of the elements in the input dataset are uncertain. The class of problems that we study includes shortest paths, minimum weight spanning trees, and minimum weight matchings over probabilistic graphs, and other combinatorial problems like knapsack. We observe that the expected value is inadequate in capturing different types of risk-averse or risk-prone behaviors, and instead we consider a more general objective which is to maximize the expected utility of the solution for some given utility function, rather than the expected weight (expected weight becomes a special case). We show that we can obtain a polynomial time approximation algorithm with additive error @math for any @math , if there is a pseudopolynomial time algorithm for the exact version of the problem (This is true for the problems mentioned above)and the maximum value of the utility function is bounded by a constant. Our result generalizes several prior results on stochastic shortest path, stochastic spanning tree, and stochastic knapsack. Our algorithm for utility maximization makes use of the separability of exponential utility and a technique to decompose a general utility function into exponential utility functions, which may be useful in other stochastic optimization problems.
There is a large volume of work on approximating functions using short exponential sums over a bounded domain, e.g., @cite_26 @cite_11 @cite_29 @cite_30 . Some works also consider using linear combinations of Gaussians or other kernels to approximate functions with finite support over the entire real axis @math @cite_35 . This is however impossible using exponentials since @math is either periodic (if @math ) or approaches to infinity when @math or @math (if @math ).
@cite_30 @cite_35 @cite_26 @cite_29 @cite_11
2078691815 2019247511 2081182772 2078132413 2008979617
Abstract We revisit the efficient approximation of functions by sums of exponentials or Gaussians in Beylkin and Monzon (2005) [16] to discuss several new results and applications of these approximations. By using the Poisson summation to discretize integral representations of e.g., power functions r − β , β > 0 , we obtain approximations with uniform relative error on the whole real line. Our approach is applicable to a class of functions and, in particular, yields a separated representation for the function e − x y . As a result, we obtain sharper error estimates and a simpler method to derive trapezoidal-type quadratures valid on finite intervals. We also introduce a new reduction algorithm for the case where our representation has an excessive number of terms with small exponents. As an application of these new estimates, we simplify and improve previous results on separated representations of operators with radial kernels. For any finite but arbitrary accuracy, we obtain new separated representations of solutions of Laplace's equation satisfying boundary conditions on the half-space or the sphere. These representations inherit a multiresolution structure from the Gaussian approximation leading to fast algorithms for the evaluation of the solutions. In the case of the sphere, our approach provides a foundation for a new multiresolution approach to evaluating and estimating models of gravitational potentials used for satellite orbit computations. This textbook is designed for graduate students in mathematics, physics, engineering, and computer science. Its purpose is to guide the reader in exploring contemporary approximation theory. The emphasis is on multi-variable approximation theory, i.e., the approximation of functions in several variables, as opposed to the classical theory of functions in one variable. Most of the topics in the book, heretofore accessible only through research papers, are treated here from the basics to the currently active research, often motivated by practical problems arising in diverse applications such as science, engineering, geophysics, and business and economics. Among these topics are projections, interpolation paradigms, positive definite functions, interpolation theorems of Schoenberg and Micchelli, tomography, artificial neural networks, wavelets, thin-plate splines, box splines, ridge functions, and convolutions. An important and valuable feature of the book is the bibliography of almost 600 items directing the reader to important books and research papers. There are 438 problems and exercises scattered through the book allowing the student reader to get a better understanding of the subject. A modification of the classical technique of Prony for fitting sums of exponential functions to data is considered. The method maximizes the likelihood for the problem (unlike the usual implementation of Prony’s method, which is not even consistent for transient signals), proves to be remarkably effective in practice, and is supported by an asymptotic stability result. Novel features include a discussion of the problem parametrization and its implications for consistency. The asymptotic convergence proofs are made possible by an expression for the algorithm in terms of circulant divided difference operators. Abstract We introduce a new approach, and associated algorithms, for the efficient approximation of functions and sequences by short linear combinations of exponential functions with complex-valued exponents and coefficients. These approximations are obtained for a finite but arbitrary accuracy and typically have significantly fewer terms than Fourier representations. We present several examples of these approximations and discuss applications to fast algorithms. In particular, we show how to obtain a short separated representation (sum of products of one-dimensional functions) of certain multi-dimensional Green's functions. Abstract We introduce new families of Gaussian-type quadratures for weighted integrals of exponential functions and consider their applications to integration and interpolation of bandlimited functions. We use a generalization of a representation theorem due to Caratheodory to derive these quadratures. For each positive measure, the quadratures are parameterized by eigenvalues of the Toeplitz matrix constructed from the trigonometric moments of the measure. For a given accuracy ϵ, selecting an eigenvalue close to ϵ yields an approximate quadrature with that accuracy. To compute its weights and nodes, we present a new fast algorithm. These new quadratures can be used to approximate and integrate bandlimited functions, such as prolate spheroidal wave functions, and essentially bandlimited functions, such as Bessel functions. We also develop, for a given precision, an interpolating basis for bandlimited functions on an interval.