Полагаю, это относится к тому, дает ли алгоритм результат, который является оптимальным для данной задачи, или же он дает "просто" приблизительный результат.
Например, если вы ищете на графике кратчайший путь от одного узла к другому, существует множество алгоритмов ( Dijkstra , Floyd-Warshall , ... вы называете их), которые точно решают проблему, то есть они дают кратчайший путь между двумя заданными узлами.
С другой стороны, рассмотрим проблему Командующий . В нем сформулирован вопрос о кратчайшем круговом пути, содержащем несколько заданных узлов. Эта проблема является NP-полной и, таким образом (предположительно), не может быть решена точно в течение разумного периода времени (по крайней мере, для общего случая). Однако существуют алгоритмы аппроксимации, работающие в разумные сроки, которые дают решение, которое не более 2*length(best route) (по крайней мере, для метрической TSP), поэтому решение из этого алгоритма не является точным, а является лишь приближением.