Show polynomial-time algorithm for gdp
Course:- Theory of Computation
Reference No.:- EM1388584

Assignment Help
Expertsmind Rated 4.9 / 5 based on 47215 reviews.
Review Site
Assignment Help >> Theory of Computation

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.

Put your comment

Ask Question & Get Answers from Experts
Browse some more (Theory of Computation) Materials
Create and implement a lexical analyzer for C-- as follows: Write the set of token types to be returned by lexical analyzer. Explain regular expressions for this set of token
Consider the LCG defined by m = 16, a = 5, c = 3, and Z0 = 7. Compute until Z19 and verify that when i = 16, the exact the same order will show up. Show all results in a tab
There are four processes that are going to share nine tape drives. Their current and maximum number of allocation numbers. Is system in a safe state? Explain why or why not?
Perform the ACL test and prepare a report with your conclusions. Document your report with ACL printouts showing details of test results and the command log - Identify an op
Construct a DFA that recognizes each of the following languages. Unless otherwise noted we are assuming that ω ∈ {0,1}*. (A drawing of a state diagram is sufficient.)
Verify that a number in base b can be converted to base b3 by partitioning the digits of the base b number into groups of three consecutive digits starting at the radix poin
Write a grammar for the language consisting of strings that have n copies of the letter a followed by same number of copies of the letter b, where n>0
Calculate the sum of 2.6125 X 101 and 4.150390625 X 10-1 by hand, assuming A and B are stored in the 16-bit half precision described in exercise 3.27. Assume 1 guard, 1 round