= Combinatorial optimization
{wiki}
<Combinatorial optimization> minimizes or maximizes an <objective function> over discrete structures such as <graph paths>, <graph matchings>, <trees> or <permutations>. A weighted <minimum spanning tree> problem, for example, chooses a tree connecting all vertices and minimizes the sum of its edge weights.
The number of feasible structures can be enormous, but this alone does not prove computational hardness. Minimum spanning trees admit efficient greedy <algorithms>, whereas the general <travelling salesman problem> is <NP-hard>. The useful question is which structural properties allow an <algorithm> to certify an optimum without explicitly listing every feasible object. Relaxations, <dynamic programming> and <approximation algorithms> exploit different kinds of structure.
Back to article page
