Re: NP  Hard  Approximation algos
From: Foo Bar (foobar965_at_hotmail.com)
Date: 04/05/05
 Next message: jumpstart: "Re: NP  Hard  Approximation algos"
 Previous message: jumpstart: "Re: Explanation for a theorem  approximation algos"
 In reply to: jumpstart: "NP  Hard  Approximation algos"
 Next in thread: jumpstart: "Re: NP  Hard  Approximation algos"
 Reply: jumpstart: "Re: NP  Hard  Approximation algos"
 Reply: jumpstart: "Re: NP  Hard  Approximation algos"
 Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Date: 5 Apr 2005 10:55:31 0700
"jumpstart" <jumpstart101@gmail.com> wrote in message news:<1112594935.719424.87720@f14g2000cwb.googlegroups.com>...
<snip>
>
> Regarding "This problem is known to be NPhard."
> (In first page,2nd Column, 2nd Paragraph, 1st line)
>
> I would be happy to have answers based on my subquestions.
>
> 1. What is NP hard?
A NPhard problem is a problem such that every problem in NP polytime
reduces to it. A NPcomplete problem is a problem in NP such that
every problem in NP polytime (Karp) reduces to it.
The distinction is important since NP is often defined as containing
only decision problems. For example, with this definition of NP,
Traveling Salesman is in NP, but phrased as "_Is_ there a route
shorter than k for this graph?" (NPcomplete). The constructive
version (called Minimum Traveling Salesman), phrased as "Give me a
route shorter than k for this graph!", is NPhard.
> 2. Why this problem is NP  hard?
Why? Because every problem in NP polytime reduces to it. Why is
Traveling Salesman NPcomplete? Same reason.
> 3. How to prove this is NP hard?
Find a polynomial time reduction from a known NPhard (or NPcomplete)
problem to this problem.
You might try and look it up in Garey & Johnson (problem ND30). There
might be a reference to a proof there. If you are interested in
approximation algorithms, the other references are probably helpful.
Oh, and the problem is also called "Shortest WeightConstrained Path".
What exactly is it you are interested in? The NPhardness proof? A
FPTAS for the problem? Something else?
Also, be aware the some of the answers you have gotten from other
posters are partially incorrect...
/FB
 Next message: jumpstart: "Re: NP  Hard  Approximation algos"
 Previous message: jumpstart: "Re: Explanation for a theorem  approximation algos"
 In reply to: jumpstart: "NP  Hard  Approximation algos"
 Next in thread: jumpstart: "Re: NP  Hard  Approximation algos"
 Reply: jumpstart: "Re: NP  Hard  Approximation algos"
 Reply: jumpstart: "Re: NP  Hard  Approximation algos"
 Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Relevant Pages
