Вернее, каково определение комбинаторного алгоритма и линейного алгоритма, соответственно ??1001*
Чтобы было понятно, потому что, очевидно, первые респонденты неправильно поняли вопрос: я не ищу определение алгоритма, работающего в линейное время против нелинейного времени. Линейный алгоритм так или иначе связан с линейным программированием, которое представляет собой метод поиска или аппроксимации решений задач линейной оптимизации.
Поскольку NP-сложные задачи очень сложны, существует целая область, пытающаяся найти приблизительные решения. Например, задача коммивояжера имеет несколько приближенных решений, которые выполняются за полиномиальное время и дают решение, которое находится в заданных пределах наилучшего решения.
Некоторые из этих аппроксимирующих алгоритмов называются линейным алгоритмом, другие комбинаторным алгоритмом; и последнее кажется предпочтительным (почему?). Вот две концепции, которые я хотел бы понять.