Back to papers

A Bouquet of Results on Maximum Range Sum: General Techniques and Hardness Reductions

Summary: Revisits MaxRS for d-balls and gives three main results: (i) first dynamic MaxRS with randomized (1/2−ε)-approx and O_ε(log n) updates; (ii) Ω(mn) conditional lower bound for batched 1D via (min,+)-convolution; (iii) colored MaxRS algorithms: randomized (1/2−ε) in R^d and (1−ε) in R^2, both O_ε(n log n). Techniques: a volume-based randomized game yields (1/2−ε) approximations, and an output-sensitive exact algorithm plus color-sampling yields (1−ε); reductions give near-tight lower bounds. (summarized by gpt-5-mini on Feb 11 2026)

Paper ID

1989

Venue

PODS

Year

2026

Pagerank

4.1945683e-05

Overall Rank

10,000 | 30.44%

DOI

10.1145/3767709