Bicriteria Data Compression is a novel compression paradigm which allows the user to trade decompression time and compressed size in a principled way. Shortly, the tool lets you specify a bound on the decompression time (say, 800 msecs), and compresses the file in such a way that the decompression time is below that time-bound and compressed size is minimized (or vice-versa).
Code is available here.