Combinatorial Optimization
Explore discrete structures; network algorithms; complexity and approximations. Concepts and connections are available independently of video coverage.
FOLLOW AN IDEA
Integer relaxations
Removing integrality yields easier problems whose optima can bound the discrete optimum.
Explore concept graph · Explore connected videos
Different ways to understand it
No reviewed video yet. Explore the concept in a map or suggest a resource. Suggest a video
More concepts to explore
Approximation algorithms
An approximation algorithm provides a provable ratio to the optimum under stated assumptions.
Traveling salesman routing
Visit each site once at least tour length; heuristics plus bounds are the practical modelling answer.
Assignment problem
A costed one-to-one pairing can be optimized using matching or linear programming structure.
Bipartite matching
Matching in a two-part graph pairs vertices across parts without shared endpoints.
Graph matchings
A matching is a set of edges with no shared endpoints.
Knowledge connections
- Approximation algorithms · Related · Map context
- Traveling salesman routing · Related · Map context