Fast Static and Dynamic Approximation Algorithms for Geometric Optimization Problems: Piercing, Independent Set, Vertex Cover, and Matching.
Sujoy BhoreTimothy M. ChanPublished in: CoRR (2024)
Keyphrases
- vertex cover
- approximation algorithms
- independent set
- optimization problems
- maximum weight
- np hard
- special case
- partial order
- evolutionary algorithm
- worst case
- metaheuristic
- minimum cost
- precedence constraints
- constant factor
- approximation ratio
- primal dual
- objective function
- polynomial time approximation
- bipartite graph
- lower bound