-2
$\begingroup$

There are $n$ students want to order food online. They plan to eat pizza. Each student has several favorite toppings (such as mushrooms, onions, garlic, sausage, etc.). Each student wants to eat at least half a pizza, and the toppings on the pizza must be her/his favorite Assuming that each pizza can only add one topping, consider the following questions:

  1. How many pizzas you can order to satisfy each student? Is it NP-hard or is there a polynomial time algorithm?
  2. If each person eats at least one-third of the pizza, and the toppings on the pizza must be what she/he likes, how many pizzas you need to order to satisfy each student? Is it NP-hard or polynomial solvable?

I don't know how to model it, can someone help me?

$\endgroup$
7
  • $\begingroup$ What have you tried? Do you want to model this as an ILP? A network-flow? Something else? $\endgroup$
    – JimN
    Commented May 4, 2023 at 17:47
  • $\begingroup$ I think it can be modeled as a classical model, such as network-flow. However, i don't have any idea. $\endgroup$
    – Yuhang Bai
    Commented May 5, 2023 at 2:49
  • $\begingroup$ Your title describes this problem as being similar to the Packing problem, and packing is considered NP-hard. But you are asking for a polytime algorithm for this. Can you elaborate on whether you are looking for a polynomial-time approximation scheme or a polynomial-time reduction or an actual polytime algorithm solution? And if you are looking for a polytime solution, do you have some restricted form of the packing problem that is polytime solvable which you are supposed to be working off of? $\endgroup$
    – JimN
    Commented May 5, 2023 at 5:23
  • $\begingroup$ Intuitively, I think it is similar to the packing problem, because it requires the minimum number of pizzas to satisfy all students, just like using the smallest box to pack all items. But this is not a standard bin packing problem, maybe it can be modeled as a simpler, classic algorithm model, such as maximum flow and so on. But I don't have a good idea, which is the purpose of my question. It is also ok if it can be modeled as a known NP-hard problem. $\endgroup$
    – Yuhang Bai
    Commented May 5, 2023 at 6:34
  • $\begingroup$ I have tried to modeled it as a maximum flow and SAT,but all failed. $\endgroup$
    – Yuhang Bai
    Commented May 5, 2023 at 6:35

1 Answer 1

1
$\begingroup$

In any scenario/students' choice of toppings, you don't have to order more than $n$ pizzas - each student picks one for themselves with one of their favorite topping.

Another observation - you will always have to order at least $\lceil\frac{n}{2}\rceil$ pizzas, because any student can eat no less than half a pizza. If there weren't any constraints on toppings, what you could do is divide students into groups of $2$ (with one group of size $1$ if $n$ is odd), and let each group order a pizza of their choosing. Note that you wouldn't be able to "move" any of the students to another (fully populated) group, because then they would have to divide their pizza into more parts than is allowed ($2$ in this case). Basically, this is the pigeonhole principle in action.

For example, if you had $n=5$ students and every one of them wanted garlic on their pizza, you will have to order at least $3$ pizzas (even though they will all be the same with garlic as a topping), but you never have to order more than $5$.

With added constraints on toppings, the number of pizzas may be larger than $\lceil\frac{n}{2}\rceil$, but as stated earlier, no greater than $n$.

If you had $n=2$ students, but one of them wanted only garlic, and the other one wanted sausage, you have to order $2$ pizzas to satisfy the constraints (even though $\lceil\frac{n}{2}\rceil=1<2$)

Those observations lead to a formulation of the problem that focuses more on groups of students rather than pizzas themselves, since each group will have to order a distinct pizza anyway; the objective is to find a grouping of students that satisfies topping constraints (each group gets a pizza such that every member gets what they want) and minimizes the number of groups (which is equal to number of pizzas).

More formally:

(Edit: added for accuracy) Let $T = \{t_1, t_2, ...\}$ be a set of all possible toppings. (for example - $T=\{mushrooms,onions,garlic,sausage\}$).

Let $S=\{S_1, S_2, ...,S_n\}$ be the family of non-empty sets of students' favorite toppings; $S_i \in T$ (for example $S_1=\{garlic, onion\}$);

Let $k$ be the maximum number of slices on a pizza (in your original problem, $k=2$, but we can generalize here);

Let $X=\{X_1, X_2,...\}$ be the family of groups of students (or a "grouping"). Each set $X_i$ is a subset of $S$ (you can define $X$ alternatively as a partition of $S$).

Constraints:

$S_i \neq \emptyset$ for each $S_i \in S$ (everyone has at least one favorite topping).

$X_i \cap X_j = \emptyset$ for $X_i, X_j \in X$. (groups are disjoint).

$1 \le |X_i| \le k$ for each $X_i \in X$. (groups can't be empty, but also no larger than $k$).

$\bigcup_{X_i \in X} X_i = S$ (no students are left out).

$\bigcap_{S_j \in X_i} S_j \neq \emptyset$ (each group has a common favorite topping).

We want to find a grouping $X$ that satisfies constraints listed above, such that $|X|$ is minimal:

$$(X=?) \implies (|X| \to min)$$

This model takes into account every constraint you listed. At first glance, the problem looks NP-hard with complexity of roughly $O(n!)$ (think of how many possible groupings there are: you can make $n \choose k$ different groups of size exactly $k$, there are at least $\lceil\frac{n}{2}\rceil$ different groups in a grouping, groups can be of different size, and so on...)

Unless there's some property of the problem I'm missing, you have to search the entire space of groupings to determine the best, hence the problem is computationally hard in the general case. Maybe that's not a problem for small values of $n$?

Also, if you absolutely need this problem to be modelled in terms of a classical problem, you can read about the hitting set problem (this is some material I found online that explains it). My first attempt of modelling your problem used the hitting set problem as a basis, but I ran into issues with constraints regarding $k$. What I found, though, is that the hitting set problem is equivalent to your problem if we don't concern ourselves about $k$ (so if a student can eat any amount of pizza to be happy). Since the hitting set problem is in itself NP-hard, I'm inclined to think that your variant (which has more constraints) is similarly complex as well.

EDIT: Why is the simpler version equivalent to the hitting set problem?

We forget about constraints with $k$, that is - a student can now eat any amount of pizza (no matter if it's half of it, a third, or any fraction) to be satisfied. This allows for a simpler model:

$T = \{t_1, t_2, ...\}$ - set of all possible toppings.

$S = \{S_1, S_2, ..., S_n\}$ - family of sets of preferred toppings, $S_i \in T$.

$P = \{p_1, p_2, ...\}$ - set of pizzas ordered. Let each element also $p_i$ describe a topping of that pizza, so for example $p_3=onion$. (note that each type of topping can be ordered only once and still satisfy constraints, because a pizza can be shared by an arbitrary number of students - there's no need to order two pizzas of the same topping).

We only have one constraint here:

$\forall S_i : S_i \cap P \neq \emptyset$ ($P$ intersects each set of student's choices; this guarantees that each student will find a pizza in $P$ that has one of their favorite toppings)

And our objective is minimizing $|P|$: $$(P=?) \implies (|P| \to min)$$

In short, we are finding the smallest set $P$ that has at least $1$ common element with every set $S_i$, which is the formulation of the hitting set problem. There is no need to worry about dividing students into groups, because as long as each student can find a pizza they like in $P$, the solution is valid.

As I have written earlier, I didn't find a way to extend the simpler model to the variant where a student has to eat at least half a pizza, that's why in the original answer I opted for another approach, independent of the hitting set problem.

$\endgroup$
7
  • $\begingroup$ Thank you! But i can't understand the Fourth and Fifth constraints. I think that $X_i$ is the subset of students and $S_i$ is the subset of topping. Why the union of $X_i$ equals to S? $\endgroup$
    – Yuhang Bai
    Commented May 5, 2023 at 12:14
  • $\begingroup$ The fourth constraint ensures that every student is a part of a group. If that constraint wasn't there, you could construct groupings that look like this, for example: $X=\{ \{S_1, S_2\}, \{S_3\} ,\{S_4\} \}$, with $S=\{S_1, S_2, S_3, S_4, S_5\}$ and $k=2$ . This satisfies the second and third constraint, but student 5 doesn't get any pizza, because they are not part of any group. By adding the fourth constraint you prevent that situation. You can also view it that way - if you "ungroup" $X$ (= take the union of every group), you have to end up with the starting set of students. $\endgroup$
    – anna
    Commented May 5, 2023 at 12:52
  • $\begingroup$ The fifth constraint is basically just a filter that discards groupings where there is a group that cannot order a pizza for themselves. A situation like that may arise if, for example, you make a group consisting of someone wanting only onion and someone wanting only mushroom. Your grouping may satisfy the first 4 constraints, but that grouping is incorrect, because a group is defined to order exactly one pizza. That is not possible in the above example, you cannot order a single pizza that satisfies both of those students. $\endgroup$
    – anna
    Commented May 5, 2023 at 12:58
  • $\begingroup$ Okay. I got it. If we don't concern $k$, that is, a student can eat any amount of pizza to be happy, then we can reduce the third constraints. However we also must have the Fifth constraints, how do we reduce it to hitting problem? Thanks for your answer again. $\endgroup$
    – Yuhang Bai
    Commented May 5, 2023 at 13:17
  • $\begingroup$ I edited my answer, please take a look. $\endgroup$
    – anna
    Commented May 5, 2023 at 14:13

Your Answer

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

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