0
$\begingroup$

Problem Description

I want to hold meetings where some given number of people will participate. They have some vacant dates respectively but they don't have the same date on which all of them can participate in the meeting. Therefore, I have to hold meetings multiple times so that all of them are able to participate at least a time. I want to reduce the number of meetings held to as few as possible.

For example, there are 4 participants $x_1, x_2, x_3, x_4$. They have their respective vacant dates:

  • $x_1$ has $y_1, y_2$
  • $x_2$ has $y_1, y_3$
  • $x_3$ has $y_2$
  • $x_4$ has $y_3$

In this case, holding meeting1 on $y_1$ where $\{x_1, x_2\}$ will participate, meeting2 on $y_2$ where $\{x_3\}$ will participates, and meeting3 on $y_3$ where $\{x_4\}$ will participates, is one of the possible solutions. However, the best solution is holding meeting1 on $y_2$ where $\{x_1, x_3\}$ will participate, and meeting2 on $y_3$ where $\{x_2, x_4\}$.

Problem Formulation

This problem can be formulated as follows: There are $N$ participants set $X = \{x_n\}_{n=1..N}$ and $M$ all possible dates set $Y = \{y_m\}_{m=1..M}$. Each participant $x_n$ has vacant dates $D_{x_n} \subseteq Y$ and $D_{x_n} \neq \emptyset$ respectively. I want to get the smallest partition $\mathcal{P} = \{P_i\}$ of $X$, e.g. $P_i \subseteq X, P_i \neq \emptyset, \bigcup_i P_i = X, P_i \cap{P_j} = \emptyset \ (i \neq j)$, that satisfy: $$\bigcap_{x_n \in P_i} D_{x_n} \neq \emptyset$$ In this notation, the optimization problem is formulated as: $$\min_{\mathcal{P}} |\mathcal{P}| \ s.t. \bigcap_{x_n \in P_i} D_{x_n} \neq \emptyset$$

I also noticed that this problem can be described as the problem on a bipartite graph with $\{x_n\} \in X$ and $\{y_m\} \in Y$ as nodes and $D_{x_n}$ can be converted into edges.

Question

  • What is better algorithm than just selecting participants who can be grouped into existing groups in a forward order, which apparently produces non-optimal solution? (Off course, there is a brute force algorithm which seems computationally hard. I don't want such an algorithm)
  • Is this problem NP hard?
  • If you know, please teach me the name of the class of this type of problems.
$\endgroup$
5
  • $\begingroup$ Hire a consultant to help you schedule your meetings. $\endgroup$ Feb 11, 2022 at 9:57
  • $\begingroup$ @Gerry Myerson This problem description with meeting scheduling is just for explaining it with an intuitive example. The real problem I'm facing is not for meeting scheduling. However, this formulation shares the same problem structure with the real problem. I am also intested in understanding the problem property itself. $\endgroup$
    – aiueogawa
    Feb 11, 2022 at 12:33
  • $\begingroup$ I suggest you post at or.stackexchange.com and delete this post. $\endgroup$ Feb 11, 2022 at 15:55
  • 2
    $\begingroup$ en.wikipedia.org/wiki/Set_cover_problem $\endgroup$
    – RobPratt
    Feb 11, 2022 at 17:54
  • $\begingroup$ "This problem description with meeting scheduling is just for explaining it with an intuitive example." In other words, it's a lie. Much better to be honest with us, and put all your cards on the table to begin with. $\endgroup$ Feb 11, 2022 at 21:04

1 Answer 1

1
$\begingroup$

From @RobPratt comment, I understood this problem is an instance of set cover problem.

The example in Problem Description above, can be viewed from the point of vacant dates instead of participants as:

  • y_1 has x_1, x_2
  • y_2 has x_1, x_3
  • y_3 has x_2, x_4

Then this problem can be seen as selecting minimum subsets from all possible subsets $\{\{x_1, x_2\}, \{x_1, x_3\}, \{x_2, x_4\}\}$ such that $X = \{x_1, x_2, x_3, x_4\}$ is fully covered by selected subsets.

From Wikipedia

  • This problem is an instance of set cover problem.
  • This problem is NP-complete.
  • There is a greedy algorithm with the approximation ratio, on each step selecting the subset which includes the largest number of uncovered elements.
$\endgroup$

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.