2
$\begingroup$

Short summary: The problem is to assign people to meetings at different days while respecting the capacities and (inter-day) constraints of the meetings. Each person can only attend at most one meeting at a day.

I don't know if this problem has a common name - therefore the weird title question, sorry. If I overcomplicated any part of the problem definition, let me know.

People P = $\{p_1, .., p_n\}$, Meeting days D = $\{d_1, .., d_m\}$,

Meetings for each day: $M_{d_1} = \{m_{d_1,1}, .., m_{d_1,a}\}, M_{d_2} = \{m_{d_2,1}, .., m_{d_2,b}\}, .., M_{d_m} = \{m_{d_m,1}, .., m_{d_m,z}\}$
The $M_{d_i}$'s are pairwise disjoint.
Each meeting $m$ can hold a maximum number of people of $\text{cap}_{m}$ (capacity),

A person must not attend two (or more) meetings at different days that are "similar". (These conflicts are only between different days ("inter-day conflicts"). There are no conflicts within a day.)
Therefore define meeting constraints $C=\{c_1,..c_q\}$. Every meeting $m$ has exactly one corresponding constraint $c_i = \text{const}(m)$, s.t. [$\text{const}(m_i) = \text{const}(m_j)$] iff. [$m_i$ is "similar" to $m_j$] for all meetings.

There are preferences which person wants to attend which meeting at a particular day, e.g.:
(here 2 preferences are specified - if we generalize it to a fixed $K$ does the problem get any harder with regards to NP-hardness etc?)
$\text{Prefs} = \{$
$(p_1, \color{red}{d_1}, m_{\color{red}{d_1}, \color{green}{2}}, m_{\color{red}{d_1}, \color{green}{4}}),$ // Person 1 wants to attend the $\color{green}{2nd}$ or $\color{green}{4th}$ meeting at $\color{red}{day 1}$
$(p_1, d_3, m_{d_3, 1}, m_{d_3, 2}),$
$(p_3, d_2, m_{d_2, 2}, m_{d_2, 3}),$
$..$ $\}$, where:
a) every person-day combination $(p_i, d_j, ..)$ appears at most once.
b) every tuple has the form: $(p_i, \color{red}{d_j}, m_{\color{red}{d_j}, a}, m_{\color{red}{d_j}, b})$, with $a \neq b$ ($\widehat{=}$ valid preferences only)
(Note: The meeting preferences for each person-day combination are not supposed to be in any order, so (.., .., $x$, $y$) does not mean $x$ is preferred over $y$.)

A valid solution to the problem is:
Assign each person-day combination $(p_i, d_j, X, Y) \in \text{Prefs} $ to the meeting X or the meeting Y or no meeting at all, s.t.:
a) for every meeting $m$: we don't assign more people to $m$ than its capacity.
b) for every person $p$: for every constraint $c$: the person $p$ is assigned to (at most) one meeting with constraint $c$. (Otherwise, $p$ would attend two meetings at different days that are "similar".)

We want to maximize the number of person-day combinations that are assigned to a meeting. (So minimize the number of person-day combinations that are assigned to no meeting at all.)

Is this problem in $P$? (If yes, what is the idea for a polynomial-time algorithm?)
Is this problem NP-hard? (I tried a reduction from Bin-Packing $\leq_p$ ThisProblem, but without success. I think it's NP-hard and would appreciate any helpful ideas for reductions.)

$\endgroup$
3
  • 3
    $\begingroup$ This should be NP-hard. Try to reduce from graph coloring. $\endgroup$ Sep 3, 2012 at 20:32
  • $\begingroup$ sounds like the "dinner table" problem where people need to be assigned to seats but there are constraints on who can or cannot sit next to each other. roughly, substitute seats for mtgs. alternatively, there are many NP complete scheduling problems that it sounds related to. $\endgroup$
    – vzn
    Sep 5, 2012 at 3:30
  • $\begingroup$ I don't see how I could reduce from graph coloring, because graph coloring seems much harder than the problem stated above. I also looked up the "dinner table" problem, but it seems that it is a completely different problem related to probability theory. $\endgroup$
    – Marc Hoff
    Sep 5, 2012 at 8:53

1 Answer 1

1
$\begingroup$

While my initial instinct was also that the problem should be NP-hard, it looks like it might be close to a problem in P, namely list coloring on graphs whose blocks, or 2-connected components, are cliques. I am not sure to what extent this is helpful, because when you solve the reduced instance all meetings will be filled to capacity, which is an additional constraint on your problem. But if the rest of the argument holds up this might have workarounds, so I will state the partial progress.

If sensible, this reduction does not need to know which day a meeting happens to fall on, so I am using more relaxed notation (dropping the info about which day the meeting was on).

Introduce cap$_m$ vertices $$\{v_m^{(1)}, v_m^{(2)}, \ldots, v_m^{(c_m)}\}$$ for every meeting $m$. Let $M_r$ denote the set of all meetings $m$ that are associated with the constraint $c_r$. the edge set involves a big clique on all vertices involved in representing $m \in M_r$, that is, $$E = \{ (v_p^{(i)},v_q^{(j)}) | p,q \in M_r \}$$ $$\color{red}{\cup \{(v_p^{(i)}, v_q^{(j)})| p, q \text{ are meetings at the same day})\}\text{ [see comment below]} }.$$

The color pallette has one color for every person, and the list asssociated with a meeting vertex is the set of all people for whom the meeting is on their preference list.

A valid list coloring in the graph will fill all meetings to full capacity, and will never assign the same person to similar meetings, and will always give a person a meeting that they wanted to be in.

Some things to note:

  1. The meetings will be filled to capacity, so this is not a completely accurate reduction. The simplest fix is to ask for a partial coloring, but I am not sure about the complexity of this question. One could make the same copies of every meeting an independent set, and add a complete partite structure across meetings with the same constraint. Now, the color corresponding to a person can be repeated within a meeting. However, I am not completely sure that the graph structure now allows for the Ptime algorithm! The other fix would be to introduce junk colors in the pallette, but then some people may not get assigned to meetings at all.

  2. The reduction works with longer preference lists, too.

  3. Conflicts within the same day can also be handled with this modelling.

And this paper mentions that list coloring can be resolved in polynomial time when the blocks of the graph are cliques.

$\endgroup$
5
  • $\begingroup$ First of all, thank you so much for your answer! Correct me if I'm wrong, but shouldn't the edges be $E = \{ (v_p^{(i)},v_q^{(j))} | p,q \in M_r \}\cup \{(v_p^{(i)}, v_q^{(j)}| p, q \text{ are meetings at the same day})\} ?$ (Otherwise, a person could be assigned to two meetings at the same day.) $\endgroup$
    – Marc Hoff
    Sep 6, 2012 at 18:25
  • $\begingroup$ That a valid list coloring will fill all meetings to full capacity is a problem though... Could you explain what you mean by adding junk colors in the pallette? $\endgroup$
    – Marc Hoff
    Sep 6, 2012 at 18:55
  • $\begingroup$ You are right about the edge set, sorry - I missed the same day constraint! And yes, I see that the full capacity thing could be a potential issue. The junk colors proposal was actually somewhat silly, which is why I didn't elaborate :) So let's say you have this extra constraint: no more than $c$ seats in any meeting can be empty. Then if I have $c$ extra colors in my color set, that don't have any semantics - that is, they are not associated with people, then you can use these colors to complete the coloring for one meeting. Having more colors will allow you to account for more meetings... $\endgroup$
    – Neeldhara
    Sep 7, 2012 at 4:32
  • $\begingroup$ ...but sadly if you push that too much, you'll potentially end up with a completely useless coloring :( Worth checking if the graph where you make all copies of a meeting an independent set has a simple enough structure for list coloring to be Ptime. I am sorry this doesn't go all the way! $\endgroup$
    – Neeldhara
    Sep 7, 2012 at 4:32
  • $\begingroup$ "One could make the same copies of every meeting an independent set, and add a complete partite structure across meetings with the same constraint. Now, the color corresponding to a person can be repeated within a meeting." Could you explain what you mean by that? What exactly is supposed to become an independent set? Also, you say that after this transformation a color could be repeated within a meeting, but that would violate one of the constraints specified in the original problem (a person could be assigned to two seats at the same meeting?). $\endgroup$
    – Marc Hoff
    Sep 7, 2012 at 9:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.