Find optimal pair of slots to satisfy most preferences

Question

Assume that we create a poll and have each student of a class submit all possible one-hour time slots that he/she can make it for a help session (recitation). In the end, we can only choose two slots and we want to satisfy most preferences so that the maximum number of the students can come in at least one of them. Visualize this as a matrix $A$ s.t.

$$A_{ij}= \left\{ \begin{array}{ll} 1, & if\ i\text{-th student is available at time slot }j \\ 0, & o.w. \\ \end{array} \right.$$

What is the optimal solution?

I was thinking that if $A$ is $m\times n$ then the solution looks like $$\underset{\mathbf{v}\in\{0,1\}^{n\times1}, \text{supp}(\mathbf{v})=2}{\mathrm{argmax}}||A\mathbf{v}||$$ i.e. take all possible binary vectors with exactly two ones, right multiply them with $A$ and choose the one that gives the maximum norm (e.g. Euclidean norm) for the product. Then, choose the slots of the indices that correspond to the non-zero elements of this vector. Is this idea correct? Can someone help with the proof?

I'm actually a teaching assistant for a course and the above is my problem.

Answer 1

Just taking the Euclidean norm will not always be enough. As a simple counter example consider the matrix $A$ for only three students and three time slots $$ A = \left( \begin{array}{ccc} 1 & 1 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1\end{array}\right) $$ then we find for the three possible vectors ${\bf v}$ $$ {\bf v} = \left( \begin{array}{c} 1 \\ 1 \\ 0 \end{array}\right) \rightarrow A {\bf v} = \left( \begin{array}{c} 2 \\ 1 \\ 0 \end{array}\right) \rightarrow ||A {\bf v}||=\sqrt{5} $$ $$ {\bf v} = \left( \begin{array}{c} 1 \\ 0 \\ 1 \end{array}\right) \rightarrow A {\bf v} = \left( \begin{array}{c} 1 \\ 0 \\ 1 \end{array}\right) \rightarrow ||A {\bf v}||=\sqrt{2} $$ $$ {\bf v} = \left( \begin{array}{c} 0 \\ 1 \\ 1 \end{array}\right) \rightarrow A {\bf v} = \left( \begin{array}{c} 1 \\ 1 \\ 1 \end{array}\right) \rightarrow ||A {\bf v}||=\sqrt{3} $$ whereas in the three cases respectively 2,2, and 3 students would participate and hence the last case would be optimal.

The problem is caused by the entries 2 that can appear in the vector $A {\bf v}$. A simple solution would be to modify the vector, in which case you would get $$ \max_{1\leq \alpha < \beta \leq n} || A_{i\alpha} \lor A_{i\beta}|| $$

If you like to avoid using the logical OR operation, there is an alternative but equivalent expression: $$ \max_{1\leq \alpha < \beta \leq n} \frac{1}{4} \left(|| A_{i\alpha} + A_{i\beta}|| + 3 || A_{i\alpha} - A_{i\beta}|| \right) $$

Answer 2

You can solve the problem via integer linear programming as follows. Let binary decision variable $v_j$ indicate whether slot $j$ is selected, and let binary decision variable $x_i$ indicate whether student $i$ is covered by at least one of the two selected slots. The problem is to maximize $\sum_i x_i$ subject to linear constraints \begin{align} \sum_j v_j &= 2 \tag1 \\ \sum_j A_{ij} v_j &\ge x_i &&\text{for all $i$} \tag2 \end{align} Constraint $(1)$ selects exactly two slots. Constraint $(2)$ enforces the logical implication $x_i \implies \bigvee\limits_{j:A_{ij}=1} v_j$.