What is the difference between a "combinatorial algorithm" and a "linear algorithm"?

Question

Or rather, what is the definition of a combinatorial algorithm and a linear algorithm, respectively?

To be clear, because, obviously, the first respondents misunderstood the question: I am not looking for a definition of an algorithm that runs in linear time compared to non-linear time. The linear algorithm is somehow related to linear programming, which is a method of searching or approximating solutions to linear optimization problems.

Since the problems with NP-difficulty are so complex, there is a whole area trying to find approximate solutions. For example, the traveling salesman problem has several approximate solutions that are executed in polynomial time and create a solution that is within the specified boundary of the best solution.

Some of these approximating algorithms are called a linear algorithm, others are called a combinatorial algorithm; and the latter seems preferable (why?). These are two concepts that I would like to understand.

Answer 1

The problem is the problem statement.

, Traveling Salesperson (TSP) NP-hard , ( , ). , . (, NP-, .)

TSP (LP) . , , . LP , . .

Answer 2

: " a, b". a

- " a b ". - a b.

Answer 3

Combinatorial algorithms explode as their input grows. Linear algorithms grow in proportion to their input signal, and combinatorial algorithms grow in proportion to exponential (or worse) or their input: listing all possible paths through a graph, for example.