RE: [Help-glpk] time complexity in glpk

[Meketon, Marc]

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: address@hidden on behalf of Brady Hunsaker
Sent: Wed 8/19/2009 8:47 AM
To: Linna Li
Cc: address@hidden
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
> address@hidden
> http://lists.gnu.org/mailman/listinfo/help-glpk



_______________________________________________
Help-glpk mailing list
address@hidden
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.
----------------------------------------------------------------------------