TRADE|marketing|commercial transaction|sale|auction sale
- algartam ceant Tagairt Faomhadh an téarma seo mar chuid de Thionscadal Lex
- ga
- auction algorithm
- en
- Sainmhíniú intuitive method for solving the classical assignment problem Tagairt "Dimitri P. Bertsekas. 'Auction Algorithms' (23.11.2021). Laboratory for Information and Decision Systems Massachusetts Institute of Technology"
- Nóta In the classical assignment problem there are n persons and n objects that we have to match on a one-to-one basis. The assignment problem is important in many practical contexts. The most obvious ones are resource allocation problems, such as assigning personnel to jobs, machines to tasks, and the like. The classical methods for assignment are based on iterative improvement of some cost function; for example a primal cost (as in primal simplex methods), or a dual cost (as in Hungarian-like methods, dual simplex methods, and re-laxation methods). The auction algorithm departs significantly from the cost improvement idea; at any one iteration, it may deteriorate both the primal and the dual cost, although in the end it finds an optimal assignment. It is based on a notion of approximate optimality, called ²-complementary slackness, and while it implicitly tries to solve a dual problem, it actually attains a dual solution that is not quite optimal.