Boston Public Schools has a mechanism for assigning incoming freshmen to high schools throughout the city. I have no ide
Posted: Mon May 02, 2022 5:01 pm
Boston Public Schools has a mechanism for assigning incoming
freshmen to high schools throughout the city. I have no idea
how it works, so let’s assume the following.
There are F incoming freshmen and H high schools in
Boston. Each student has a set of schools they are interested
in attending. We will let Si be the set of
schools that student i is interested in (1 ≤ i ≤ F). Note that the
cardinalities of the Si ’s may not all be the same, but
they’re all non-empty.
Similarly, each school has a set of students they would like to
attend their school. We will let Tj be the set of students
that school j would like to attend their school (1 ≤ j ≤ H). We’ll
assume that each school could take on 150 students, but they
don’t necessarily need to fill all slots.
We would like to determine if there is a way to assign every
student to a school such that all constraints are
met. More precisely, we have the following inputs and desired
outputs:
• Input: The values F, H, S1, . . . , SF , T1, . . . , TH .
• Output: If possible, an assignment of students to schools such
that (1) every student is assigned, (2) every school is assigned at
most 150 students, (3) every student assigned to school j is
from the set Tj , and (4) the school that student i is assigned to
is in set Si .
Otherwise, ⊥ meaning that no such assignment is possible.
Show how to obtain a polynomial time algorithm for this problem
by using the integer maximum flow problem that we know how to
solve. Your algorithm should do the following (1) build a flow
network, (2) solve for the max flow on your flow network, (3) use
the resulting flow to determine if an assignment exists.
(a) How would you build a flow network from the inputs given
above? If you had a flow, what would the flow value on each edge
represent?
(b) Suppose you’ve used Ford-Fulkerson to solve MAXFLOW on the
graph from part (a).Which flow value(s) would correspond to a
desired student assignment existing (the “yes range”)? Which flow
value(s) correspond to no assignment existing (the “no range”)?
In the case where a desired assignment exists, how would you
find the assignment from the max flow? Argue why every
possible flow value is in either the yes range or no range.
freshmen to high schools throughout the city. I have no idea
how it works, so let’s assume the following.
There are F incoming freshmen and H high schools in
Boston. Each student has a set of schools they are interested
in attending. We will let Si be the set of
schools that student i is interested in (1 ≤ i ≤ F). Note that the
cardinalities of the Si ’s may not all be the same, but
they’re all non-empty.
Similarly, each school has a set of students they would like to
attend their school. We will let Tj be the set of students
that school j would like to attend their school (1 ≤ j ≤ H). We’ll
assume that each school could take on 150 students, but they
don’t necessarily need to fill all slots.
We would like to determine if there is a way to assign every
student to a school such that all constraints are
met. More precisely, we have the following inputs and desired
outputs:
• Input: The values F, H, S1, . . . , SF , T1, . . . , TH .
• Output: If possible, an assignment of students to schools such
that (1) every student is assigned, (2) every school is assigned at
most 150 students, (3) every student assigned to school j is
from the set Tj , and (4) the school that student i is assigned to
is in set Si .
Otherwise, ⊥ meaning that no such assignment is possible.
Show how to obtain a polynomial time algorithm for this problem
by using the integer maximum flow problem that we know how to
solve. Your algorithm should do the following (1) build a flow
network, (2) solve for the max flow on your flow network, (3) use
the resulting flow to determine if an assignment exists.
(a) How would you build a flow network from the inputs given
above? If you had a flow, what would the flow value on each edge
represent?
(b) Suppose you’ve used Ford-Fulkerson to solve MAXFLOW on the
graph from part (a).Which flow value(s) would correspond to a
desired student assignment existing (the “yes range”)? Which flow
value(s) correspond to no assignment existing (the “no range”)?
In the case where a desired assignment exists, how would you
find the assignment from the max flow? Argue why every
possible flow value is in either the yes range or no range.