[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

RE: [Help-glpk] time complexity in glpk

From: Meketon, Marc
Subject: RE: [Help-glpk] time complexity in glpk
Date: Wed, 19 Aug 2009 09:15:27 -0400

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.

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.


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

Help-glpk mailing list

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.

reply via email to

[Prev in Thread] Current Thread [Next in Thread]