AA Final Assignment (70 marks in total)
Mingyu Guo
2023 S1
Instructions
If a solution doesn’t contain enough details or is not convincing (i.e., sounds
like “guessing”), then it is considered incorrect.
1 Problem 1 (10 marks)
We described the serial cost sharing mechanism in assignment 1 (rule 3). A short
description goes like this: given n households with n valuations (v1, v2, . . . , vn)
for the swimming pool, we find the largest k∗ so that at least k∗ households are
willing to each pay at least 1k∗ . Then these k
∗ households have access to the
swimming pool and they each pay 1k∗ (together the total payment is 1, which
will exactly cover the project cost). For example, suppose there are n = 4
households and their valuations are (1, 1, 0.5, 0.2), then k∗ = 3 (as we can find
three households who are willing to pay at least 13 ).
We still assume that the valuations are from U(0, 1) (i.e., uniform distribu-
tion from 0 to 1).
Prove that as n goes to infinity, the expected number of winners (i.e., the
expectation of k∗ in the above description) also goes to infinity.
2 Problem 2 (15 marks)
Given an undirected graph G, you are asked to delete k nodes so that the
remaining nodes’ maximum degree is at most d. Please derive a fixed-parameter
tractable algorithm using k and d as parameters. That is, your algorithm’s
complexity should be O(f(k, d)Poly(n)).
3 Problem 3 (15 marks)
Let S = {1, 2, . . . , n}. Let X1, X2, . . . , Xk be k subsets of S. That is, Xi ⊆ S.
Your task is to select as few integers as possible from S, under the constraint
that for every Xi, at least |Xi| − 1 integers from Xi are selected (i.e., at most
1
one integer is not selected). Please prove that this problem is NP-hard. Please
derive a 2-approximation algorithm. That is, if the optimal (minimum) number
of integers selected is OPT, then your algorithm selects at most 2OPT integers.
4 Problem 4 (15 marks)
Suppose you are given two MLP models (as described by the figure below). For
simplicity, we assume both MLP models are exactly as described by the figure
(i.e., 6 inputs, 2 hidden layers, 1 output). Also for simplicity, we assume every
input feature is a continuous value from [0, 1] and all activation functions are
ReLU.
For example, suppose the model is on life expectancy. The six inputs are
bmi (normalised to [0, 1]), blood sugar level (normalised to [0, 1]), cholesterol
level (normalised to [0, 1]), etc. and the output is life expectancy.
Suppose the two MLP models are already trained (i.e., they are models
trained by two health insurance companies using their own private data), you
want to analyse the two models and figure out whether there are major incon-
sistencies. That is, you want to figure out the input (a vector of 6 dimensions)
that leads to the maximum gap between the two models’ predictions. Formally,
given the two MLP models with their specific weights and biases, the task is to
figure out
arg max
0≤x1,...,x6≤1
|MLP1(x1, . . . , x6)−MLP2(x1, . . . , x6)|
Please describe how to do this. (Hint: use mixed-integer programming).
5 Problem 5 (15 marks)
We mentioned quite a number of theoretical computational problems: TSP,
vertex cover, bin packing, knapsack, SAT, etc.
2
Pick one theoretical model mentioned in this course, and search for existing
research papers that use machine learning (for example, deep learning) as the
main solution tool. Write a one-page summary. You could pick just one paper
and do an in-depth summary, or pick a few papers and do a high-level summary.
Recommend paper selection criteria:
• Publications from the following conferences: NeurIPS, ICML, ICLR, AAAI,
IJCAI
• Don’t pick a paper that is too old
• Choose something “niche” (it’d be more fun)
• Don’t take everything claimed in a paper to be the truth, even if we
are talking about papers published in top-quality venues. (One paper
worth reading is “What’s Wrong with Deep Learning in Tree Search for
Combinatorial Optimization” – it shows that some past results from high-
profile papers/authors are not reproducible.)