Min-Max Latency Walks: Approximation Algorithms for Monitoring Vertex-Weighted Graphs.
Soroush AlamdariElaheh FataStephen L. SmithPublished in: WAFR (2012)
Keyphrases
- approximation algorithms
- min max
- weighted graph
- minimum weight
- undirected graph
- edge weights
- vertex set
- np hard
- special case
- vertex cover
- minimum cost
- shortest path
- worst case
- graph model
- graph partitioning
- discrete data
- regularization framework
- primal dual
- set cover
- data objects
- graph structure
- open shop
- spanning tree
- randomized algorithms
- approximation guarantees
- approximation ratio
- disjoint paths