The -digraph optimization problem and the greedy algorithm |
| |
Authors: | David Hartvigsen |
| |
Affiliation: | Mendoza College of Business, University of Notre Dame, Notre Dame, IN 46556-5646, USA |
| |
Abstract: | In this paper we present a new optimization problem and a general class of objective functions for this problem. We show that optimal solutions to this problem with these objective functions are found with a simple greedy algorithm. Special cases include matroids, Huffman's data compression problem, a special class of greedoids, a special class of min cost max flow problems (related to Monge sequences), a special class of weighted f-factor problems, and some new problems. |
| |
Keywords: | Greedy algorithm Matroids Huffman codes Data compression |
本文献已被 ScienceDirect 等数据库收录! |
|