Chapter 6 Combinatorial Optimisation Flashcards
(17 cards)
What is combinatorial optimisation?
Solving problems where the goal is to choose the best combination from a discrete set of options, often under constraints.
Why can’t calculus-based optimisation be used in combinatorial problems?
Because the choices are discrete and don’t have derivatives, making root-finding and gradient methods inapplicable.
What is a greedy algorithm?
An algorithm that makes the best local choice at each step with the hope of finding a global optimum.
What are the key properties of greedy algorithms?
Safe choices, optimal substructure, and only one subproblem to solve after each decision.
What is the activity selection problem?
Selecting the maximum number of non-overlapping activities based on start and finish times.
Why does a greedy solution work for the activity selection problem?
Because selecting the earliest finishing activity always leaves the most room for subsequent ones, ensuring an optimal solution.
What is a minimum spanning tree (MST)?
A subset of a graph’s edges that connects all vertices with the minimum total edge weight and no cycles.
Which greedy algorithms are used for MST?
Prim’s and Kruskal’s algorithms.
What is the safe edge theorem in MST?
A light edge crossing a cut that respects the current tree is safe to add and part of some MST.
What is the 0-1 knapsack problem?
Selecting a subset of items with given weights and values to maximize value without exceeding capacity, where each item is either taken or not.
Why doesn’t a greedy approach work for the 0-1 knapsack problem?
Because selecting items by value-per-weight ratio may miss combinations that provide higher total value.
What is simulated annealing?
A heuristic algorithm that explores the solution space by probabilistically accepting worse solutions to escape local optima, inspired by cooling in metallurgy.
How does temperature affect simulated annealing?
Higher temperatures allow more exploration; lower temperatures focus the search and help converge to a solution.
What is a stable matching?
A matching where no pair prefers each other over their current matches.
What is the Gale-Shapley algorithm?
An iterative algorithm that produces a stable matching by letting one side propose to their preferences and adjusting engagements based on mutual rankings.
What is Pareto optimality in matching?
A state where no individual can be made better off without making someone else worse off.
What is beam search?
A search algorithm that expands the best k nodes at each level of a search tree to find an optimal or near-optimal solution.
