# 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 NP-hard."
*

*> (In first page,2nd Column, 2nd Paragraph, 1st line)
*

*>
*

*> I would be happy to have answers based on my sub-questions.
*

*>
*

*> 1. What is NP- hard?
*

A NP-hard problem is a problem such that every problem in NP poly-time

reduces to it. A NP-complete problem is a problem in NP such that

every problem in NP poly-time (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?" (NP-complete). The constructive

version (called Minimum Traveling Salesman), phrased as "Give me a

route shorter than k for this graph!", is NP-hard.

*> 2. Why this problem is NP - hard?
*

Why? Because every problem in NP poly-time reduces to it. Why is

Traveling Salesman NP-complete? Same reason.

*> 3. How to prove this is NP- hard?
*

Find a polynomial time reduction from a known NP-hard (or NP-complete)

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 Weight-Constrained Path".

What exactly is it you are interested in? The NP-hardness 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 ]