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, resp.?

To make it clear because obviously the first responders misunderstood the question: I am not looking for a definition of an algorithm running in linear time vs non-linear time. A linear algorithm is somehow related to linear programming, which is a technique for finding or approximating solutions to linear optimization problems.

Since NP-hard problems are so hard, there is a whole field trying to find approximate solutions. The traveling salesman problem for instance has several approximate solutions which run in polynomial time and produce a solution which is within a given bound of the best solution.

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

Answer 1

A linear algorithm tends to work with just one set of data - 'Take all the numbers in set a, double them, and put the result in set b'. The number of operations is equal to the count of items in set a

A combinatorial one works on combinations of sets - 'For each number in set a, work out the sum of that number and each number in set b and print to screen'. The number of operations is the product of the size of set a and the size of set b.

Answer 2

Combinatorial algorithms "explode" as their input grows. Linear algorithms grows proportional to their input, while combinatorial algorithms grows proportional to an exponent (or worse) or their input: enumerating all possible paths through a graph, for example.