High Speed Internet

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.\]

However, as time goes by the town realizes that solving the above problem is not necessarily the best for the overall good of the town. In the rest of the problem, you will design algorithms to maximize the total worth of your chosen subset along with some additional constraints to address some potential inequalities in your solution.

• 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 such valid subsets (of size at least $\tau$). Note that the optimal worth can be $0$ (if there is no valid subset of size at least $\tau$).

  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)]$):

  1. Input: $2;[(1,4,10),(5,10,20),(1,10,100)]$.
     Output: $30$ (for valid subset $\{1,2\}$).
  2. Input: $3;[(1,4,10),(5,10,20),(1,10,100)]$.
     Output: $0$ (since there is no valid subset of size $3$).

  Design an $O(n^2)$ algorithm to solve the above problem.
  
  
• 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 the valid 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 S|e_i=j\}\right|\ge \rho_j\cdot |S|.\] Note that the optimal worth can be $0$ (if there is no valid subset that can meet 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)]$):

  1. 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\}$).
  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).

  Design an $O(n^5)$ time algorithm to solve the above problem.