Problem

edit

Let us have the following eight panel sessions:

  • Institutional and Media Outreach (short: Outreachр O)
  • Volunteer Support (short: Volunteer, V)
  • Low-cost Project (short: Low-cost, L)
  • Cross-border Cooperation (short: Cross-border, C)
  • Gender Gap (short: Gender, G)
  • Wiki Events (short: Wiki Events, W)
  • Technical Tools (short: Tools, T)
  • Wiki Education Programme (short: Education, E)

Let us have the following 13 speakers, having 2+ roles as speakers or moderators in different panel sessions:

  • Anna in "Education" and "Gender"
  • Asaf in "Gender", "Volunteer" and "Low-cost"
  • Bojan in "Outreach" and "Events"
  • David in "Education" and "Tools"
  • Greta in "Events" and "Gender"
  • Ivo in "Tools" and "Low-cost"
  • Krzysztof in "Education" and "Outreach"
  • Levon in "Events" and "Cross-border"
  • Marek in "Tools" and "Low-cost"
  • Marios in "Education" and "Cross-border"
  • Milica in "Volunteer" and "Low-cost"
  • Natalia - in "Volunteer" and "Outreach"
  • Vassia - in "Education", "Outreach" and "Low-cost"

These eight sessions need to be placed in the programme in pairs, so that the people do not have their commitments in sessions that are scheduled in parallel, the so-called Bilocation Problem. Let us suppose that all eight sessions are of equal length.

Approach

edit

1. Prepare a table 8×8, labelled with the eight panel sessions.

O V L C G W T E
O
V
L
C
G
W
T
E


2. The cells according to the main diagonal are cancelled, as you cannot have the same session running in parallel with itself. Let us mark them with dark grey and the sign "X".

O V L C G W T E
O X
V X
L X
C X
G X
W X
T X
E X


3. The two triangles that are thus formed are practically identical. Let us cancel the cells above the main diagonal and only concentrate on the lower triangle. It contains 28 cells, which is (8*7)/2. In the general case of n sessions, this number will be (n*(n-1))/2.

O V L C G W T E
O X X X X X X X X
V X X X X X X X
L X X X X X X
C X X X X X
G X X X X
W X X X
T X X
E X


4. The cells that correspond to speakers in two sessions need to be cancelled, too, meaning that these two sessions cannot happen in parallel. Let us mark them with red and the name of the speaker.

4.1. In case of speaker in two sessions A and B, we have one cancelled cell (A;B).

O V L C G W T E
O X X X X X X X X
V X X X X X X X
L X X X X X X
C X X X X X
G X X X X
W X X X
T X X
E Anna X


4.2. In case of speaker in three sessions A, B and C, we have three cancelled cells (A;B), (A;C) and (B;C).

O V L C G W T E
O X X X X X X X X
V X X X X X X X
L Asaf X X X X X X
C X X X X X
G Asaf Asaf X X X X
W X X X
T X X
E Anna X


4.3. Proceed with the rest names from the list.

O V L C G W T E
O X X X X X X X X
V Natalia X X X X X X X
L Vassia Asaf, Milica X X X X X X
C X X X X X
G Asaf Asaf X X X X
W Bojan Levon Greta X X X
T Ivo, Marek X X
E Krzysztof, Vassia Vassia Marios Anna David X


5. What remains as empty cells can contain the possible solutions of the problem. We need to form 4 pairs from the 8 sessions. This means that if we confirm one pair (A,B) (green "V"), we will have to cancel all the other pairs (A,C), (A,D), (A,E) ... and (C,B), (D,B), (E,B)... (red "X"-s).

O V L C G W T E
O X X X X X X X X
V Natalia X X X X X X X
L Vassia Asaf, Milica X X X X X X
C X X V X X X X X
G Asaf Asaf X X X X X
W Bojan X Levon Greta X X X
T Ivo, Marek X X X
E Krzysztof, Vassia Vassia Marios Anna David X

We iteratively proceed.

Solutions

edit

In this case we have found three possible solutions.

Solution 1

edit
O V L C G W T E
O X X X X X X X X
V Natalia X X X X X X X
L Vassia Asaf, Milica X X X X X X
C X X V X X X X X
G V Asaf Asaf X X X X X
W Bojan X X Levon Greta X X X
T X V Ivo, Marek X X X X X
E Krzysztof, Vassia X Vassia Marios Anna V David X

Formed pairs:

  • Cross border — Low Cost
  • Gender — Outreach
  • Tools — Volunteers
  • Education — Wiki Events

Solution 2

edit
O V L C G W T E
O X X X X X X X X
V Natalia X X X X X X X
L Vassia Asaf, Milica X X X X X X
C X X X X X X X X
G X Asaf Asaf V X X X X
W Bojan X V Levon Greta X X X
T V X Ivo, Marek X X X X X
E Krzysztof, Vassia V Vassia Marios Anna X David X

Formed pairs:

  • Cross border — Gender
  • Wiki Events — Low-cost
  • Tools — Outreach
  • Education — Volunteers

Solution 3

edit
O V L C G W T E
O X X X X X X X X
V Natalia X X X X X X X
L Vassia Asaf, Milica X X X X X X
C X X X X X X X X
G V Asaf Asaf X X X X X
W Bojan X V Levon Greta X X X
T X X Ivo, Marek V X X X X
E Krzysztof, Vassia V Vassia Marios Anna X David X

Formed pairs:

  • Outreach — Gender
  • Wiki Events — Low-cost
  • Tools — Cross-border
  • Education — Volunteers

Decision

edit
Solution 1
  • Cross border — Low Cost : Problem – both are about projects - but these projects are about different scale and nature.
  • Gender — Outreach : OK
  • Tools — Volunteers : OK
  • Education — Wiki Events : OK
Solution 2
  • Cross border — Gender : OK
  • Wiki Events — Low-cost : OK
  • Tools — Outreach : OK
  • Education — Volunteers : Very problematic - similar groups of people are interested in both.
Solution 3
  • Outreach — Gender : OK
  • Wiki Events — Low-cost : OK
  • Tools — Cross-border : OK
  • Education — Volunteers : Very problematic - similar groups of people are interested in both.
Final decision: Solution 1.