There are no optimal algorithms known!

Other than the first problem, we do not know of optimal algorithms to solve the rest of the problems and we suspect that doing so is not possible (definitely not within a semester). Note that this is unlike the HW Q3s where your code is supposed to always output the optimal/correct solution: i.e. you will have to think of algorithms where you might not be able to prove any guarantee on how good your output is.

Input

The input for the problem is the same as the previous one except for the bandwidth being limited and the tolerance threshold for every client being an arbitrary value greater than or equal to $1$. To put it formally, following is the input:

1. $G = (V, E)$
2. $i \in V$
3. $C$ s.t. $C \subseteq V \setminus \{i\}$
4. For all $u \in V \setminus \{i\}$, $b_u$ s.t. $b_u < \infty$
5. For all $c \in C$, $\alpha_c$ s.t. $\alpha_c \ge 1$
6. For all $c \in C$, $\text{pmt}_c$
7. For all $c \in C$, $\text{priority(c)} =$ PRIORITY_DEFAULT

Note

The highlighted input, is the part of the input that is different from the previous problem.

Determining $D(P')$ for every client

We claim that: $D(P’_1) = 2, D(P’_3) = 4, D(P’_6) = 4, D(P’_7) = 4, D(P’_8) = 3$. We verify this by tracing each time step in the routing simulation:

At Time Tick $0$:

Current: All packets at 0.

Passed on: All

At Time Tick $1$:

Current:

• $\text{pkt}_1$ at node $10$
• $\text{pkt}_3$ at node $10$
• $\text{pkt}_6$ at node $10$
• $\text{pkt}_7$ at node $10$
• $\text{pkt}_8$ at node $9$

Passed on: All

At Time Tick $2$:

Current:

• $\text{pkt}_1$ at node $1$
• $\text{pkt}_3$ at node $1$
• $\text{pkt}_6$ at node $1$
• $\text{pkt}_7$ at node $1$
• $\text{pkt}_8$ at node $3$

Reached: $\text{pkt}_1$

Passed on: $\text{pkt}_3, \text{pkt}_6, \text{pkt}_7,\text{pkt}_8$

At Time Tick $3$:

Current:

• $\text{pkt}_3$ at node $2$
• $\text{pkt}_6$ at node $5$
• $\text{pkt}_7$ at node $4$
• $\text{pkt}_8$ at node $8$

Reached: $\text{pkt}_8$

Passed on: $\text{pkt}_3, \text{pkt}_6, \text{pkt}_7$

At Time Tick $4$:

Current:

• $\text{pkt}_3$ at node $3$
• $\text{pkt}_6$ at node $6$
• $\text{pkt}_7$ at node $7$

Reached: All packets have reached their destination so routing terminates.

Determining $D(P')$ for every client

We claim that: $D(P’_1) = 2, D(P’_3) = 2, D(P’_6) =4, D(P’_7) = 4, D(P’_8) = 5$. Let's now trace each time tick in the routing simulation:

At Time Tick $0$:

Current: All packets at 0.

Passed on: All

At Time Tick $1$:

Current:

• $\text{pkt}_1$ at node $10$
• $\text{pkt}_3$ at node $9$
• $\text{pkt}_6$ at node $9$
• $\text{pkt}_7$ at node $10$
• $\text{pkt}_8$ at node $9$

Passed on: $\text{pkt}_1, \text{pkt}_3, \text{pkt}_7$

Delayed: $\text{pkt}_6, \text{pkt}_8$

At Time Tick $2$:

Current:

• $\text{pkt}_1$ at node $1$
• $\text{pkt}_3$ at node $3$
• $\text{pkt}_6$ at node $9$
• $\text{pkt}_7$ at node $1$
• $\text{pkt}_8$ at node $9$

Reached: $\text{pkt}_1, \text{pkt}_3$

Passed on: $\text{pkt}_6, \text{pkt}_7$

Delayed: $\text{pkt}_8$

At Time Tick $3$:

Current:

• $\text{pkt}_6$ at node $3$
• $\text{pkt}_7$ at node $4$
• $\text{pkt}_8$ at node $9$

Passed on: $\text{pkt}_6, \text{pkt}_7, \text{pkt}_8$

At Time Tick $4$:

Current:

• $\text{pkt}_6$ at node $6$
• $\text{pkt}_7$ at node $7$
• $\text{pkt}_8$ at node $3$

Reached: $\text{pkt}_6, \text{pkt}_7$

Passed on: $\text{pkt}_8$

At Time Tick $5$:

Current:

• $\text{pkt}_8$ at node $8$

Reached: $\text{pkt}_8$

NOTE: Some of the $D(P'_c)$ values have changed from the previous solution due to bandwidth restrictions.

A useful resource

For the specific reflection questions, we will be quoting from Cathy O'Neil and Hanna Gunn's book chapter titled Near-Term Artificial Intelligence and the Ethical Matrix .

You can access the book chapter as a PDF from UB Libraries .

While the book is about ethical issues in AI, the concepts in the book chapter are applicable more widely and in particular, for our project (that does not have anything to do with AI).

Preliminary Grading Guidelines

Below is a preliminary instantiation of the generic grading rubric above for (the last three questions) on Problem 2. (The Algorithm Idea part will be graded similarly to algorithm ideas in homework submissions.) In actual grading, we will use a grading rubric that expands on the preliminary grading rubric below.

• Level 0.
  1. The authors did not answer all reflective questions; OR
  2. Answers may not be entirely relevant to the assignment.
• Level 1.
  1. The authors answers all reflective questions, although the responses are underdeveloped; AND
  2. (For the 2nd and 3rd questions) Authors have identified un/favored users/stakeholders, but have either missed a stakeholder who should have been identified as either favored or unfavored OR have given little justification for their assessment.
  3. (For the 4th question) The authors clearly understand the questions, but have not demonstrated much effort in thinking through the connection between their algorithm and fairness to stakeholders. Answers may seem perfunctory.
• Level 2.
  1. The authors answer all reflective questions thoroughly and thoughtfully; AND
  2. (For the 2nd and 3rd questions) The authors clearly demonstrate their grasp of the questions and their algorithm’s potential to favor some users/stakeholders interests over others.
  3. (For the 4th question) Outside sources— i.e. O’Neil and/or Gunn’s definition of fairness (or parts of their definitions)—are directly referenced in responses. Authors have clearly connected these sources to their own designs.