O problema e a solução são explicados aqui: link
rm /etc/apt/apt.conf.d/docker-gzip-indexes
apt-get purge apt-show-versions
rm /var/lib/apt/lists/*lz4
apt-get -o Acquire::GzipIndexes=false update
[…]
apt-get install apt-show-versions
The following NEW packages will be installed:
apt-show-versions
0 upgraded, 1 newly installed, 0 to remove and 0 not upgraded.
Need to get 29.6 kB of archives.
After this operation, 163 kB of additional disk space will be used.
Get:1 http://archive.ubuntu.com/ubuntu xenial/universe amd64 apt-show-versions all 0.22.7 [29.6 kB]
Fetched 29.6 kB in 0s (371 kB/s)
Selecting previously unselected package apt-show-versions.
(Reading database ... 46320 files and directories currently installed.)
Preparing to unpack .../apt-show-versions_0.22.7_all.deb ...
Unpacking apt-show-versions (0.22.7) ...
Processing triggers for man-db (2.7.5-1) ...
Setting up apt-show-versions (0.22.7) ...
** initializing cache. This may take a while **
root@4127ac89e58f:/#