## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

# 12Solution to Problems

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 iI has a value vi, which corresponds to the number of voters that he will bring in, and a cost mi. 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:

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

The last criterion ...

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required