search

gatagat / lap

Linear Assignment Problem solver (LAPJV/LAPMOD).
BSD 2-Clause "Simplified" License
216 stars 68 forks source link

Single threaded #8

Open bkj opened 6 years ago

bkj commented 6 years ago

Question: is this a single threaded implementation or are their options for multithreading?

gatagat commented 6 years ago

Interesting question. Both current algorithms (LAPJV, LAPMOD) are sequential, but it would certainly be great to add a parallel one (e.g. Balas et al, 1991).

bkj commented 6 years ago

Interesting, thanks. Do you have a link to that paper, by chance?

gatagat commented 6 years ago

http://www.dtic.mil/dtic/tr/fulltext/u2/a233588.pdf

An interesting discussion of parallelizing the LAP is in section 3.4 of this report: https://www.opt.math.tugraz.at/~cela/papers/lap_bericht.pdf