0
$\begingroup$

I am attempting to find the best path from start to finish from a set of points. Say that one path has costs $x_1,x_2,...,x_n$ and $y_1,y_2,...,y_n$ associated with it. I am attempting to find the path such that $$S = (\sum_{i=1}^n x_i)^3+(\sum_{i=1}^n y_i)^3$$ is minimized.

I am trying to find a way to approximate the problem by making it linear, which would make my application much easier to work with. Though not mathematically equivalent, my intuition tells me that if I simply minimize $$S = \sum_{i=1}^n x_i+\sum_{i=1}^n y_i$$

I will have an approximate solution to the original problem. My question is whether this is a good heuristic, and if there is a way to quantify how close this approximation would be. What would the limitations of this approximation be? If this would not work, is there any other way to approximate it that would work for a decent number of test cases?

$\endgroup$
1
$\begingroup$

Minimizing $S$ is equivalent to minimizing $S^3.$ Write $X$ for the first sum and $Y$ for the second then you are effectively replacing $X^3+Y^3$ with $(X+Y)^3.$ Up to a constant (which does not influence optimisation) the difference is $3XY(X+Y).$

This is all we can say about the 'quality' of the approximation as long as no probability distribution on the $x_i, y_i$ is assumed.

If you want other approximations then you should first elaborate why the 'real' value is difficult to compute and you need an approximation in the first place.

$\endgroup$
  • $\begingroup$ I am seeing how well minimizing $X + Y$ approximates minimizing $X^3+Y^3$, not using $(X+Y)^3$ to approximate $X^3+Y^3$. The reason I am trying to linearize the problem is because I am attempting to find the shortest cost path on a graph, and doing this is trivial if I can treat $x+y$ as a single cost on an edge. $\endgroup$ – flubsy Dec 6 '15 at 21:09
  • 1
    $\begingroup$ Understood. Note that $x\mapsto x^3$ is monotonous so minimizing $X+Y$ is the same as minimizing $(X+Y)^3.$ $\endgroup$ – Justpassingby Dec 6 '15 at 22:53

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.