The latest release of GLPK has an out-of-kilter method for network problems, which includes the assignment problem. That is probably a polynomial time algorithm (n*n*n? I'm rusty on this aspect). I haven't used this feature yet, and therefore I don't know how to turn it on. -Marc
________________________________ From: [email protected] on behalf of Brady Hunsaker Sent: Wed 8/19/2009 8:47 AM To: Linna Li Cc: [email protected] Subject: Re: [Help-glpk] time complexity in glpk GLPK uses the simplex algorithm, which is generally fast in practice but can take exponential time in the worst case (proven for several pivot rules, anyway). Also, in the presence of poorly scaled instances it is possible for GLPK to not be able to solve an instance at all. So there's no guarantee on the time it will take to solve. Brady Linna Li wrote: > Hi, > > I'm using glpk to solve the assignment problem. What is the time complexity > for this? I haven't found any documents with this information. Thanks a > lot! > > Linna > > > > ------------------------------------------------------------------------ > > _______________________________________________ > Help-glpk mailing list > [email protected] > http://lists.gnu.org/mailman/listinfo/help-glpk _______________________________________________ Help-glpk mailing list [email protected] http://lists.gnu.org/mailman/listinfo/help-glpk ---------------------------------------------------------------------------- This e-mail and any attachments may be confidential or legally privileged. If you received this message in error or are not the intended recipient, you should destroy the e-mail message and any attachments or copies, and you are prohibited from retaining, distributing, disclosing or using any information contained herein. Please inform us of the erroneous delivery by return e-mail. Thank you for your cooperation. ----------------------------------------------------------------------------
_______________________________________________ Help-glpk mailing list [email protected] http://lists.gnu.org/mailman/listinfo/help-glpk
