# Reducing optimization problem to its decision version

There are two problems that need to be solved. Both problems use a compatibility matrix $$C$$, where $$C[a, b]$$ is how compatible students $$a$$ and $$b$$ are.

(1) Given an $$n \times n$$ compatibility matrix $$C$$ for $$n$$ students, and $$r$$ rooms with sizes $$s_1, s_2, \dots, s_r$$, where $$n$$ is the sum of room sizes, and a target $$A$$; determine if there is some assignment of the students to the rooms with average compatibility value at least $$A$$.

(2) Given an $$n \times n$$ compatibility matrix $$C$$ for $$n$$ students, and $$r$$ rooms with sizes $$s_1, s_2, \dots, s_r$$, where $$n$$ is the sum of room sizes; find an optimal assignment of the students to the rooms.

These two problems seem to be hard to solve efficiently. Not surprisingly, your manager asks you to write programs to solve the two problems. As usual you have no idea how to write such programs. For both problems, you find an efficient program on the Internet that solves that problem. Unfortunately your budget will only allow you to buy one such program.

1. Assume that you have a program that solves the second problem in time $$\Theta(n^j)$$, for $$j ≥ 1$$. Can you use it to solve the first problem in polynomial time? If so, how, and how fast is your algorithm?

2. Assume that you have a program that solves the first problem in time $$\Theta(n^k)$$, for $$k ≥ 1$$. Can you use it to solve the second problem in polynomial time? If so, how, and how fast is your algorithm

I understand how to do problem 15, but for problem 16, I have no idea.

Use binary search on the target $$A$$, finding the maximal value for which an assignment of average compatibility $$A$$ exists.