"Small amount of additional complexity" = converts algorithm solution from polynomial to superpolynomial complexity... what with the expansion of medical schools and residencies, maybe that's why they have given themselves a few weeks to run the algorithm? Lol. At least it is NP-complete so the (eventual) solution can be proven correct in polynomial time.
Your comment did get me curious though as to what kind of polynomials we are talking about. The stable marriage problem (like bubble sort) is O(n^2). I haven't done the math but my gut feeling is the residency match would be O(n * m) then, increasing linearly with an increase in either applicants or residency slots.
If it continues to hold that the variations like couples matching don't practically add much additional complexity, then as long as the time it takes to double the number of applicants AND double the number of residency slots (i.e. slowing the run time by a factor of four) takes longer than 3 years (the time it would take to increase computing power by a factor of four) the match algorithm is gonna take less and less time to run every year. Seventeen seconds is a maximum.