Improved streaming algorithm for the Klee's measure problem and generalizations

DOI10.4230/LIPICS.APPROX/RANDOM.2024.26MaRDI QIDQ6920817zbMATH OpenFDO

Authors Mridul Nandi, N. V. Vinodchandran, Arijit Ghosh, Kuldeep S. Meel, Soumit Pal, Sourav Chakraborty

Publication date 6 October 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.APPROX/RANDOM.2024.26

zbMATH Keywords

Klee's measure problemsamplingstreaming

Mathematics Subject Classification ID

Randomized algorithms (68W20) Approximation algorithms (68W25) Combinatorial optimization (90C27)

Cites work

• A (slightly) faster algorithm for Klee's measure problem
• Approximating the volume of unions and intersections of high-dimensional geometric objects
• Automata, logics, and infinite games. A guide to current research
• Can the Measure of ∪ n 1 [ a i , b i ] be Computed in Less Than O(n logn) Steps?
• scientific article; zbMATH DE number 1302378 (Why is no real title available?)
• scientific article; zbMATH DE number 2019620 (Why is no real title available?)
• scientific article; zbMATH DE number 7278047 (Why is no real title available?)
• New Upper Bounds in Klee’s Measure Problem
• On the complexity of computing the measure of ∪[a _i ,b _i ]
• Probabilistic counting algorithms for data base applications
• Probability and computing. Randomization and probabilistic techniques in algorithms and data analysis
• Range‐Efficient Counting of Distinct Elements in a Massive Data Stream
• The space complexity of approximating the frequency moments
• Time-space tradeoffs for counting NP solutions modulo integers
• Two improved range-efficient algorithms for \(F_0\) estimation
• Universal classes of hash functions

This page was built for publication: Improved streaming algorithm for the Klee's measure problem and generalizations

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