Scaling Hungarian algorithm / assignment problem to tens…
0 reactions
Scaling Hungarian algorithm / assignment problem to tens of millions of candidate pairs . No partitioning?
Hey folks — I’m implementing a 1–1 assignment (Hungarian / linear assignment) for a business matching problem and I’m hitting scalability walls.
**My current setup is below:**
* I don’t build a dense cost matrix. I have a sparse edge list: `(id_left, id_right, score)`
* Left side is \~2.0M, right side is \~115k
* After candidate generation + filtering, I still have \~45M edges/pairs going into the final optimization stage
* Running this inside Snowflake (Snowpark / UDTF style) and the “final solve” can blow memory / take forever
**Current problem what I am facing:**
Business wants “global” optimization (can’t just chunk by time or arbitrary partitions). We don’t want to lose valid pairs. (Ideally would have loved to partition it)!
**Question:**
How do people scale assignment problems like this in practice?
* Any recommended solvers/approaches for *sparse rectangular* assignment at this scale?
* Is there a principled way to split the problem while keeping global optimality?
* Any architecture patterns (e.g., min-cost flow, auction algorithm, connected components, etc.) that work well?
Would love pointers to algorithms, libraries, or production patterns. Thanks!
#technology
source
Hey folks — I’m implementing a 1–1 assignment (Hungarian / linear assignment) for a business matching problem and I’m hitting scalability walls.
**My current setup is below:**
* I don’t build a dense cost matrix. I have a sparse edge list: `(id_left, id_right, score)`
* Left side is \~2.0M, right side is \~115k
* After candidate generation + filtering, I still have \~45M edges/pairs going into the final optimization stage
* Running this inside Snowflake (Snowpark / UDTF style) and the “final solve” can blow memory / take forever
**Current problem what I am facing:**
Business wants “global” optimization (can’t just chunk by time or arbitrary partitions). We don’t want to lose valid pairs. (Ideally would have loved to partition it)!
**Question:**
How do people scale assignment problems like this in practice?
* Any recommended solvers/approaches for *sparse rectangular* assignment at this scale?
* Is there a principled way to split the problem while keeping global optimality?
* Any architecture patterns (e.g., min-cost flow, auction algorithm, connected components, etc.) that work well?
Would love pointers to algorithms, libraries, or production patterns. Thanks!
#technology
source
| 2,000 mlx | |
| 2 | |
| 0 |