Worst Case Analysis of Greedy Heuristics for Integer Programming with Non-Negative Data.
STANFORD UNIV CA SYSTEMS OPTIMIZATION LAB
Pagination or Media Count:
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
- Theoretical Mathematics