[Top][All Lists]

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

Re: [Help-glpk] Linear Programming Relaxation

From: RC Loh
Subject: Re: [Help-glpk] Linear Programming Relaxation
Date: Wed, 25 Nov 2009 23:00:42 +0800 (SGT)

Hi David,
Thank you very much for your reply.
I hope you can help me on another question that I could not find the answer from the Internet.
I read some papers that stated "2-approximation" "3-approximation" or "6-approximation" for example the paper titled:
"Massaging a linear programming solution to give a 2-approximation for a generalization of the vertex cover problem"
What does actually "2-approximation" "3-approximation" or "6-approximation" means?

From: David Bremner <address@hidden>
To: RC Loh <address@hidden>
Cc: address@hidden
Sent: Wednesday, 25 November 2009 8:54:12
Subject: Re: [Help-glpk] Linear Programming Relaxation

RC Loh wrote:

>Just to confirm on question (2). I understand that GLPK also uses
>Interior Point method. Isn't the Interior Point method a polynomial
>time method?

Yes it is, but for linear programming, not for integer or mixed
integer programming.

>So with the Linear Programming Relaxation, the GLPK still does not
>runs in polynomial time?

A MIP solver needs to solve a whole search tree where each node is an
LP relaxation, and in general the number of LP relaxations solved is
not bounded by a polynomial in the input size.  There are many books
where this is explained; I happen to know "A First Course in
Combinatorial Optimization" by Jon Lee, see Chapters 6 and 7. 


New Email names for you!
Get the Email name you've always wanted on the new @ymail and @rocketmail.
Hurry before someone else does!
reply via email to

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