On sums of independent random variables with unbounded variance, and estimating the average degree in a graph

DOI10.1145/1007352.1007443zbMATH Open1192.60021OpenAlexW2121707217MaRDI QIDQ3580951FDOQ3580951

Authors: Uriel Feige 

Publication date: 15 August 2010

Published in: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1007352.1007443

Recommendations

• On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a Graph
• scientific article; zbMATH DE number 7204459
• Sublinear time estimation of degree distribution moments: the arboricity connection
• Approximating Average Parameters of Graphs
• Approximating average parameters of graphs

Mathematics Subject Classification ID

Approximation algorithms (68W25) Combinatorial probability (60C05) Vertex degrees (05C07)

Cited In (5)

• Comparing node degrees in probabilistic networks
• Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
• A sublinear-time approximation scheme for bin packing
• Edge-statistics on large graphs
• A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling

This page was built for publication: On sums of independent random variables with unbounded variance, and estimating the average degree in a graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3580951)