On The Complexity of Delaying an Adversary's Project
Author
Brown, Gerald G.
Carlyle, Matthew W.
Royset, Johannes
Wood, Kevin
Date
2005Metadata
Show full item recordAbstract
A "project manager" wises to complete a project (e.g., a weapons-development program) as quickly as possible. Using a limited interdiction budget, as "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 the worst-case complexity implies.
Description
in The Next Wave in Computing, Optimization and Decision Technologies, B. Golden, S. Raghavan and E.Wasil, eds., Springer, New York, pp. 3-17.
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.Collections
Related items
Showing items related by title, author, creator and subject.
-
On The Complexity of Delaying an Adversary's Project
Brown, G.; Carlyle, M.; Royset, J.; Wood, K. (2005);A “project manager” wishes to complete a project (e.g., a weapons- development program) as quickly as possible. Using a limited interdic- tion budget, an “interdictor” wishes to delay the project’s overall com- pletion ... -
Anatomy of a Project to Produce a First Nuclear Weapon
Brown, G.; Carlyle M.; Harney R.; Skroch E.; Wood, K. (2006);We describe the industrial project that a "proliferator" would conduct to produce a first, small bach of nuclear weapons. From refining yellowcake ore to final weapons assembly, we highlight the project's tasks and their ... -
Anatomy of a Project to Produce a First Nuclear Weapon
Brown, G.; Carlyle, M.; Harney, R.; Skroch, E.; Wood, K. (2006);We describe the industrial project that a “proliferator” would conduct to produce a first, small batch of nuclear weapons. From refining yellowcake ore to final weapons assem- bly, we highlight the project’s tasks and their ...