A forward/reverse auction algorithm for asymmetric assignment problems
- Published: December 1992
- Volume 1 , pages 277–297, ( 1992 )
Cite this article
- Dimitri P. Bertsekas 1 &
- David A. Castañon 2 , 3
422 Accesses
61 Citations
3 Altmetric
Explore all metrics
In this paper we consider the asymmetric assignment problem and we propose a new auction algorithm for its solution. The algorithm uses in a novel way the recently proposed idea of reverse auction, where, in addition to persons bidding for objects by raising their prices, we also have objects competing for persons by essentially offering discounts. In practice, the new algorithm apparently deals better with price wars than the currently existing auction algorithms. As a result, it tends to terminate substantially (and often dramatically) faster than its competitors.
This is a preview of subscription content, log in via an institution to check access.
Access this article
Price excludes VAT (USA) Tax calculation will be finalised during checkout.
Instant access to the full article PDF.
Rent this article via DeepDyve
Institutional subscriptions
Similar content being viewed by others
Auctions (Theory)
The assignment problem revisited
D.P. Bertsekas, “A distributed algorithm for the assignment problem,” Lab. for Information and Decision Systems Working Paper, M.I.T., Cambridge, MA, March, 1979.
Google Scholar
D.P. Bertsekas, “A distributed asynchronous relaxation algorithm for the assignment problem,” Proc. 24th IEEE Conf. Dec. & Contr., pp. 1703–1704, 1985.
D.P. Bertsekas, “The auction algorithm: A distributed relaxation method for the assignment problem,” Ann. Oper. Res. vol. 14, pp. 105–123, 1988.
D.P. Bertsekas, “The auction algorithm for assignment and other network flow problems: A tutorial,” Interfaces, vol. 20, pp. 133–149, 1990.
D.P. Bertsekas, Linear network optimization: Algorithms and codes, M.I.T. Press, Cambridge, MA, 1991.
D.P. Bertsekas, and D.A. Castañon, “Parallel synchronous and asynchronous implementations of the auction algorithm,” Alphatech Report, Burlington, MA, November, 1989 (also Parallel Comput. vol. 17, pp. 707–732, 1991).
D.P. Bertsekas, D.A. Castañon, and H. Tsaknakis, “Reverse auction and the solution of inequality constrained assignment problems,” Alphatech Report, Burlington, MA, March 1991; to appear in SIAM J. on Optimization.
D.P. Bertsekas, and J. Eckstein, “Dual coordinate step methods for linear network flow problems,” Math. Progr., Series B, vol. 42, pp. 203–243, 1988.
D.A. Castañon, “Reverse auction algorithms for assignment problems,” to appear in DIMACS Series in Discrete Math. and Comput. Sci.
D. Kempa, J. Kennington, and H. Zaki, “Performance characteristics of the Jacobi and Gauss-Seidel versions of the auction algorithm on the Alliant FX/8,” Report OR-89–008, Dept. of Mech. and Ind. Engg., Univ. of Illinois, Champaign-Urbana, IL, 1989.
J. Kennington, and R. Helgason, Algorithms for network programming, Wiley, New York, NY, 1980.
C.H. Papadimitriou, and K. Steiglitz, Combinatorial optimization: Algorithms and complexity, Prentice-Hall, Englewood Cliffs, NJ, 1982.
C. Phillips, and S.A. Zenios, “Experiences with large scale network optimization on the connection machine”, Report 88–11–05, Dept. of Decision Sci., The Wharton School, Univ. of Pennsylvania, Philadelphia, PA, November, 1988.
R.T. Rockafellar, Network flows and monotropic programming, Wiley-Interscience, New York, NY, 1984.
J. Wein, and S.A. Zenios, “Massively parallel auction algorithms for the assignment problem,” Proc. of 3rd Symp. on the Frontiers of Massively Parallel Computation, MD., pp. 90–99, November, 1990.
J. Wein, and S.A. Zenios, “On the massively parallel solution of the assignment problem,” J. of Parallel and Distributed Comput., vol. 13, pp. 228–236, 1991.
H. Zaki, “A comparison of two algorithms for the assignment problem,” Report ORL 90-002, Dept. of Mech. and Ind. Eng., Univ. of Illinois, Urbana, Ill.
Download references
Author information
Authors and affiliations.
Department of Electrical Engineering and Computer Science, M.I.T., 02139, Cambridge, Mass., USA
Dimitri P. Bertsekas
Department of Electrical Engineering, Boston University, 01803, Burlington, Mass., USA
David A. Castañon
ALPHATECH, Inc., 01803, Burlington, Mass., USA
You can also search for this author in PubMed Google Scholar
Rights and permissions
Reprints and permissions
About this article
Bertsekas, D.P., Castañon, D.A. A forward/reverse auction algorithm for asymmetric assignment problems. Comput Optim Applic 1 , 277–297 (1992). https://doi.org/10.1007/BF00249638
Download citation
Received : 19 April 1992
Revised : 12 August 1992
Issue Date : December 1992
DOI : https://doi.org/10.1007/BF00249638
Share this article
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative
- auction algorithm
- network programming
- optimization
- Find a journal
- Publish with us
- Track your research
A forward/reverse auction algorithm for asymmetric assignment problems
- Arizona State University
- Boston University
- This person is not on ResearchGate, or hasn't claimed this research yet.
Discover the world's research
- 25+ million members
- 160+ million publication pages
- 2.3+ billion citations
- Bodhisattva Sen
- Andrea Bracci
- Denis Shemonaev
- Anthony Besseau
- G A Rios-Esparza
- Guoqing Diao
- Ekaterina Merkurjev
- Selim Esedoglu
- Heinrich H. Nax
- H. Peyton Young
- Jonathan. Eckstein
- J OPER RES SOC
- Charles Whitlock
- J. L. Kennington
- Richard V. Helgason
- Hossam A. Zaki
- Recruit researchers
- Join for free
- Login Email Tip: Most researchers use their institutional email address as their ResearchGate login Password Forgot password? Keep me logged in Log in or Continue with Google Welcome back! Please log in. Email · Hint Tip: Most researchers use their institutional email address as their ResearchGate login Password Forgot password? Keep me logged in Log in or Continue with Google No account? Sign up
A forward/reverse auction algorithm for asymmetric assignment problems
Research output : Contribution to journal › Article › peer-review
In this paper we consider the asymmetric assignment problem and we propose a new auction algorithm for its solution. The algorithm uses in a novel way the recently proposed idea of reverse auction, where, in addition to persons bidding for objects by raising their prices, we also have objects competing for persons by essentially offering discounts. In practice, the new algorithm apparently deals better with price wars than the currently existing auction algorithms. As a result, it tends to terminate substantially (and often dramatically) faster than its competitors.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 277-297 |
| Number of pages | 21 |
| Journal | |
| Volume | 1 |
| Issue number | 3 |
| DOIs | |
| State | Published - Dec 1992 |
| Externally published | Yes |
- auction algorithm
- network programming
- optimization
ASJC Scopus subject areas
- Control and Optimization
- Computational Mathematics
- Applied Mathematics
Access to Document
- 10.1007/BF00249638
Other files and links
- Link to publication in Scopus
Fingerprint
- Auctions Mathematics 100%
- Assignment Problem Mathematics 83%
- Reverse Mathematics 69%
- Person Mathematics 36%
- Bidding Mathematics 28%
- Object Mathematics 24%
- Discount Mathematics 23%
- Terminate Mathematics 20%
T1 - A forward/reverse auction algorithm for asymmetric assignment problems
AU - Bertsekas, Dimitri P.
AU - Castañon, David A.
N1 - Copyright: Copyright 2007 Elsevier B.V., All rights reserved.
PY - 1992/12
Y1 - 1992/12
N2 - In this paper we consider the asymmetric assignment problem and we propose a new auction algorithm for its solution. The algorithm uses in a novel way the recently proposed idea of reverse auction, where, in addition to persons bidding for objects by raising their prices, we also have objects competing for persons by essentially offering discounts. In practice, the new algorithm apparently deals better with price wars than the currently existing auction algorithms. As a result, it tends to terminate substantially (and often dramatically) faster than its competitors.
AB - In this paper we consider the asymmetric assignment problem and we propose a new auction algorithm for its solution. The algorithm uses in a novel way the recently proposed idea of reverse auction, where, in addition to persons bidding for objects by raising their prices, we also have objects competing for persons by essentially offering discounts. In practice, the new algorithm apparently deals better with price wars than the currently existing auction algorithms. As a result, it tends to terminate substantially (and often dramatically) faster than its competitors.
KW - Assignment
KW - auction algorithm
KW - network programming
KW - optimization
UR - http://www.scopus.com/inward/record.url?scp=0026997991&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0026997991&partnerID=8YFLogxK
U2 - 10.1007/BF00249638
DO - 10.1007/BF00249638
M3 - Article
AN - SCOPUS:0026997991
SN - 0926-6003
JO - Computational Optimization and Applications
JF - Computational Optimization and Applications
- DOI: 10.1137/0803013
- Corpus ID: 9958077
Reverse Auction and the Solution of Inequality Constrained Assignment Problems
- D. Bertsekas , D. Castañón , H. Tsaknakis
- Published in SIAM Journal on Optimization 1 May 1993
- Mathematics, Computer Science
Figures from this paper
66 Citations
A forward/reverse auction algorithm for asymmetric assignment problems, new auction algorithms for the assignment problem and extensions, auction algorithms for network flow problems: a tutorial introduction.
- Highly Influenced
The equivalence between two classic algorithms for the assignment problem
Towards auction algorithms for large dense assignment problems, a generic auction algorithm for the minimum cost network flow problem, descending price algorithm for determining market clearing prices in matching markets, a descending price auction for matching markets, revisiting the auction algorithm for weighted bipartite perfect matchings, fully distributed auction algorithm for spectrum sharing in unlicensed bands, 35 references, the auction algorithm for assignment and other network flow problems, mathematical equivalence of the auction algorithm for assignment and the ∊-relaxation (preflow-push) method for min cost flow, the auction algorithm: a distributed relaxation method for the assignment problem, the auction algorithm for the minimum cost network flow problem, a computational analysis of the auction algorithm, a comparison of two algorithms for the assignment problem, massively parallel auction algorithms for the assignment problem, a distributed asynchronous relaxation algorithm for the assignment problem, distributed relaxation methods for linear network flow problems, parallel synchronous and asynchronous implementations of the auction algorithm, related papers.
Showing 1 through 3 of 0 Related Papers
Network optimization – auction algorithms
Repository files navigation
Programming Assignment #3 of Network Optimization Course.
Auction Algorithm for Symmetric and Assymetric Type of Assignment Problems.
Algorithm Conforming to Chapter 7 of the book "Network Optimization: Continuous and Discrete Models" by Dimitri P. Bertsekas, Massachusetts Institute of Technology.
- Python 100.0%
IMAGES
VIDEO
COMMENTS
similarly combining forward and reverse auction. The purpose of this paper is to develop auction algorithms for asymmetric assignment problems that switch frequently between forward and reverse auction. Our computational results show that for difficult problem structures, some of which typically arise in important.
3. A Forward/Reverse Auction Algorithm for Asymmetric Assignment Problems The algorithms terminate when S becomes feasible and in addition all unassigned objects j satisfy p j ≤ λ. Thus upon termination, in view of Eq. (3), the third †-CS condition (2c) is satisfied and by Prop. 1, the assignment S is optimal if † < 1/m and the benefits a
In this paper we consider the asymmetric assignment problem and we propose a new auction algorithm for its solution. The algorithm uses in a novel way the recently proposed idea of reverse auction, where, in addition to persons bidding for objects by raising their prices, we also have objects competing for persons by essentially offering discounts. In practice, the new algorithm apparently ...
FOR ASYMMETRIC ASSIGNMENT PR OBLEMS 1. by. Dimitri P. Bertsekas 2and David A. Casta˜non3. Abstract. In this paper we consider the asymmetric assignment problem and we propose a new auction ...
Sec. 2.1 The Auction Algorithm for the Symmetric Assignment Problem 3 2.1.1 The Main Auction Algorithm We recall the auction algorithm, described in Section 1.4.1. It was moti-vated by the simpler but awed naive auction algorithm. A key notion, which made possible the correct operation of the algorithm was the -
In this paper we consider the asymmetric assignment problem and we propose a new auction algorithm for its solution. The algorithm uses in a novel way the recently proposed idea of reverse auction, where, in addition to persons bidding for objects by raising their prices, we also have objects competing for persons by essentially offering discounts.
A forward/reverse auction algorithm for asymmetric assignment problems. dc.contributor: Bertsekas, Dimitri P. en_US: dc.contributor: Castañon, David A. en_US: ... A forward/reverse auction algorithm for asymmetric assignment problems: en_US Files in this item. Name: P-2159-27790376.pdf Size: 1.288Mb Format: PDF.
Author (s) Bertsekas, Dimitri P.; Castañon, David A.; Massachusetts Institute of Technology. Laboratory for Information and Decision Systems. Download P-2159-27790376.pdf (1.288Mb)
for the objects. Auction algorithms for asymmetric and other related assignment problems will be discussed in Section 9. The assignment problem is important in many practical contexts, but it is also of great theoretical importance. Despite its simplicity, it embodies a fundamental linear programming structure.
forward and reverse auction, we eliminate this drawback. In particular, we give a new auction algorithm for solving the asymmetric assignment problem, where the starting object prices can be arbitrary, so that †-scaling can be used in the same way as for symmetric problems.
3. A Forward/Reverse Auction Algorithm for Asymmetric Assignment Problems The algorithms terminate when S becomes feasible and in addition all unassigned objects j satisfy pi < A. Thus upon termination, in view of Eq. (3), the third e-CS condition (2c) is satisfied and by Prop.
This paper considers the asymmetric assignment problem and proposes a new auction algorithm that uses in a novel way the recently proposed idea of reverse auction, where, in addition to persons bidding for objects by raising their prices, objects competing for persons by essentially offering discounts. In this paper we consider the asymmetric assignment problem and we propose a new auction ...
Let us describe the conservative auction algorithm more precisely. The algorithm proceeds in iterations and throughout its operation, maintains a set of prices p = (p 1, …, p n) and a partial assignment A where each assigned person is assigned to a maximal profit object, i.e., the CS condition (1) is satisfied. It terminates when following an iteration, the assignment obtained is complete.
We will also show how two classes of algorithms, the auction algorithms and the push/relabel algorithms, are related. In Chapter 4, we modify one of these algorithms, the auction algorithm, to efficiently solve a generalisation of the assignment problem, namely the asymmetric assignment problem, where one set is allowed to be larger than the other.
This paper proposes auction algorithms for solving several types of assignment problems with inequality constraints, including asymmetric problems with dierent numbers of persons and objects, and multiassignment problems, where persons may be assigned to several objects and reversely. In this paper we propose auction algorithms for solving several types of assignment problems with inequality ...
the auction algorithm for the assignment problem. This is an intuitive method that operates like a real ... Auction algorithms for asymmetric and other related assignmment problems will be discussed in Section 9. The assignment problem is important in many practical contexts, but it is also of great theoretical importance. Despite its ...
3) AUCTION_AS: Auction algorithm for asymmetric assignment problems. 4) AUCTION_FR: Forward/reverse auction algorithm for symmetric assignment problems. 5) NAUCTION_SP: Combined naive auction and sequential shortest path method for assignment. The codes include a built-in random problem generator. This generator can be replaced by other code ...
[10] . Auction algorithms were extended to solve the transportation problem [11] , the minimum cost flow problem [12] − [14] and the shortest path problem [15] . In the 1990s, many sequential methods for the assignment problem (especially auction, shortest path-based Hungarian method, and primal simplex algorithms) have been parallelized
cost flow problem and its various special cases (e.g., shortest path, max-flow, etc.) to equivalent assignment problems. Once the auction algorithm is applied to the corresponding equivalent assignment problem and the computations are streamlined, one obtains an auction algorithm for the original problem.
the auction algorithm for the assignment problem. This is an intuitive method that operates like a real ... Auction algorithms for asymmetric and other related assignmment problems will be discussed in Section 9. The assignment problem is important in many practical contexts, but it is also of great theoretical importance. Despite its ...
The algorithm implements the Gauss-Siedel asymmetric forward-reverse auction process described originally by Bertsekas, 1993. See the included papers for details, as the algorithm is quite complicated.
D. P. Bertsekas, "A New Algorithm for the Assignment Problem," Mathematical Programming, Vol. 21, pp. 152-171, 1981. Contains the naive version of the auction algorithm (which does not use epsilon), and its combination with the Hungarian method (this is the basis for the widely used JV code for linear assignment problems).
Algorithm Conforming to Chapter 7 of the book "Network Optimization: Continuous and Discrete Models" by Dimitri P. Bertsekas, Massachusetts Institute of Technology. About Auction Algorithm for symmetric and asymmetric type assignment problems