Sublinear Algorithms and Lower Bounds for Estimating MST and TSP Cost in General Metrics.

Yu Chen Sanjeev Khanna Zihan Tan

Published in: ICALP (2023)

Keyphrases

lower bound
computational cost
optimization problems
upper bound
upper and lower bounds
objective function
optimal solution
computational complexity
learning algorithm
significant improvement
special case
worst case
memory efficient
lower and upper bounds
computationally efficient
np hard
search space