Notation for Coding Mini Project
Here we collect notation related to the coding mini project.
Notation for all problems
| Notation | Meaning |
| $G=(V,E)$ | The (undirected) communication graph of the ForProfitOnly |
| $i$ | $i\in V$ is the content provider |
| $C$ | $C\subseteq V\setminus \{i\}$ is the set of clients |
| $d_e$ | Delay of edge $e$: for all problem $d_e=1$ for every $e\in E$ |
| $\text{pkt}_c$ | Packet for client $c\in C$ |
| $D(P)$ | Delay of path $P$, i.e. $D(P)=\sum_{e\in P} d_e$ |
| $d(c)$ | For $c\in C$, minimum delay $D(P_c)$ among all $i-c$ paths $P_c$ |
| $P'_c$ | $i-c$ path output by your algorithm (note $c\in C$) |
| $L_{P'}$ | List of all paths $P'_c$ for all $c\in C$ output by your algorithm |
| $b_u$ | Bandwidth of node $u\in V$, i.e. the maximum number of packets node $u$ can send in one time step/tick |
| $\text{priority}(c)$ | Priority of client $c\in C$. |
| $\text{pmt}_c$ | Payment that client $c$ makes to ForProfitOnly |
| $\alpha_c$ | Tolerance threshold for client $c$ (see the various penalty functions on how it is used) |
Notation introduced in Problem 1
| Notation | Meaning |
| $pen_0(c, D(P'_c),\alpha_c, d(c),\text{pmt}_c)$ | Penalty function defined as follows: $pen_0(c,D(P'_c),\alpha_c,d(c),\text{pmt}_c) = \begin{cases} \text{pmt}_c &\text{if} \quad D(P'_c) >\alpha_c \cdot d(c) \\ 0 &\text{ otherwise} \end{cases}$ |
| $rev(c, D(P'_c),\alpha_c,d(c),\text{pmt}_c)$ | Revenue received from client $c$, defined as follows: $rev(c, D(P'_c),\alpha_c,d(c),\text{pmt}_c) = \text{pmt}_c - pen_0(c,D(P'_c),\alpha_c,d(c),\text{pmt}_c)$ |
Notation introduced in Problem 3
| Notation | Meaning |
| $Z$ | For all $u\in V\setminus \{i\}$, bandwidth can be increased at a cost of $\$Z$ per unit increase in bandwidth |
| $b'_u$ | Updated bandwidth for $u\in V\setminus\{i\}$ (as determined by your algorithm). |
| $X$ | Total bandwidth increase, i.e. $X=\sum_{u \in V \setminus \{i\}} \max(0,b'_u - b_u)$ |
| $\beta_c$ | Complaint threshold for $c\in C$ who can complain if $D(P'_c)> \beta_c\cdot d(c)$ |
| $S$ | Subset of clients $S\subseteq C$ |
| $\rho_{\text{lawsuit}}$ | If $\rho_{\text{lawsuit}}$ fraction of clients (in $C$) complain, then ForProfitOnly gets hit with a lawsuit |
| $A$ | $\$A$ is the lawsuit/settlement amount |
| $\rho_{\text{fcc}}$ | If $\rho_{\text{fcc}}$ fraction of clients (in $S$) complain, then ForProfitOnly gets hit with an FCC fine |
| $B$ | $\$B$ is the FCC fine amount |
| $pen_1(T,L_{P'},L_{\beta},L_{D},\rho, L)$ | Second penalty function defined as follows. If at least $\lfloor \rho \cdot |T| \rfloor$ clients in $T$ complain (recall $c\in T$ complains if $D(P'_c) > \beta_c\cdot d(c)$), then $pen_1$ outputs $L$. Else $pen_1$ outputs $0$. |
| $L_{b'}$ | List of updated bandwidths (output by your algorithm) |
Notation introduced in Problem 4
| Notation | Meaning |
| $R$ | Set of rural clients $R\subseteq C$. For every $c\in C$, $\alpha_c=\infty$ |
| $L_{priority}$ | List of $\text{priority(c)}$ for every $c\in C$ |