Hacker Times
new
|
past
|
comments
|
ask
|
show
|
jobs
|
submit
login
inigyou
23 days ago
|
parent
|
context
|
favorite
| on:
NP-overrated
So we see that a slight modification of the problem makes the approximation work for all graphs.
LPisGood
23 days ago
[–]
Elaborate on the proposed modification — are you referring to the fact that this can be done if distances obey a metric function?
inigyou
22 days ago
|
parent
[–]
If you modify the problem to allow passing by a node that you've already visited then the spanning tree approximation works for all graphs.
Guidelines
|
FAQ
|
Lists
|
API
|
Security
|
Legal
|
Apply to YC
|
Contact
Search: