%0 Conference Paper
%B 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS)
%D 2011
%T Maximizing Expected Utility for Stochastic Combinatorial Optimization Problems
%A Li,Jian
%A Deshpande, Amol
%K Approximation algorithms
%K Approximation methods
%K combinatorial problems
%K Fourier series
%K knapsack problems
%K optimisation
%K OPTIMIZATION
%K polynomial approximation
%K polynomial time approximation algorithm
%K Polynomials
%K Random variables
%K stochastic combinatorial optimization
%K stochastic knapsack
%K stochastic shortest path
%K stochastic spanning tree
%K vectors
%X 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 ϵ for any ϵ >; 0, 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.
%B 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS)
%I IEEE
%P 797 - 806
%8 2011/10/22/25
%@ 978-1-4577-1843-4
%G eng
%R 10.1109/FOCS.2011.33
%0 Journal Article
%J The Journal of the Acoustical Society of America
%D 2010
%T Insights into head-related transfer function: Spatial dimensionality and continuous representation
%A Zhang,Wen
%A Abhayapala,Thushara D.
%A Kennedy,Rodney A.
%A Duraiswami, Ramani
%K acoustic signal processing
%K Bessel functions
%K Fourier series
%K hearing
%K Transfer functions
%X This paper studies head-related transfer function (HRTF) sampling and synthesis in a three-dimensional auditory scene based on a general modal decomposition of the HRTF in all frequency-range-angle domains. The main finding is that the HRTF decomposition with the derived spatial basis function modes can be well approximated by a finite number, which is defined as the spatial dimensionality of the HRTF. The dimensionality determines the minimum number of parameters to represent the HRTF corresponding to all directions and also the required spatial resolution in HRTF measurement. The general model is further developed to a continuous HRTF representation, in which the normalized spatial modes can achieve HRTF near-field and far-field representations in one formulation. The remaining HRTF spectral components are compactly represented using a Fourier spherical Bessel series, where the aim is to generate the HRTF with much higher spectral resolution in fewer parameters from typical measurements, which usually have limited spectral resolution constrained by sampling conditions. A low-computation algorithm is developed to obtain the model coefficients from the existing measurements. The HRTF synthesis using the proposed model is validated by three sets of data: (i) synthetic HRTFs from the spherical head model, (ii) the MIT KEMAR (Knowles Electronics Mannequin for Acoustics Research) data, and (iii) 45-subject CIPIC HRTF measurements.
%B The Journal of the Acoustical Society of America
%V 127
%P 2347 - 2357
%8 2010///
%G eng
%U http://link.aip.org/link/?JAS/127/2347/1
%N 4
%R 10.1121/1.3336399