In this final chapter, we return to the small problems outlined at the beginning of this book.

## 12.1. The swing state problem

1. *What kind of combinatorial optimization problem is the “swing state” problem in relation with?*

The candidate has an overall budget of $ 500 k, comparable to a capacity *C* . He must, therefore, choose which states he must invest in, knowing that each state *i* ∈ *I* has a value *v*_{i}, which corresponds to the number of voters that he will bring in, and a cost *m*_{i}. The objective is to maximize the summation of the value of all the chosen states, without exceeding the capacity. We can recognize the knapsack problem.

2. *Determine a criterion according to which the states can be ranked from most interesting to least interesting. Deduce a construction heuristic from this and give its principle. What solution do you find?*

We will define as a saturated solution one for which it is not possible to add new states without violating the capacity constraint. The purpose of this question is to find a criterion that helps to sort states out. The order thus defined will allow determining which states will be selected through a greedy heuristic.

Three sorting criteria can be proposed:

- – prioritizing states that require smaller investments (cost criterion);
- – prioritizing states that give the most electoral votes (value criterion);
- – prioritizing states where the investment per electoral vote obtained is the largest (ratio criterion).

The last criterion ...