Accession Number:

ADA093618

Title:

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

Descriptive Note:

Technical rept.,

Corporate Author:

STANFORD UNIV CA SYSTEMS OPTIMIZATION LAB

Personal Author(s):

Report Date:

1980-10-01

Pagination or Media Count:

27.0

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

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE