since np hard problem reduced other np hard problem mapping, question 1 step forward; example every step of algo : mapped other np hard?
thanks in advance
from http://en.wikipedia.org/wiki/approximation_algorithm see that
np-hard problems vary in approximability; some, such bin packing problem, can approximated within factor greater 1 (such family of approximation algorithms called polynomial time approximation scheme or ptas). others impossible approximate within constant, or polynomial factor unless p = np, such maximum clique problem. (end quote)
it follows approximation in 1 np-complete problem not approximation in np-complete problem. in fortunate world use easily-approximated np-complete problems find approximate algorithms other np-complete problems, not case here, there hard-to-approximate np-complete problems.
Comments
Post a Comment