High Speed Internet
Dyanmic Programming algorithm problem.
Here are some extra notes that can be used in a recitation
Thanks to Suresh Venkatasubramanian for very helpful initial discussions on formulating this problem.
Material Developed by: Atri Rudra
Context of this assignment
This problem is part of a series of assignments in an UG algorithms course that are all related to access to high speed Internet.
Here are some slides from a talk that gives an overview of these assignments.
The Problem
Unfortunately it turns out that after all the work you put into designing a greedy algorithm to designing optimal placement of cell towers to give Internet access to everyone in SomePlaceInUSA
, the funding for putting up the cell towers fell through. Fortunately, there is a small glimmer of hope in that the town was able to secure a small grant to install a high speed Internet connection to one computer in the town's library. In this problem you will explore how effectively the town can share the resource of this one computer among the needy citizens of SomePlaceInUSA
in order to maximize the social good that this computer with high speed Internet connection can provide to the town as a whole.
Residents of SomePlaceInUSA
have applied to use the library's high speed Internet computer. Each of the $n$ citizens provide the following information. The $i$'th citizen submits a tuple $(s_i,f_i,w_i)$, where $s_i$ and the $f_i>s_i$ are the start and finish times of when the applicant plans to use the computer every weekday; $w_i$ is their estimation of the worth of getting to use the terminal from $s_i$ to $f_i$. (Note: the larger the value of $w_i$ the better for citizen $i$ and you can assume that $w_i\ge 0$ are integers.)
Your initial goal is to determine the maximum worth among all valid
subset of citizens $S\subseteq [n]$. A subset $S$ is valid
if the start and finish times of any citizen $i\neq j\in S$ do not conflict (i.e. either $s_i> f_j$ or $s_j> f_i$). Further, the worth of a subset is \[w(S)=\sum_{i\in S} w_i.\]
Sample Input/Output
Here is a sample input/output pair (the input array is stated as $[(s_1,f_1,w_1),\dots,(s_n,f_n,w_n)]$) for $n=3$:

Input:
$[(1,4,10),(5,10,20),(1,10,100)]$.
Output:
$100$ (for the subset $\{3\}$).
 Part (a): Citizens of
SomePlaceInUSA
realize that the current problem as stated above could be monopolized by a citizen who (perhaps legitimately) can get a huge worth by using the computer terminal for the entire day. They come to you to help them solve the following updated version of the problem: The input to your algorithm is now the set of triples $\{(s_i,f_i,w_i)i\in [n]\}$ along with an integer threshold $\tau\ge 0$. Your algorithm should
output the maximum worth among all
valid
subset $S\subseteq [n]$ with $S\ge \tau$. and output one with the maximum worth among all suchvalid
subsets (of size at least $\tau$). Note that the optimal worth can be $0$ (if there is novalid
subset of size at least $\tau$). 
Input:
$2;[(1,4,10),(5,10,20),(1,10,100)]$.
Output:
$30$ (for valid subset $\{1,2\}$). 
Input:
$3;[(1,4,10),(5,10,20),(1,10,100)]$.
Output:
$0$ (since there is no valid subset of size $3$).
Sample Input/Output
Here is a sample input/output pair (the input is stated as $\tau;[(s_1,f_1,w_1),\dots,(s_n,f_n,w_n)]$):
 The input to your algorithm is now the set of triples $\{(s_i,f_i,w_i)i\in [n]\}$ along with an integer threshold $\tau\ge 0$. Your algorithm should
output the maximum worth among all
 Part (b): (Thanks to Jonathan Manes for advice on legal aspects of this part of the question.) Citizens of
SomePlaceInUSA
realize that the current problem as stated above might not be representative of their town. In particular, they would like thevalid
subset to be representative of the economic diversity of their town. In particular, now they want your solution to meet some more requirements:
The input to your algorithm is now the set of $4$tuples $\{(s_i,f_i,w_i,e_i)i\in [n]\}$ (where $s_i,f_i,w_i$ are as before and $e_i\in \{1,2,3\}$ being an identifier for the range of their household income) along with there real numbers $0\le \rho_1,\rho_2,\rho_3\le 1$ such that $\rho_1+\rho_2+\rho_3\le 1$. Your algorithm should output the maximum worth among all
valid
subset $S\subseteq [n]$ with the following minimum requirement of the economic diversity for every $j\in [3]$, we must have \[\left\{i\in Se_i=j\}\right\ge \rho_j\cdot S.\] Note that the optimal worth can be $0$ (if there is novalid
subset that can meet the economic diversity constraint). 
Input:
$\left(\frac 13, \frac 12, 0\right);[(1,4,10,1),(5,10,20,2),(1,10,100,3)]$.
Output:
$30$ (for the valid subset $\{1,2\}$). 
Input:
$\left(\frac 13, \frac 13, \frac13\right);[(1,4,10,1),(5,10,20,2),(1,10,100,3)]$.
Output:
$0$ ($\emptyset$ is the only valid subset that satisfies the economic diversity constraint).
Sample Input/Output
Here is a sample input/output pair (the input is stated as $(\rho_1,\rho_2,\rho_3);[(s_1,f_1,w_1,e_1),\dots,(s_n,f_n,w_n,e_n)]$):

Hint
It might be useful to think of subproblems that generalize the ones we saw in weighted interval scheduling (but the recurrence would look different).
Walkthrough video
Thanks to Iman AbdulRashed for the video: