Relative Approximation Bounds for NP-Complete Optimization Problems

Abstract

IDA Paper P-2347, Relative Approximation Bounds for NP-Complete Optimization Problems, documents a new method for determining lower bounds on the relative accuracy attainable for polynomial-time approximations to certain restricted types of NP-Complete optimization problems. These problems are the bounded optimizations, NP constrained optimizations, and optimizations. The initial tasking was to investigate up to three promising areas in Complexity Theory. The first area involved developing new separation results for Krentel's OptP classification of NP optimization problems. The second area was to examine the possible extension of Krentel's absolute error bounds for NP approximations to relative error bounds, while the third area involved examination of the EP theory of parallel algorithms by Kruskal, Randolph, and Snir. However, time did not permit investigation of the third area.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Mar 01, 1990
Accession Number
ADA236570

Entities

People

  • Kevin J. Rappoport

Organizations

  • Institute for Defense Analyses

Tags

DTIC Thesaurus Topics

  • Accuracy
  • Algorithms
  • Automata
  • Classification
  • Computer Science
  • Governments
  • Maryland
  • Mathematical Analysis
  • New York
  • Notation
  • Simulations
  • Software Development
  • Standards
  • Theoretical Computer Science
  • United States
  • Weighting Functions
  • Yield

Readers

  • Operations Research
  • Regression Analysis.