2005 | OriginalPaper | Buchkapitel
On the Complexity of Delaying an Adversary’s Project
verfasst von : Gerald G. Brown, W. Matthew Carlyle, Johannes O. Royset, R. Kevin Wood
Erschienen in: The Next Wave in Computing, Optimization, and Decision Technologies
Verlag: Springer US
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.