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?
Thank-you.
Rdgs,
Paul
________________________________
From: David Bremner <brem...@unb.ca>
To: RC Loh <rc_...@yahoo.com.sg>
Cc: help-glpk@gnu.org
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.
David
Yahoo! Toolbar is now powered with Free Anti-Virus and Anti-Adware
Software.
Download Yahoo! Toolbar now!
http://sg.toolbar.yahoo.com/_______________________________________________
Help-glpk mailing list
Help-glpk@gnu.org
http://lists.gnu.org/mailman/listinfo/help-glpk
