1
$\begingroup$

Suppose you have a problem which goal is to find the permutation of some set $S$ given in input that minimizes an objective function $f$ (for example the Traveling Salesman problem).

A trivial algorithm $E(S)$ that find the exact solution enumerates all the permutations and outputs the one that minimizes $f$. Its time complexity is $O(n!)$ where $n$ is the size of $S$.

A trivial greedy algorithm $G(S)$ that finds an approximation of the solution is:

out[0] = select a good starting item from S according to some heuristic h_1.
S = S - {out[0]}
for i=1 to n-1 do:
    out[i] = select the next best element using some heuristic h_2
    S = S - {out[i]}
return out

Where $h_1$ and $h_2$ are two heuristics. Its complexity in time is $O(n^2)$ assuming that $h_2$ runs in constant time.

Sometimes I mix the two techniques (enumeration and greedy) by selecting at each step the best $k$ items (instead of the best one) and enumerating all their permutations to find the one that locally minimizes $f$. Then I choose the best $k$ items among the remaining $n-k$ items and so on.

Here is the pseudocode (assuming $n$ is a multiple of $k$):

for i in 0 to n/k do:
    X = select the best k items of S according to some heuristic h
    S = S - X
    out[i*k ... (i+1)*k-1] = E(X)
return out

Where $E(X)$ is algorithm that find the exact solution applied on a subset $X \subset S$ rather than on the whole $S$. This last algorithm finds an approximate solution and has a time complexity of $O(\frac{n}{k}(n \log k + k! ))$ assuming that $h$ can be computed in constant time. This complexity can be comparable to $O(n^2)$ if $k$ is small although according to my experience the performances can be way better than the greedy approach.

I don't think I invented this kind of optimization technique: do you know its name? Can you please include some theoretical references?

I know for sure it is not beam search, because beam search never mixes the best $k$ solutions found at each step.

Thank you.

$\endgroup$
  • 1
    $\begingroup$ I don't know of a name for this kind of heuristic. A slightly different type of heuristic for finding an optimal permutation ( = TSP tour), in which an initial permutation is formed somehow and then all subsets of $k$ elements are optimally permuted (keeping the remaining $n-k$ items fixed), repeating until no subset of $k$ elements yields an improvement, is simply called "$k$-opt". $\endgroup$ – j_random_hacker Mar 24 at 18:44

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.