How to Catch Marathon Cheaters: New Approximation Algorithms for Tracking Paths.

Michael T. Goodrich Siddharth Gupta Hadi Khodabandeh Pedro Matias

Published in: WADS (2021)

Keyphrases

approximation algorithms
disjoint paths
np hard
special case
facility location problem
minimum cost

vertex cover
worst case
exact algorithms
approximation ratio
network design problem
set cover

np hardness
randomized algorithms
particle filter
primal dual
shortest path
constant factor

constant factor approximation
undirected graph
approximation schemes
open shop
linear programming