Worst Case Analysis of Greedy Heuristics for Integer Programming with Non-Negative Data.

Abstract

We give a worst case analysis for two greedy heuristics for the integer programming problem minimize cx, Ax > or = b, O < or = x < or = u, x integer, where the entries A, b, and c are all non-negative. The first heuristic is for the case where the entries in A and b are integral, the second only assumes the rows are scaled so that the smallest nonzero entry is at least 1. In both cases we compare the ratio of the value of the greedy solution to that of the integer optimal. The error bound grows logarithmically in the maximum column sum of A for both heuristics. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Oct 01, 1980
Accession Number
ADA093618

Entities

People

  • Greg Dobson

Organizations

  • Stanford University

Tags

Communities of Interest

  • C4I

DTIC Thesaurus Topics

  • Algorithms
  • Computer Programming
  • Coverings
  • Error Analysis
  • Errors
  • Inequalities
  • Integer Programming
  • Integrals
  • Intervals
  • Iterations
  • Military Research
  • Notation
  • Operations Research
  • Optimization
  • Polynomials
  • United States
  • United States Government

Fields of Study

  • Computer science
  • Mathematics

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Approximation Theory.
  • Linear Algebra