GitHunt
EV

EvanOman/AuctionAlgorithmScala

Scala Implementation of Bertsekas' Auction Algorithm

Auction Algorithm Scala

This is a repo contains a Scala implementation of Bertsekas's Auction Algorithm. The algorithm solves the problem of optimally assigning M objects to N people given the preferences specified in a given cost matrix.

After a bit of optimization, this implementation can solve a size 500 assignment problem in ~.125 seconds. I have also implemented a parallel version, which seems to outperform the sequential version once the problem size is over 5000. This implementation is still being optimized.

Languages

Scala100.0%

Contributors

Created June 23, 2016
Updated June 29, 2022