𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A greedy algorithm for some classes of integer programs

✍ Scribed by V.V. Shenmaier

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
144 KB
Volume
133
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

✦ Synopsis

We establish a necessary and su cient condition for a greedy algorithm to ΓΏnd an optimal solution in the case of integer programs with separable concave objective functions. This extends some well-known results for spanning trees, matroids, and greedoids. As a corollary we obtain one new generalization of matroids and integer polymatroids preserving the optimality of greedy solutions. ?

πŸ“œ SIMILAR VOLUMES

An enumerative algorithm framework for a
An enumerative algorithm framework for a class of nonlinear integer programming problems
✍ Mohamed Djerdjour πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 763 KB

This paper presents a framework for a branch and search algorithm for solving a class of general integer restricted, linearly constrained, quadratic integer programming problems where the objective function is a nonseparable quadratic concave function.

An analysis of six greedy selection rule
An analysis of six greedy selection rules on a class of zero-one integer programming models
✍ G. Edward Fox; Christopher J. Nachtsheim πŸ“‚ Article πŸ“… 1990 πŸ› John Wiley and Sons 🌐 English βš– 509 KB

Six greedy primal selection rules are evaluated on a class of generalized set packing models. The evaluation is conducted in accordance with experimental design methodologies proposed by Lin and Rardin. Results indicate that the simplest of rules performs best, except when the model constraints exhi