Aproximovatelnost NM
Napsal: 11. 1. 2012 10:11
Ahoj,
v poznamkach ze cviceni mam u otazky, zda je mozne aproximacni alg. z prednasky pro vrcholove pokryti (s r=2) pouzit i jako aproximacni
algoritmus pro nezavislou mnozinu (protoze NM = V \ VP). Mam k tomu jen poznamenano, ze "aproximovatlenost je ruzna"...
Nemate k tomu nekdo neco vic?
Diky
v poznamkach ze cviceni mam u otazky, zda je mozne aproximacni alg. z prednasky pro vrcholove pokryti (s r=2) pouzit i jako aproximacni
algoritmus pro nezavislou mnozinu (protoze NM = V \ VP). Mam k tomu jen poznamenano, ze "aproximovatlenost je ruzna"...
Nemate k tomu nekdo neco vic?
Diky