Exact and Approximation Algorithms for Routing a Convoy Through a Graph.
Martijn van EeTim OosterwijkRené SittersAndreas WiesePublished in: MFCS (2023)
Keyphrases
- approximation algorithms
- undirected graph
- np hard
- moving object trajectories
- disjoint paths
- constant factor
- special case
- worst case
- vertex cover
- minimum cost
- facility location problem
- randomized algorithms
- graph structure
- approximation ratio
- primal dual
- set cover
- directed graph
- random walk
- spanning tree
- open shop
- precedence constraints
- approximation schemes
- weighted graph
- approximation guarantees
- exact solution
- shortest path
- combinatorial auctions
- search algorithm