Take the 2-minute tour ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.

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.

share|improve this question

3 Answers 3

up vote 2 down vote accepted

The issue is one of problem formulation.

Just as you said Traveling Salesperson Problem (TSP) is NP-hard precisely because it has a discrete problem formulation (the salesperson either visits a city or not at a particular time). This discrete formulation makes the problem, and it's algorithm, combinatorial. (Note that not all combinatorial problems are NP-hard; consider sorting algorithms.)

However, the Linear-Programming (LP) relaxation of TSP results in a linear algorithm. This is because the problem has been reformulated such that the salesperson visits a city a certain proportion of the time. The main reason for using an LP relaxation is because the relaxed version can be solved in polynomial time. However, the solution to the LP relaxation is not necessarily a solution to the original problem.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.
{"cc_re__cc_re__cc_by_sa_3_0": ["                  <li><a href=\"//area51.stackexchange.com\" title=\"proposing new sites in the Stack Exchange network\">Area 51</a></li>\r\n                        <li><a href=\"//careers.stackoverflow.com\">Stack Overflow Careers</a></li>\r\n                    \r\n                </ol>\r\n            </td>\r\n    </tr>\r\n</table>\r\n                </div>\r\n            </div>\r\n\r\n            <div id=\"copyright\">\r\n                site design / logo &#169; 2015 stack exchange inc; user contributions licensed under <a href=\"http://creativecommons.org/licenses/by-sa/3.0/\" rel=\"license\">cc by-sa 3.0</a>                   with <a href=\"http://blog.stackoverflow.com/2009/06/attribution-required/\" rel=\"license\">attribution required</a>\r\n            </div>\r\n            <div id=\"svnrev\">\r\n                rev 2015.1.25.2220\r\n            </div>\r\n            \r\n        </div>\r\n    </div>\r\n    <noscript>\r\n        <div id=\"noscript-warning\">Stack Overflow works best with JavaScript enabled<img src=\"http://pixel.quantserve.com/pixel/p-c1rF4kxgLUzNc.gif\" alt=\"\" class=\"dno\"></div>\r\n    </nos"], "copyright__copyright__copyright": ["ve this answer\n\nCombinatorial 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.\n\nshare|improve this answer\n\nYour Answer\n\n\u00a0\ndiscard\n\nBy posting your answer, you agree to the privacy policy and terms of service.\n\nNot the answer you're looking for? Browse other questions tagged or ask your own question."]}