Optimal Multi-Pass Lower Bounds for MST in Dynamic Streams.

Sepehr Assadi Gillat Kol Zhijun Zhang

Published in: Electron. Colloquium Comput. Complex. (2023)

Keyphrases

lower bound
optimal cost
upper bound
optimal solution
dynamic environments
worst case
objective function
dynamic programming
constant factor
np hard
data streams
real time
competitive ratio
branch and bound algorithm
upper and lower bounds
asymptotically optimal
quadratic assignment problem
neural network