On the Complexity of Delaying an Adversary's Project

Abstract

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 2005
Accession Number
ADA486934

Entities

People

  • Gerald G. Jerry Brown
  • Johannes Royset
  • R. Kevin Wood
  • W. M. Carlyle

Organizations

  • Naval Postgraduate School

Tags

Communities of Interest

  • Counter WMD
  • Energy and Power Technologies
  • Weapons Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Arms Control
  • Computational Complexity
  • Computer Programming
  • Dynamic Programming
  • Interdiction
  • Linear Programming
  • Mathematical Models
  • Models
  • New York
  • Nuclear Weapons
  • Operations Research
  • Optimization
  • Pert
  • Polynomials
  • Standards
  • Weapons

Fields of Study

  • Computer science

Readers

  • Mathematics or Statistics
  • Operations Research
  • Systems Analysis and Design