Examples
Some problems where local search has been applied are:
- The vertex cover problem, in which a solution is a vertex cover of a graph, and the target is to find a solution with a minimal number of nodes
- The travelling salesman problem, in which a solution is a cycle containing all nodes of the graph and the target is to minimize the total length of the cycle
- The boolean satisfiability problem, in which a candidate solution is a truth assignment, and the target is to maximize the number of clauses satisfied by the assignment; in this case, the final solution is of use only if it satisfies all clauses
- The nurse scheduling problem where a solution is an assignment of nurses to shifts which satisfies all established constraints
- The k-medoid clustering problem and other related facility location problems for which local search offers the best known approximation ratios from a worst-case perspective
Read more about this topic: Local Search (optimization)
Famous quotes containing the word examples:
“Histories are more full of examples of the fidelity of dogs than of friends.”
—Alexander Pope (1688–1744)
“In the examples that I here bring in of what I have [read], heard, done or said, I have refrained from daring to alter even the smallest and most indifferent circumstances. My conscience falsifies not an iota; for my knowledge I cannot answer.”
—Michel de Montaigne (1533–1592)
“It is hardly to be believed how spiritual reflections when mixed with a little physics can hold people’s attention and give them a livelier idea of God than do the often ill-applied examples of his wrath.”
—G.C. (Georg Christoph)