Can polynomial time approximation algorithms can be used

Assignment Help Computer Engineering

Reference no: EM132084385

About NP complete problems, we learned that if a polynomial algorithm could be found for one NP complete problem, then that algorithm could be used to solve any problem in NP in polynomial time.

My question is, can polynomial time approximation algorithms (like the ones we learned in this module) can be used in a similar way?

That is, if we have one polynomial time approximation algorithm, can we use that algorithm as a subroutine to approximately solve other NP problems in polynomial time?

Reference no: EM132084385

Questions Cloud

How to convert the ebit to free cash flow : How to convert the EBIT to free cash flow for the next 12 years?

Cash flow of the loan from the borrower perspective : Calculate (a) The cash flow of the loan from the borrower's perspective (b) The amount of the annual principal repayment (c) The stream of interest payments

Create a simple number guessing game : Create a simple number guessing game. Before the game starts, your program will randomly select a number between one and ten.

What is the investor two year holding period return : These funds increased by 20% over the next year. The investor then closed his account. What is the investor's two year holding period return?

Can polynomial time approximation algorithms can be used : Can polynomial time approximation algorithms (like the ones we learned in this module) can be used in a similar way?

What is the treynor measure of excess returns : If the portfolio return is 10 percent and the U.S. T-bill rate is 5.75 percent what is the Treynor measure of excess returns?

Calculate the expected cash collections : On average, 60% of credit sales are paid for in the current month, 20% in the next month, and the remainder in the month after that.

What sort of trade-offs do you think are necessary to deal : What sort of trade-offs do you think are necessary to deal with these problems in developing software for wireless devices?

What is the break-even level of ebit : All of the money raised from the debt issue would be used to repurchase stock. What is the break-even level of EBIT between the two structures?

User Account

All Pages