Complexity of Delaying an Adversary's Project; Conference paper

摘要

A 'project manager' wishes to complete a project (e.g., a weapons- development program) as quickly as possible. Using a limited interdiction budget, an 'interdictor' wishes to delay the project's overall completion time by interdicting and thereby delaying some of the project's component tasks. We explore a variety of PERT-based interdiction models for such problems and show that the resulting problem complexities run the gamut: polynomially solvable, weakly NP-complete, strongly NP-complete or NP-hard. We suggest methods for solving the problems that are easier than worst-case complexity implies.