Auction Algorithm: Difference between revisions
Jump to navigation
Jump to search
Andrewgracyk (talk | contribs) No edit summary |
Andrewgracyk (talk | contribs) No edit summary |
||
| Line 3: | Line 3: | ||
==The Assignment Problem== | ==The Assignment Problem== | ||
We begin by discussing the assignment problem. Consider the specialized case when weights <math> a_i </math> and <math> b_j </math> are equal. Suppose we have <math> N </math> buyers, denoting the index with <math> i </math>, and <math> N </math> goods to be bought, denoted by <math> j </math>. We look for an assignment <math> j = \sigma(i), \sigma \in S_N </math> | We begin by discussing the assignment problem. Consider the specialized case when weights <math> a_i </math> and <math> b_j </math> are equal. Suppose we have <math> N </math> buyers, denoting the index with <math> i </math>, and <math> N </math> goods to be bought, denoted by <math> j </math>. We look for an assignment <math> j = \sigma(i), \sigma \in S_N </math> which maximizes <math> \sum_{i} </math> | ||
Revision as of 03:17, 5 May 2020
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 and are equal. Suppose we have buyers, denoting the index with , and goods to be bought, denoted by . We look for an assignment which maximizes
