DocumentCode
1964461
Title
A New Probability Inequality Using Typical Moments and Concentration Results
Author
Kannan, Ravindran
Author_Institution
Microsoft Res. Labs., India
fYear
2009
fDate
25-27 Oct. 2009
Firstpage
211
Lastpage
220
Abstract
We present two probability inequalities. The simpler first inequality weakens both hypotheses in Hoffding-Azumaine quality. Using it, we generalize concentration results previously known for the uniform density for the TSP, MWST and Random Projections to long-tailed inhomogeneous distributions. The second more complicated inequality further weakens the moment requirements and using it, we prove the best possible concentration for the long-studied bin packing problem as well as some others.
Keywords
bin packing; probability; Hoffding-Azuma inequality; bin packing problem; concentration results; long-tailed inhomogeneous distributions; probability inequality; typical moments; Algorithm design and analysis; Computer science; Data analysis; Gaussian distribution; Probability distribution; Random variables; Stochastic processes; Tail; Tree graphs; Concentration; Long-tailed distributions; Probability Inequality;
fLanguage
English
Publisher
ieee
Conference_Titel
Foundations of Computer Science, 2009. FOCS '09. 50th Annual IEEE Symposium on
Conference_Location
Atlanta, GA
ISSN
0272-5428
Print_ISBN
978-1-4244-5116-6
Type
conf
DOI
10.1109/FOCS.2009.20
Filename
5438630
Link To Document