Show polynomial-time algorithm for gdp

Assignment Help Theory of Computation

Reference no: EM1388584

Let the following "gold-digger problem" (GDP). You are given the map of territory consisting of set of towns connected by trails. Each trail (u, v) connecting towns u and v is labeled with dollar value w(u, v), which is value of gold you will find along that trail. You can traverse trail as frequently as you want, but you only get value of trail the first time you traverse it; subsequent traversals have no value. Each town v has lodging cost c(v), which you pay each time you enter the town.

Expedition is cyclic path which starts and ends at given town. Expedition has profit k if total value of gold found, minus cost of all the town visits, is k. Goal is to find expedition of maximum profit. Either show that there exists polynomial-time algorithm for GDP, or show that corresponding decision problem is NP-complete. If you want to illustrate that problem is hard, you may decrease from any of: SAT, 3-CNF-SAT, CLIQUE, VERTEX-COVER, SUBSET-SUM, PARTITION, HAM-CYCLE, TSP.

Reference no: EM1388584

Questions Cloud

Recognize input data required for each of processes : Recognize input data required for each of processes. Recognize logical name for each data output item and kind of data output (real number, integer, text).

Calculate the interest in canada : Explain and illustrate the economy's adjustement with devaluation and find the real wage rate implied by the price-setting equation

How ecosystem affected by a decline in fungi species : Throughout much of Europe, there has been a severe decline in mushroom population. On study plots in Holland, data collected since 1912 indicate that the number of mushroom species has dropped from 37 to twelve per plot in recent years.

Define the mass of the necklace : A 40-g bullet leaves the muzzle of a gun at a speed of 300 m/s. If the barrel of the gun is 12 cm long, what is the force acting on the bullet while it is in the barrel.

Show polynomial-time algorithm for gdp : Goal is to find expedition of maximum profit. Either show that there exists polynomial-time algorithm for GDP, or show that corresponding decision problem is NP-complete.

Evolution of vascular plants : Discuss how evolution of vascular plants has provided opportunities for fungal diversification?

Why does the car mass not matter : It was a rainy day and the coefficient of friction was estimated to be 0.42. Use these data to determine the speed of the car while the driver slammed on (and locked) the brakes.

Estimate the highest emf induced in the coil : Presume the needle moves 7.5 mm from its highest to its lowest position and it makes 26 stitches in 9.1 s. What is the highest needle speed.

Identify the main biological organic compounds : Identify the main biological organic compounds and identify and explain three functions of lipids and why lipids do not mix with water.

User Account

All Pages