2
$\begingroup$

We are given complete graph, such that each edge has two costs $a \text{ and } b$. We should find path that passes through each node once and has minimum total cost. Cost of a path is the maximum of both of the sums $a$ and $b$ of the edges laying on the edges crossed on the path.

One person told me that this is easily solvable by taking the maximum of $a \text { and } b$ for each edge and then using the dynamic programming technique storing the final index and the bitmask of visited nodes. I couldn't find a counter test case, however I'm not sure if this is correct approach.

$\endgroup$
  • $\begingroup$ Can you add a reference to the original problem? $\endgroup$ – Apass.Jack Jun 14 at 22:33
  • $\begingroup$ I don't have reference this time, since this was a problem I saw at one programming camp, however there wasn't any resource mentioned and the problems are not being published online. $\endgroup$ – someone12321 Jun 15 at 11:10
  • $\begingroup$ What is "the maximum of both of the sums 𝑎 and 𝑏 of the edges laying on the edges crossed on the path"? Can you add a simple non-trivial example in the question?? $\endgroup$ – Apass.Jack Jun 16 at 8:04
  • $\begingroup$ Say you choose one path (that goes through each node once) of the complete graph. On this path keep two variables, one is the sum of all a values on this path, and the other one is the sum of all b variables on this path. Then the cost of this path is the maximum of those two sums. $\endgroup$ – someone12321 Jun 16 at 8:12

Your Answer

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

Browse other questions tagged or ask your own question.