Methods
There is a large amount of literature on polynomial-time algorithms for certain special classes of discrete optimization, a considerable amount of it unified by the theory of linear programming. Some examples of combinatorial optimization problems that fall into this framework are shortest paths and shortest path trees, flows and circulations, spanning trees, matching, and matroid problems.
For NP-complete discrete optimization problems, current research literature includes the following topics:
- polynomial-time exactly solvable special cases of the problem at hand (e.g. see fixed-parameter tractable)
- algorithms that perform well on "random" instances (e.g. for TSP)
- approximation algorithms that run in polynomial time and find a solution that is "close" to optimal
- solving real-world instances that arise in practice and do not necessarily exhibit the worst-case behavior inherent in NP-complete problems (e.g. TSP instances with tens of thousands of nodes).
Combinatorial optimization problems can be viewed as searching for the best element of some set of discrete items, therefore, in principle, any sort of search algorithm or metaheuristic can be used to solve them. However, generic search algorithms are not guaranteed to find an optimal solution, nor are they guaranteed to run quickly (in polynomial time). Since some discrete optimization problems are NP-complete, such as the traveling salesman problem, this is expected unless P=NP.
Read more about this topic: Combinatorial Optimization
Famous quotes containing the word methods:
“A writer who writes, “I am alone” ... can be considered rather comical. It is comical for a man to recognize his solitude by addressing a reader and by using methods that prevent the individual from being alone. The word alone is just as general as the word bread. To pronounce it is to summon to oneself the presence of everything the word excludes.”
—Maurice Blanchot (b. 1907)
“I conceive that the leading characteristic of the nineteenth century has been the rapid growth of the scientific spirit, the consequent application of scientific methods of investigation to all the problems with which the human mind is occupied, and the correlative rejection of traditional beliefs which have proved their incompetence to bear such investigation.”
—Thomas Henry Huxley (1825–95)
“With a generous endowment of motherhood provided by legislation, with all laws against voluntary motherhood and education in its methods repealed, with the feminist ideal of education accepted in home and school, and with all special barriers removed in every field of human activity, there is no reason why woman should not become almost a human thing. It will be time enough then to consider whether she has a soul.”
—Crystal Eastman (1881–1928)