Find optimal pair of slots to satisfy most preferences
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
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{
beginarrayll
1, & if itext-th student is available at time slot j \
0, & o.w. \
endarray
right.$$
What is the optimal solution?
I was thinking that if $A$ is $mtimes n$ then the solution looks like
$$undersetmathbfvin0,1^ntimes1, textsupp(mathbfv)=2mathrmargmax||Amathbfv||$$
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.
linear-algebra optimization norm
asked Aug 23 at 6:04
mgus
624616
add a comment |Â
up vote
0
down vote
favorite
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{
beginarrayll
1, & if itext-th student is available at time slot j \
0, & o.w. \
endarray
right.$$
What is the optimal solution?
I was thinking that if $A$ is $mtimes n$ then the solution looks like
$$undersetmathbfvin0,1^ntimes1, textsupp(mathbfv)=2mathrmargmax||Amathbfv||$$
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.
linear-algebra optimization norm
asked Aug 23 at 6:04
mgus
624616
It's not that hard to write a program to try all $binom n2$ pairs of slots and pick the best pair.
– Rahul
Aug 24 at 10:13
@Rahul Yes I have already done that. Basically, I picked the vector $mathbfv$ which gives the maximum support size in $Amathbfv$ but I am also interested in other options/proof.
– mgus
Aug 24 at 13:47
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
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{
beginarrayll
1, & if itext-th student is available at time slot j \
0, & o.w. \
endarray
right.$$
What is the optimal solution?
I was thinking that if $A$ is $mtimes n$ then the solution looks like
$$undersetmathbfvin0,1^ntimes1, textsupp(mathbfv)=2mathrmargmax||Amathbfv||$$
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.
linear-algebra optimization norm
asked Aug 23 at 6:04
mgus
624616
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{
beginarrayll
1, & if itext-th student is available at time slot j \
0, & o.w. \
endarray
right.$$
What is the optimal solution?
I was thinking that if $A$ is $mtimes n$ then the solution looks like
$$undersetmathbfvin0,1^ntimes1, textsupp(mathbfv)=2mathrmargmax||Amathbfv||$$
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.
linear-algebra optimization norm
asked Aug 23 at 6:04
mgus
624616
asked Aug 23 at 6:04
mgus
624616
asked Aug 23 at 6:04
mgus
624616
asked Aug 23 at 6:04
mgus
624616
624616
It's not that hard to write a program to try all $binom n2$ pairs of slots and pick the best pair.
– Rahul
Aug 24 at 10:13
@Rahul Yes I have already done that. Basically, I picked the vector $mathbfv$ which gives the maximum support size in $Amathbfv$ but I am also interested in other options/proof.
– mgus
Aug 24 at 13:47
add a comment |Â
It's not that hard to write a program to try all $binom n2$ pairs of slots and pick the best pair.
– Rahul
Aug 24 at 10:13
@Rahul Yes I have already done that. Basically, I picked the vector $mathbfv$ which gives the maximum support size in $Amathbfv$ but I am also interested in other options/proof.
– mgus
Aug 24 at 13:47
It's not that hard to write a program to try all $binom n2$ pairs of slots and pick the best pair.
– Rahul
Aug 24 at 10:13
It's not that hard to write a program to try all $binom n2$ pairs of slots and pick the best pair.
– Rahul
Aug 24 at 10:13
@Rahul Yes I have already done that. Basically, I picked the vector $mathbfv$ which gives the maximum support size in $Amathbfv$ but I am also interested in other options/proof.
– mgus
Aug 24 at 13:47
@Rahul Yes I have already done that. Basically, I picked the vector $mathbfv$ which gives the maximum support size in $Amathbfv$ but I am also interested in other options/proof.
– mgus
Aug 24 at 13:47
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
0
down vote
accepted
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( beginarrayccc 1 & 1 & 0 \ 0 & 1 & 0 \ 0 & 0 & 1endarrayright)
$$
then we find for the three possible vectors $bf v$
$$
bf v = left( beginarrayc 1 \ 1 \ 0 endarrayright) rightarrow A bf v = left( beginarrayc 2 \ 1 \ 0 endarrayright) rightarrow ||A bf v||=sqrt5
$$
$$
bf v = left( beginarrayc 1 \ 0 \ 1 endarrayright) rightarrow A bf v = left( beginarrayc 1 \ 0 \ 1 endarrayright) rightarrow ||A bf v||=sqrt2
$$
$$
bf v = left( beginarrayc 0 \ 1 \ 1 endarrayright) rightarrow A bf v = left( beginarrayc 1 \ 1 \ 1 endarrayright) rightarrow ||A bf v||=sqrt3
$$
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_1leq alpha < beta leq n || A_ialpha lor A_ibeta||
$$
If you like to avoid using the logical OR operation, there is an alternative but equivalent expression:
$$
max_1leq alpha < beta leq n frac14 left(|| A_ialpha + A_ibeta|| + 3 || A_ialpha - A_ibeta|| right)
$$
answered Aug 24 at 9:53
Ronald Blaak
1,79938
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
accepted
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( beginarrayccc 1 & 1 & 0 \ 0 & 1 & 0 \ 0 & 0 & 1endarrayright)
$$
then we find for the three possible vectors $bf v$
$$
bf v = left( beginarrayc 1 \ 1 \ 0 endarrayright) rightarrow A bf v = left( beginarrayc 2 \ 1 \ 0 endarrayright) rightarrow ||A bf v||=sqrt5
$$
$$
bf v = left( beginarrayc 1 \ 0 \ 1 endarrayright) rightarrow A bf v = left( beginarrayc 1 \ 0 \ 1 endarrayright) rightarrow ||A bf v||=sqrt2
$$
$$
bf v = left( beginarrayc 0 \ 1 \ 1 endarrayright) rightarrow A bf v = left( beginarrayc 1 \ 1 \ 1 endarrayright) rightarrow ||A bf v||=sqrt3
$$
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_1leq alpha < beta leq n || A_ialpha lor A_ibeta||
$$
If you like to avoid using the logical OR operation, there is an alternative but equivalent expression:
$$
max_1leq alpha < beta leq n frac14 left(|| A_ialpha + A_ibeta|| + 3 || A_ialpha - A_ibeta|| right)
$$
answered Aug 24 at 9:53
Ronald Blaak
1,79938
add a comment |Â
up vote
0
down vote
accepted
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( beginarrayccc 1 & 1 & 0 \ 0 & 1 & 0 \ 0 & 0 & 1endarrayright)
$$
then we find for the three possible vectors $bf v$
$$
bf v = left( beginarrayc 1 \ 1 \ 0 endarrayright) rightarrow A bf v = left( beginarrayc 2 \ 1 \ 0 endarrayright) rightarrow ||A bf v||=sqrt5
$$
$$
bf v = left( beginarrayc 1 \ 0 \ 1 endarrayright) rightarrow A bf v = left( beginarrayc 1 \ 0 \ 1 endarrayright) rightarrow ||A bf v||=sqrt2
$$
$$
bf v = left( beginarrayc 0 \ 1 \ 1 endarrayright) rightarrow A bf v = left( beginarrayc 1 \ 1 \ 1 endarrayright) rightarrow ||A bf v||=sqrt3
$$
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_1leq alpha < beta leq n || A_ialpha lor A_ibeta||
$$
If you like to avoid using the logical OR operation, there is an alternative but equivalent expression:
$$
max_1leq alpha < beta leq n frac14 left(|| A_ialpha + A_ibeta|| + 3 || A_ialpha - A_ibeta|| right)
$$
answered Aug 24 at 9:53
Ronald Blaak
1,79938
add a comment |Â
up vote
0
down vote
accepted
up vote
0
down vote
accepted
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( beginarrayccc 1 & 1 & 0 \ 0 & 1 & 0 \ 0 & 0 & 1endarrayright)
$$
then we find for the three possible vectors $bf v$
$$
bf v = left( beginarrayc 1 \ 1 \ 0 endarrayright) rightarrow A bf v = left( beginarrayc 2 \ 1 \ 0 endarrayright) rightarrow ||A bf v||=sqrt5
$$
$$
bf v = left( beginarrayc 1 \ 0 \ 1 endarrayright) rightarrow A bf v = left( beginarrayc 1 \ 0 \ 1 endarrayright) rightarrow ||A bf v||=sqrt2
$$
$$
bf v = left( beginarrayc 0 \ 1 \ 1 endarrayright) rightarrow A bf v = left( beginarrayc 1 \ 1 \ 1 endarrayright) rightarrow ||A bf v||=sqrt3
$$
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_1leq alpha < beta leq n || A_ialpha lor A_ibeta||
$$
If you like to avoid using the logical OR operation, there is an alternative but equivalent expression:
$$
max_1leq alpha < beta leq n frac14 left(|| A_ialpha + A_ibeta|| + 3 || A_ialpha - A_ibeta|| right)
$$
answered Aug 24 at 9:53
Ronald Blaak
1,79938
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( beginarrayccc 1 & 1 & 0 \ 0 & 1 & 0 \ 0 & 0 & 1endarrayright)
$$
then we find for the three possible vectors $bf v$
$$
bf v = left( beginarrayc 1 \ 1 \ 0 endarrayright) rightarrow A bf v = left( beginarrayc 2 \ 1 \ 0 endarrayright) rightarrow ||A bf v||=sqrt5
$$
$$
bf v = left( beginarrayc 1 \ 0 \ 1 endarrayright) rightarrow A bf v = left( beginarrayc 1 \ 0 \ 1 endarrayright) rightarrow ||A bf v||=sqrt2
$$
$$
bf v = left( beginarrayc 0 \ 1 \ 1 endarrayright) rightarrow A bf v = left( beginarrayc 1 \ 1 \ 1 endarrayright) rightarrow ||A bf v||=sqrt3
$$
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_1leq alpha < beta leq n || A_ialpha lor A_ibeta||
$$
If you like to avoid using the logical OR operation, there is an alternative but equivalent expression:
$$
max_1leq alpha < beta leq n frac14 left(|| A_ialpha + A_ibeta|| + 3 || A_ialpha - A_ibeta|| right)
$$
answered Aug 24 at 9:53
Ronald Blaak
1,79938
answered Aug 24 at 9:53
Ronald Blaak
1,79938
answered Aug 24 at 9:53
Ronald Blaak
1,79938
answered Aug 24 at 9:53
Ronald Blaak
1,79938
1,79938
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2891754%2ffind-optimal-pair-of-slots-to-satisfy-most-preferences%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
It's not that hard to write a program to try all $binom n2$ pairs of slots and pick the best pair.
– Rahul
Aug 24 at 10:13
@Rahul Yes I have already done that. Basically, I picked the vector $mathbfv$ which gives the maximum support size in $Amathbfv$ but I am also interested in other options/proof.
– mgus
Aug 24 at 13:47