Given infinite time, we could approach a string's exact Kolmogorov complexity. If we don't have infinite time, we can still calculate an upper bound on the Kolmogorov complexity of a string:
...simply compress the string s with some method, implement the corresponding decompressor in the chosen language, concatenate the decompressor to the compressed string, and measure the length of the resulting string...(Wikipedia)
Is there an algorithm--guaranteed to terminate within a finite amount of time--that provides a tighter upper bound on Kolmogorov complexity than len(compressed string) + len(decompressor)?
Unfortunately, K(x) is not approximable. There is no upper bound. Consider compressing pi. There exists a small program that produces pi, so K(pi) is very small. But "standard" compression programs (zip, etc...) can't compress pi much. So compress(pi) is large -- arbitrarily large. Hence compress(pi) - K(pi) is unbounded.
Put another way: we don't know how small K(x) could be so we can't place an upper bound on an approximation.