Job assignments An employer wishes to fill i vacancies with pretrained skilled labour. An employment agency provides a list of j potential employees, each having been trained for one or more of the...

1. 
   

   
   Job assignments
   

   
   

An employer wishes to fill i vacancies with pretrained skilled labour. An employment agency provides a list of j potential employees, each having been trained for one or more of the vacancies. Using Hall's theorem (exercise 5.3) how might the prospects of:

1. 
   

   
   filling all the vacancies, and
   

   
   


2. 
   

   
   employing all the candidates, be judged?
   

   
   

Does Hall's theorem provide an efficient way to answer these questions? How might a maximum number of vacancies be filled in polynomial time?