Some recent results in the analysis of greedy algorithms for assignment problems |
| |
Authors: | Ulrich Faigle |
| |
Affiliation: | (1) Department of Applied Mathematics, University of Twente, P.O. Box 217, 7500 AE Enschede, The Netherlands |
| |
Abstract: | We survey some recent developments in the analysis of greedy algorithms for assignment and transportation problems. We focus on the linear programming model for matroids and linear assignment problems with Monge property, on general linear programs, probabilistic analysis for linear assignment and makespan minimization, and on-line algorithms for linear and non-linear assignment problems.This is an expanded version of a survey lecture presented at the DGOR/NSOR Symposium, Amsterdam, 1993 |
| |
Keywords: | Greedy algorithms assignment problems Monge property job scheduling |
本文献已被 SpringerLink 等数据库收录! |
|