On The Complexity of Delaying an Adversary's Project
Brown, Gerald G.
Carlyle, Matthew W.
MetadataShow full item record
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.
in The Next Wave in Computing, Optimization and Decision Technologies, B. Golden, S. Raghavan and E.Wasil, eds., Springer, New York, pp. 3-17.
RightsThis 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.
Showing items related by title, author, creator and subject.
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 ...
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 ...
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 ...