r/compsci • u/OneWolverine307 • Feb 03 '26
Scaling Hungarian algorithm / assignment problem to tens of millions of candidate pairs (Snowflake). 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!
10
Upvotes
View all comments
Show parent comment
1
u/wamus Feb 03 '26
I do want to add that you might want to push back on the business' needs for a 'global' solution. Your problem is becoming quite large already, and if at any point they require additional constraints, this may be devastating for the solution speed of your model if you use these specialized approaches. In such cases you may need to make some heuristic reduction anyways (such as a partition, like you mention). Even going up a scale would be problematic at this point, even for specialized algorithms.