Functions for Measuring the Quality of Approximate Solutions to Zero-One Programming Problems.

Abstract

The difficulties associated with measuring the are defined of an approximate (heuristic) solution by 'Percentage-Error' as is customary are pointed out. A set of properties that are to be expected from a proper measure of solution quality are defined and the family of functions which satisfy those conditions are investigated. In particular, it is shown that for any class of 0-1 programming problems appropriate functions do exist and that they are uniquely defined up to monotone transformations. Several examples of linear functions which are suitable for certain classes of problems are included.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 1978
Accession Number
ADA060651

Entities

People

  • Eitan Zemel

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Energy and Power Technologies
  • Human Systems

DTIC Thesaurus Topics

  • Algorithms
  • British Columbia
  • Computational Complexity
  • Computer Programming
  • Construction
  • Errors
  • Monotone Functions
  • Notation
  • Optimization
  • Pennsylvania
  • Permutations
  • Schools
  • Sequences
  • Students
  • Transportation
  • Universities

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.
  • Systems Analysis and Design