Assignment/allocation matching problems

Questions involving bipartite graphs, adjacency matrices, or tables where people/workers must be matched to tasks/jobs, often with constraints on who can do what, typically solved using matching algorithms or systematic enumeration.

102 questions

Edexcel D1 2016 June Q3
  1. 594518553471183171542
    1. The list of numbers above is to be sorted into descending order. Perform a quick sort to obtain the sorted list. You should show the result of each pass and identify your pivots clearly.
    The numbers in the list represent the lengths, in cm, of some pieces of copper wire. The copper wire is sold in one metre lengths.
  2. Use the first-fit decreasing bin packing algorithm to determine how these pieces could be cut from one metre lengths. (You should ignore wastage due to cutting.)
  3. Determine whether your solution to (b) is optimal. Give a reason for your answer.
Edexcel D1 2004 November Q3
3. Six newspaper reporters Asif (A), Becky (B), Chris (C), David (D), Emma (E) and Fred (F), are to be assigned to six news stories Business (1), Crime (2), Financial (3), Foreign (4), Local (5) and Sport (6). The table shows possible allocations of reporters to news stories. For example, Chris can be assigned to any one of stories 1, 2 or 4.
123456
A\(\checkmark\)
B\(\checkmark\)\(\checkmark\)
C\(\checkmark\)\(\checkmark\)\(\checkmark\)
D\(\checkmark\)
E\(\checkmark\)\(\checkmark\)\(\checkmark\)
F\(\checkmark\)
  1. Show these possible allocations on the bipartite graph on the diagram in the answer book. A possible matching is
    A to 5,
    C to 1 ,
    E to 6,
    F to 4
  2. Show this information, in a distinctive way, on the diagram in the answer book.
    (1)
  3. Use an appropriate algorithm to find a maximal matching. You should list any alternating paths you have used.
  4. Explain why it is not possible to find a complete matching.