TY - CONF
T1 - Maximizing Expected Utility for Stochastic Combinatorial Optimization Problems
T2 - 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS)
Y1 - 2011
A1 - Li,Jian
A1 - Deshpande, Amol
KW - Approximation algorithms
KW - Approximation methods
KW - combinatorial problems
KW - Fourier series
KW - knapsack problems
KW - optimisation
KW - OPTIMIZATION
KW - polynomial approximation
KW - polynomial time approximation algorithm
KW - Polynomials
KW - Random variables
KW - stochastic combinatorial optimization
KW - stochastic knapsack
KW - stochastic shortest path
KW - stochastic spanning tree
KW - vectors
AB - 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.
JA - 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS)
PB - IEEE
SN - 978-1-4577-1843-4
M3 - 10.1109/FOCS.2011.33
ER -
TY - JOUR
T1 - Insights into head-related transfer function: Spatial dimensionality and continuous representation
JF - The Journal of the Acoustical Society of America
Y1 - 2010
A1 - Zhang,Wen
A1 - Abhayapala,Thushara D.
A1 - Kennedy,Rodney A.
A1 - Duraiswami, Ramani
KW - acoustic signal processing
KW - Bessel functions
KW - Fourier series
KW - hearing
KW - Transfer functions
AB - 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.
VL - 127
UR - http://link.aip.org/link/?JAS/127/2347/1
CP - 4
M3 - 10.1121/1.3336399
ER -