Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic Independence.
Nima AnariYang P. LiuThuy-Duong VuongPublished in: FOCS (2022)
Keyphrases
- point processes
- average case
- worst case
- spanning tree
- monte carlo
- worst case analysis
- competitive ratio
- hot spots
- minimum cost
- uniform distribution
- edge disjoint
- learning curves
- approximation algorithms
- spatial analysis
- minimum spanning tree
- lower bound
- upper bound
- sample size
- particle filter
- decision makers
- dynamic programming
- high dimensional
- computational complexity
- optimal solution