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.
Articles by others on the same topic
Combinatorial optimization is a branch of optimization in mathematics and computer science that deals with problems where the objective is to find an optimal solution from a finite set of possible solutions. These problems often involve discrete structures, such as graphs, integers, or combinations of sets. Key features of combinatorial optimization include: 1. **Discrete Solutions**: Unlike continuous optimization, which deals with real-valued variables, combinatorial optimization focuses on scenarios where the solutions are discrete or combinatorial in nature.