OPTIMAL ASSIGNMENTS IN AN ORDERED SET; AN APPLICATION OF MATROID THEORY

Abstract

A certain set of jobs has been arranged in order of importance by some priority system and it is desired to fill the jobs from a pool of workers where each worker is qualified for some subset of the jobs. In general, it will not be possible to fill all of the jobs and the problem is therefore to choose the set of jobs to be filled in some optimal way. Roughly speaking, given all possible assignable sets of jobs one wishes to choose the one with 'highest priority.' It is not clear, however, what this means as, for example, if the choice were between filling jobs 1, 4, 6 or 2, 3, 4, 5. The purpose of this note is to show that, in fact, there always does exist a 'best' assignment.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Feb 01, 1967
Accession Number
AD0648715

Entities

People

  • David Gale

Organizations

  • University of California, Berkeley

Tags

DTIC Thesaurus Topics

  • Algorithms
  • California
  • Computational Science
  • Contracts
  • Engineering
  • Governments
  • Interdisciplinary Science
  • Literature
  • Mathematics
  • Military Research
  • Observation
  • Operations Research
  • United States
  • United States Government
  • Universities

Fields of Study

  • Economics

Readers

  • Instructional Design and Training Evaluation.
  • Mathematical Modeling and Probability Theory.
  • Organizational Psychology.