Near-Quadratic Lower Bounds for Two-Pass Graph Streaming Algorithms.
Sepehr AssadiRan RazPublished in: CoRR (2020)
Keyphrases
- lower bound
- graph theory
- objective function
- learning algorithm
- computational complexity
- depth first search
- maximum weight
- theoretical analysis
- optimization problems
- data structure
- np complete
- random walk
- worst case
- combinatorial optimization
- pairwise
- lower and upper bounds
- search algorithm
- graph search
- online algorithms