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

DOI10.1145/1007352.1007443MaRDI QIDQ3580951zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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

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

Cited in

(5)

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

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)