Hi,

I am doing a research on Approximation algorithms.
I came across a paper "Efficient Computation of Delay-sensitive Routes
from One Source to All Destinations" 

Reference:
http://www.ieee-infocom.org/2001/paper/148.ps

I know a few basic concepts of Algorithm analysis and Computational
complexity stuffs.However, I don't know much about the details.

I would like to know answers to my questions regarding that paper.

THIS IS A TIME CONSTRAINED ONE, AS MY RESEARCH STARTS WITH THIS PAPER AND 
AM HINDERED NOW WITH MY QUESTIONS NOT BEING ABLE TO PROCEED FURTHER.


(1). Regarding "This problem is know to be NP-hard." (In first page,
     2nd Column, 2nd Paragraph, 1st line)

     I would like to have answers based on my sub-questions.

	1. What is NP- hard?
	2. Why this problem is NP - hard?
	3. How to prove this is NP- hard?	


(2). I need step by step explanation (Mainly in plain English with
     basic technical terms)

     From "Our results" (in second page) 
     till before  III. SIMULATION RESULTS (in third page)

	That is, 

	Starting from....
	"Given a source s and a delay threshold T, .......

	Up untill
 	"....can also be extended to multiple constraining metrics"


      Also, in the explanation I need more details, concentrating much
      on the following questions:

	1. What is the expansion of DAD? (Fig. 2. Subroutine DAD which
           iterates on integer delays)

	2.a.  I need clear explanation for the Subroutine DAD.

	2.b.  I need clear explanation for the Algorithm DSA.

	3. I would like to know the proof of the lemma II.1? (The proof was
           omitted in the paper)

	4. How they get the term O (mD/e)?  (I represent "e" for "epsilon")

	5.a. What is Dijkstra's algorithm? 

        5.b. How the complexity of Dijkstra's algorithm is O (m+n log n)?

	6. How they arrive at the complexity O ((m+n log n) D/e)?  (I
           represent "e" for "epsilon")

I would be happy if any one answers me within a week or so.

Thanks for everyone's time,
Jumpstart


P:S:

If anyone who would like to post comment on question:
Please help me, even if you know only partial answers.

---

Clarification of Question by jumpstart-ga on 29 Mar 2005 22:15 PST

HERE IS THE MODIFIED **NEW** QUESTION


Hi,

I am doing a research on Approximation algorithms.
I came across a paper "Efficient Computation of Delay-sensitive Routes
from One Source to All Destinations" 

Reference:
http://www.ieee-infocom.org/2001/paper/148.ps

I know a few basic concepts of Algorithm analysis and Computational
complexity stuffs.However, I don't know much about the details.

I would like to know answers to my questions regarding that paper.

THIS IS A TIME CONSTRAINED ONE, AS MY RESEARCH STARTS WITH THIS PAPER AND 
AM HINDERED NOW WITH MY QUESTIONS NOT BEING ABLE TO PROCEED FURTHER.


(1). Regarding "This problem is known to be NP-hard." (In first page,
     2nd Column, 2nd Paragraph, 1st line)

     I would like to have answers based on my sub-questions.

	1. What is NP- hard?
	2. How to prove this is NP- hard?	


(2). I need step by step explanation (Mainly in plain English with
     basic technical terms)

     From "Our results" (in second page) 
     till before  III. SIMULATION RESULTS (in third page)

	That is, 

	Starting from....
	"Given a source s and a delay threshold T, .......

	Up untill
 	"....can also be extended to multiple constraining metrics"


      Also, in the explanation I need more details, concentrating much
      on the following questions:

	
	1.  I need clear explanation for the Subroutine DAD.

	2.  I need clear explanation for the Algorithm DSA.

	3.  How they get the term O (mD/e)?  (I represent "e" for "epsilon")

	4.  How they arrive at the complexity O ((m+n log n) D/e)?  (I
            represent "e" for "epsilon")

I would be happy if any one answers me ASAP.

Thanks for everyone's time,
Jumpstart


P:S:

If anyone who would like to post comment on question:
Please help me, even if you know only partial answers.

---

Request for Question Clarification by pythagoras-ga on 02 Apr 2005 07:34 PST

Hello

I can probably help you, but I need more money for this question, it
will take much time.
 
I think 200$ would be fair.

I have studied computer science at the university of Ghent Belgium.

Greetings

Pythagoras

---

Clarification of Question by jumpstart-ga on 02 Apr 2005 09:03 PST

Dear pythagoras-ga,

Thanks for your taking time to give me suggestion. 
I guess I can't afford $200 at this point of time.

Thanks,
pythagoras-ga,

---

Clarification of Question by jumpstart-ga on 03 Apr 2005 22:31 PDT

At least,

I would like to know the clear explanation for the proof of the
theorem II.I ( in 3rd page)

Reference:
http://www.ieee-infocom.org/2001/paper/148.ps

Hi,
do you really expect, that someone might answer this for 10 bucks?
Thats quite a work to write this down exactly.

Hi frankfi,

Thanks for your Comment
I appreciate it, even if it's not "totally" related to my question. :-)

--jumpstart

Hello,

Anyone please help me, even it its a partial answer.

I need it before APRIL 2.

Thanks a bunch,
jumpstart