0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

I'll let you work out the resulting multiplicative overhead (which depends on the magnitude of the numbers involved).

$\endgroup$
  • $\begingroup$ Is it still polynomial time though? $\endgroup$ – Mike Deng Dec 9 '18 at 0:41
  • $\begingroup$ I'll let you work that out. $\endgroup$ – Yuval Filmus Dec 9 '18 at 0:41
  • $\begingroup$ I still don't get it. How can you decide how much to increase/decrease the value of A? And when you reach the maximal, how can you find the optimal assignment? More detail will really be appreciated. $\endgroup$ – Mike Deng Dec 9 '18 at 2:04
  • $\begingroup$ For your second question, this requires an additional step using the “self-reducibility” of your problem. I suspect that the question is stated incorrectly, and you are only supposed to find the optimal value, not an optimal solution; but in any case, finding the optimal value is the first step. $\endgroup$ – Yuval Filmus Dec 9 '18 at 2:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.