# What do you call a greedy algorithm that solves a combinatorial problem by optimizing the best k>1 choices altogether?

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.

• 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". – j_random_hacker Mar 24 at 18:44