title: Implementing the Hungarian Method as described by Papadimitriou & Steiglitz
body: <p>If you've implemented the Hungarian Method <strong>exactly</strong> as given in Figure 11-2 of <em>Combinatorial Optimization: Algorithms and Complexity</em>, did you succeed without altering the pseudo-code in any [significant] way? To be specific, I'm referring to the corrected 1998 Dover edition, which is up-to-date with respect to the errata file dated October 2000 given on Steiglitz's website.</p>
  
  <p>An acceptable answer would be along the lines of, "I implemented it, and it works perfectly." Or, "I implemented it, but it needed such-and-such on line so-and-so." In the former case, I'd know to continue the already-extensive delving and debugging of my code. (I'm going to do that anyway, though.) In the latter case, I'd have a bit of insight that might make my own implementation work correctly.</p>
  
  <p>If you've implemented the Hungarian Method, but did not use <em>CO:AaC</em> or did not use C without third-party libraries, you are still more than welcome to offer an answer. In fact, if you're a super-genius who can just examine Figure 11-2 and point out an error of omission or commission by P&amp;S, I'd like to hear from you, and I bet they would, too :-)</p>
  
  <p><strong>Edit:</strong> <a href="http://books.google.com/books?id=u1RmDoJqkF4C&amp;lpg=PA252&amp;ots=S7EOLV1WHe&amp;dq=combinatorial%20optimization%20figure%2011-2&amp;pg=PP1#v=onepage&amp;q&amp;f=false" rel="nofollow">Here</a>'s the book on Google Books. For the Hungarian Method, see pages 251-252. For the pseudo-code for the <code>augment()</code> procedure, see page 224. For the explanation of the data structures, see the surrounding pages. Ideally you have the physical book, as the Google Books version is predictably partial.</p>
  
  <p><strong>Update:</strong></p>
  
  <p>After more thorough testing of my implementation and more thorough examination of the book's pseudo-code and text, I <em>think</em> I've resolved some issues with the pseudo-code itself. There were a couple of new errata. I've been in touch with Prof. Steiglitz, who maintains the errata file at his Princeton homepage, and he has said that he will review my notes when he has more time at the end of the semester in <del>December</del> January. (Sorry to anyone who'd been expecting resolution by year's end. I had assumed December was end-of-semester for Princeton, but it's actually January.)</p>
  
  <p><strong>Update:</strong></p>
  
  <p>Prof. Steiglitz has posted my code-&amp;-documentation package to his Princeton webspace. See my answer below for a link.</p>