2026· International Colloquium on Automata, Languages and Programming· pp. 34:1-34:21· 0 citations· 29 references
Computer Science
TL;DR
This approach integrates a classic grid-based partition framework with a novel charging analysis that controls the cost of structure-sensitive offline routines within each cell, to perform a global aggregation of the update time, by circumventing the worst-case costs associated with individual cell updates.
A polynomial-time approximation algorithm with approximation factor strictly better than $1-1/e$ for any set system with linear 2-shallow cell complexity and any set system that can be decomposed into a constant number of such set systems is presented.
S. Bhore, Timothy M. Chan, Pasin Manurangsi· arXiv.org· 0 citations
This paper provides a tight reduction demonstrating that any exact distance sensitivity oracle can be used to efficiently solve decremental exact diameter and all-node eccentricities and introduces two new instructive techniques and demonstrates how to utilize them to construct several new algorithms.
Sam Hiken, Yael Kirkpatrick, Jakob Nogler et al.· 0 citations
The main contribution is giving an essentially matching lower bound on the space complexity of diameter estimation for a set of points in Euclidean space in the dynamic (turnstile) streaming model.
Ashwin Padaki, Krish Singal, Erik Waingarten· 0 citations
PAWC is proposed: an exact $O(N\log N)$ time, $O(N)$ memory algorithm returning all $K+1$ costs, nested active sets and plans in one run, together with a single gap that is simultaneously optimal for every cardinality.
A dynamic-threshold algorithm (DTA) is developed for a continuous quadratic knapsack problem with a weighted equality constraint that maintains a threshold invariant through three operations--addition, reset, and removal--and its finite termination and correctness are established.
An exact transcript-cone game yields one uniform interpreter whose charged addition-comparison cost equals one uniform interpreter whose optimal actions are synthesizable in polynomial space but may require exponential time.
Bin Cai· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
