Auction Algorithm

The auction algorithm is an algorithm connected to the dual problem, but it is not based on a sequence of improvements of the dual objective function. Instead, it attempts to seek an equilibrium. Because of such, the algorithm has applications in economics.

The Assignment Problem

We begin by discussing the assignment problem. Consider the specialized case when weights $a_{i}$ and $b_{j}$ are equal. Suppose we have $N$ buyers, denoting the index with $i$, and $N$ goods to be bought, denoted by $j$. We look for an assignment $j=\sigma (i),\sigma \in S_{N}$ which maximizes $\sum _{i}$