Linear-Time Approximation Algorithms for Unit Disk Graphs.
Guilherme Dias da FonsecaVinícius Gusmão Pereira de SáCelina M. H. de FigueiredoPublished in: WAOA (2014)
Keyphrases
- approximation algorithms
- worst case
- undirected graph
- np hard
- special case
- facility location problem
- vertex cover
- approximation guarantees
- minimum cost
- upper bound
- np hardness
- network design problem
- open shop
- lower bound
- set cover
- exact algorithms
- constant factor
- primal dual
- approximation ratio
- weighted graph
- graph matching
- precedence constraints
- randomized algorithms
- graph structure
- approximation schemes
- partial order