6
$\begingroup$

In which time complexity operates the Savings algorithm from Clarke and Wright for the TSP? I mean the parallel version of Savings. I think it is in $\mathcal O(|V|\log|V|)$ with V as vertex/node because the most complex operation is sorting the savings which operate in this time for, e.g. Quicksort. The rest operates, I think, in linear time. Is this right, and is there something on the internet that covers this?

$\endgroup$

1 Answer 1

4
$\begingroup$

You might want to read the paper DIFFERENT VERSIONS OF THE SAVINGS METHOD FOR THE TIME LIMITED VEHICLE ROUTING PROBLEM[1] which gives time complexities between $O(n^3)$ and $O(n^2\log(n))$ note that in these complexity analysis the number of nodes not nodes as $n$. The reason why it is $n^2$ and not $n$ is this part of the algorithm: enter image description here Taken from EOR 151 – Lecture 18 Savings Algorithm page 1

The number of savings grows $O(n^2)$ (actually like $n(n+1)/2$) so sorting that leads to $O(n^2\log(n^2)) = O(2n^2\log(n)) = O(n^2\log(n))$ time complexity unless a non-comparison based sorting like trie/radix/couting sort is used.

$\endgroup$
3
  • $\begingroup$ V is the set of vertices or nodes. So n=|V|. This would not agree with the complexity that I proposed. Why does the sorting take longer than O(|V|log|V|)? $\endgroup$
    – maxmitz
    Sep 17, 2021 at 7:41
  • $\begingroup$ Sorry i confused vertices for edges. $\endgroup$ Sep 17, 2021 at 7:47
  • 1
    $\begingroup$ @Theodeo my newest edit should make it clear while sorting takes $O(|s|*log(|s|))$ where $|s|$ is the number of savings and $|s|$ is in $O(n^2)$ $\endgroup$ Sep 17, 2021 at 7:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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