On approximation intractability of the path-distance-width problem.
Koichi YamazakiPublished in: Discret. Appl. Math. (2001)
Keyphrases
- distance measure
- absolute error
- efficient computation
- approximation error
- shortest path
- relative error
- closed form
- path length
- hamming distance
- database systems
- distance measurement
- queueing networks
- approximation algorithms
- distance metric
- endpoints
- np complete
- weight function
- similarity measure
- approximation schemes
- image segmentation
- euclidean norm