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 <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.
David