Approximation Algorithms for Covering Vertices by Long Paths.
Mingyang GongBrett EdgarJing FanGuohui LinEiji MiyanoPublished in: Algorithmica (2024)
Keyphrases
- approximation algorithms
- disjoint paths
- undirected graph
- np hard
- special case
- worst case
- facility location problem
- minimum cost
- network design problem
- vertex cover
- exact algorithms
- open shop
- approximation ratio
- approximation schemes
- np hardness
- shortest path
- primal dual
- set cover
- randomized algorithms
- lower bound
- approximation guarantees
- precedence constraints
- combinatorial auctions
- random walk
- mathematical model