Lower Bounds for Approximating Graph Parameters via Communication Complexity.
Talya EdenWill RosenbaumPublished in: APPROX-RANDOM (2018)
Keyphrases
- lower bound
- upper bound
- worst case
- objective function
- maximum likelihood
- graph theory
- parameter values
- min sum
- communication systems
- structured data
- branch and bound algorithm
- np hard
- graph cuts
- random walk
- parameter space
- communication networks
- computational complexity
- graph structure
- optimal solution
- directed acyclic graph
- graph representation
- image segmentation