Para aqueles que podem estar interessados, eu encontrei uma solução, embora eu não ache que seja uma boa solução.
Essencialmente, eu esperava que o pacote que estava exigindo linux-libc-dev esperasse aceitar um intervalo de linux-libc-dev versões.
Então eu enrolei a versão mais próxima em /var/cache/apt/archives
% cd /var/cache/apt/archives
%
..cache/apt/archives % sudo curl -O 'http://security.ubuntu.com/ubuntu/pool/main/l/linux/linux-libc-dev_4.4.0-72.93_amd64.deb'
%
cache/apt/archives % sudo dpkg --install linux-libc-dev_4.4.0-72.93_amd64.deb
%
Os pacotes linux-libc-dev e checkinstall foram instalados, mas parece que ele pode ter substituído muitos outros pacotes
cache/apt/archives % sudo dpkg --install linux-libc-dev_4.4.0-72.93_amd64.deb
Selecting previously unselected package linux-libc-dev:amd64.
(Reading database ... 60543 files and directories currently installed.)
Preparing to unpack linux-libc-dev_4.4.0-72.93_amd64.deb ...
Unpacking linux-libc-dev:amd64 (4.4.0-72.93) ...
Setting up linux-libc-dev:amd64 (4.4.0-72.93) ...
%
cache/apt/archives % sudo apt-get install checkinstall
Reading package lists... Done
Building dependency tree
Reading state information... Done
The following additional packages will be installed:
build-essential cpp cpp-5 dpkg-dev fakeroot g++ g++-5 gcc gcc-5 libalgorithm-diff-perl libalgorithm-diff-xs-perl libalgorithm-merge-perl libasan2 libatomic1
libc-dev-bin libc6-dev libcc1-0 libcilkrts5 libdpkg-perl libfakeroot libfile-fcntllock-perl libgcc-5-dev libgomp1 libisl15 libitm1 liblsan0 libmpc3 libmpx0
libquadmath0 libstdc++-5-dev libtsan0 libubsan0 make manpages-dev
Suggested packages:
gettext cpp-doc gcc-5-locales debian-keyring g++-multilib g++-5-multilib gcc-5-doc libstdc++6-5-dbg gcc-multilib autoconf automake libtool flex bison gdb gcc-doc
gcc-5-multilib libgcc1-dbg libgomp1-dbg libitm1-dbg libatomic1-dbg libasan2-dbg liblsan0-dbg libtsan0-dbg libubsan0-dbg libcilkrts5-dbg libmpx0-dbg libquadmath0-dbg
glibc-doc libstdc++-5-doc make-doc
The following NEW packages will be installed:
build-essential checkinstall cpp cpp-5 dpkg-dev fakeroot g++ g++-5 gcc gcc-5 libalgorithm-diff-perl libalgorithm-diff-xs-perl libalgorithm-merge-perl libasan2
libatomic1 libc-dev-bin libc6-dev libcc1-0 libcilkrts5 libdpkg-perl libfakeroot libfile-fcntllock-perl libgcc-5-dev libgomp1 libisl15 libitm1 liblsan0 libmpc3
libmpx0 libquadmath0 libstdc++-5-dev libtsan0 libubsan0 make manpages-dev
0 upgraded, 35 newly installed, 0 to remove and 0 not upgraded.
Need to get 0 B/35.3 MB of archives.
After this operation, 126 MB of additional disk space will be used.
Do you want to continue? [Y/n] y
Extracting templates from packages: 100%
Selecting previously unselected package libmpc3:amd64.
(Reading database ... 61354 files and directories currently installed.)
Preparing to unpack .../libmpc3_1.0.3-1_amd64.deb ...
Unpacking libmpc3:amd64 (1.0.3-1) ...
Selecting previously unselected package libc-dev-bin.
Preparing to unpack .../libc-dev-bin_2.23-0ubuntu7_amd64.deb ...
Unpacking libc-dev-bin (2.23-0ubuntu7) ...
Selecting previously unselected package libc6-dev:amd64.
Preparing to unpack .../libc6-dev_2.23-0ubuntu7_amd64.deb ...
Unpacking libc6-dev:amd64 (2.23-0ubuntu7) ...
Selecting previously unselected package libisl15:amd64.
Preparing to unpack .../libisl15_0.16.1-1_amd64.deb ...
Unpacking libisl15:amd64 (0.16.1-1) ...
Selecting previously unselected package cpp-5.
Preparing to unpack .../cpp-5_5.4.0-6ubuntu1~16.04.4_amd64.deb ...
Unpacking cpp-5 (5.4.0-6ubuntu1~16.04.4) ...
Selecting previously unselected package cpp.
Preparing to unpack .../cpp_4%3a5.3.1-1ubuntu1_amd64.deb ...
Unpacking cpp (4:5.3.1-1ubuntu1) ...
Selecting previously unselected package libcc1-0:amd64.
Preparing to unpack .../libcc1-0_5.4.0-6ubuntu1~16.04.4_amd64.deb ...
Unpacking libcc1-0:amd64 (5.4.0-6ubuntu1~16.04.4) ...
Selecting previously unselected package libgomp1:amd64.
Preparing to unpack .../libgomp1_5.4.0-6ubuntu1~16.04.4_amd64.deb ...
Unpacking libgomp1:amd64 (5.4.0-6ubuntu1~16.04.4) ...
Selecting previously unselected package libitm1:amd64.
Preparing to unpack .../libitm1_5.4.0-6ubuntu1~16.04.4_amd64.deb ...
Unpacking libitm1:amd64 (5.4.0-6ubuntu1~16.04.4) ...
Selecting previously unselected package libatomic1:amd64.
Preparing to unpack .../libatomic1_5.4.0-6ubuntu1~16.04.4_amd64.deb ...
Unpacking libatomic1:amd64 (5.4.0-6ubuntu1~16.04.4) ...
Selecting previously unselected package libasan2:amd64.
Preparing to unpack .../libasan2_5.4.0-6ubuntu1~16.04.4_amd64.deb ...
Unpacking libasan2:amd64 (5.4.0-6ubuntu1~16.04.4) ...
Selecting previously unselected package liblsan0:amd64.
Preparing to unpack .../liblsan0_5.4.0-6ubuntu1~16.04.4_amd64.deb ...
Unpacking liblsan0:amd64 (5.4.0-6ubuntu1~16.04.4) ...
Selecting previously unselected package libtsan0:amd64.
Preparing to unpack .../libtsan0_5.4.0-6ubuntu1~16.04.4_amd64.deb ...
Unpacking libtsan0:amd64 (5.4.0-6ubuntu1~16.04.4) ...
Selecting previously unselected package libubsan0:amd64.
Preparing to unpack .../libubsan0_5.4.0-6ubuntu1~16.04.4_amd64.deb ...
Unpacking libubsan0:amd64 (5.4.0-6ubuntu1~16.04.4) ...
Selecting previously unselected package libcilkrts5:amd64.
Preparing to unpack .../libcilkrts5_5.4.0-6ubuntu1~16.04.4_amd64.deb ...
Unpacking libcilkrts5:amd64 (5.4.0-6ubuntu1~16.04.4) ...
Selecting previously unselected package libmpx0:amd64.
Preparing to unpack .../libmpx0_5.4.0-6ubuntu1~16.04.4_amd64.deb ...
Unpacking libmpx0:amd64 (5.4.0-6ubuntu1~16.04.4) ...
Selecting previously unselected package libquadmath0:amd64.
Preparing to unpack .../libquadmath0_5.4.0-6ubuntu1~16.04.4_amd64.deb ...
Unpacking libquadmath0:amd64 (5.4.0-6ubuntu1~16.04.4) ...
Selecting previously unselected package libgcc-5-dev:amd64.
Preparing to unpack .../libgcc-5-dev_5.4.0-6ubuntu1~16.04.4_amd64.deb ...
Unpacking libgcc-5-dev:amd64 (5.4.0-6ubuntu1~16.04.4) ...
Selecting previously unselected package gcc-5.
Preparing to unpack .../gcc-5_5.4.0-6ubuntu1~16.04.4_amd64.deb ...
Unpacking gcc-5 (5.4.0-6ubuntu1~16.04.4) ...
Selecting previously unselected package gcc.
Preparing to unpack .../gcc_4%3a5.3.1-1ubuntu1_amd64.deb ...
Unpacking gcc (4:5.3.1-1ubuntu1) ...
Selecting previously unselected package libstdc++-5-dev:amd64.
Preparing to unpack .../libstdc++-5-dev_5.4.0-6ubuntu1~16.04.4_amd64.deb ...
Unpacking libstdc++-5-dev:amd64 (5.4.0-6ubuntu1~16.04.4) ...
Selecting previously unselected package g++-5.
Preparing to unpack .../g++-5_5.4.0-6ubuntu1~16.04.4_amd64.deb ...
Unpacking g++-5 (5.4.0-6ubuntu1~16.04.4) ...
Selecting previously unselected package g++.
Preparing to unpack .../g++_4%3a5.3.1-1ubuntu1_amd64.deb ...
Unpacking g++ (4:5.3.1-1ubuntu1) ...
Selecting previously unselected package make.
Preparing to unpack .../archives/make_4.1-6_amd64.deb ...
Unpacking make (4.1-6) ...
Selecting previously unselected package libdpkg-perl.
Preparing to unpack .../libdpkg-perl_1.18.4ubuntu1.1_all.deb ...
Unpacking libdpkg-perl (1.18.4ubuntu1.1) ...
Selecting previously unselected package dpkg-dev.
Preparing to unpack .../dpkg-dev_1.18.4ubuntu1.1_all.deb ...
Unpacking dpkg-dev (1.18.4ubuntu1.1) ...
Selecting previously unselected package build-essential.
Preparing to unpack .../build-essential_12.1ubuntu2_amd64.deb ...
Unpacking build-essential (12.1ubuntu2) ...
Selecting previously unselected package checkinstall.
Preparing to unpack .../checkinstall_1.6.2-4ubuntu1_amd64.deb ...
Unpacking checkinstall (1.6.2-4ubuntu1) ...
Selecting previously unselected package libfakeroot:amd64.
Preparing to unpack .../libfakeroot_1.20.2-1ubuntu1_amd64.deb ...
Unpacking libfakeroot:amd64 (1.20.2-1ubuntu1) ...
Selecting previously unselected package fakeroot.
Preparing to unpack .../fakeroot_1.20.2-1ubuntu1_amd64.deb ...
Unpacking fakeroot (1.20.2-1ubuntu1) ...
Selecting previously unselected package libalgorithm-diff-perl.
Preparing to unpack .../libalgorithm-diff-perl_1.19.03-1_all.deb ...
Unpacking libalgorithm-diff-perl (1.19.03-1) ...
Selecting previously unselected package libalgorithm-diff-xs-perl.
Preparing to unpack .../libalgorithm-diff-xs-perl_0.04-4build1_amd64.deb ...
Unpacking libalgorithm-diff-xs-perl (0.04-4build1) ...
Selecting previously unselected package libalgorithm-merge-perl.
Preparing to unpack .../libalgorithm-merge-perl_0.08-3_all.deb ...
Unpacking libalgorithm-merge-perl (0.08-3) ...
Selecting previously unselected package libfile-fcntllock-perl.
Preparing to unpack .../libfile-fcntllock-perl_0.22-3_amd64.deb ...
Unpacking libfile-fcntllock-perl (0.22-3) ...
Selecting previously unselected package manpages-dev.
Preparing to unpack .../manpages-dev_4.04-2_all.deb ...
Unpacking manpages-dev (4.04-2) ...
Processing triggers for man-db (2.7.5-1) ...
Processing triggers for libc-bin (2.23-0ubuntu7) ...
Setting up libmpc3:amd64 (1.0.3-1) ...
Setting up libc-dev-bin (2.23-0ubuntu7) ...
Setting up libc6-dev:amd64 (2.23-0ubuntu7) ...
Setting up libisl15:amd64 (0.16.1-1) ...
Setting up cpp-5 (5.4.0-6ubuntu1~16.04.4) ...
Setting up cpp (4:5.3.1-1ubuntu1) ...
Setting up libcc1-0:amd64 (5.4.0-6ubuntu1~16.04.4) ...
Setting up libgomp1:amd64 (5.4.0-6ubuntu1~16.04.4) ...
Setting up libitm1:amd64 (5.4.0-6ubuntu1~16.04.4) ...
Setting up libatomic1:amd64 (5.4.0-6ubuntu1~16.04.4) ...
Setting up libasan2:amd64 (5.4.0-6ubuntu1~16.04.4) ...
Setting up liblsan0:amd64 (5.4.0-6ubuntu1~16.04.4) ...
Setting up libtsan0:amd64 (5.4.0-6ubuntu1~16.04.4) ...
Setting up libubsan0:amd64 (5.4.0-6ubuntu1~16.04.4) ...
Setting up libcilkrts5:amd64 (5.4.0-6ubuntu1~16.04.4) ...
Setting up libmpx0:amd64 (5.4.0-6ubuntu1~16.04.4) ...
Setting up libquadmath0:amd64 (5.4.0-6ubuntu1~16.04.4) ...
Setting up libgcc-5-dev:amd64 (5.4.0-6ubuntu1~16.04.4) ...
Setting up gcc-5 (5.4.0-6ubuntu1~16.04.4) ...
Setting up gcc (4:5.3.1-1ubuntu1) ...
Setting up libstdc++-5-dev:amd64 (5.4.0-6ubuntu1~16.04.4) ...
Setting up g++-5 (5.4.0-6ubuntu1~16.04.4) ...
Setting up g++ (4:5.3.1-1ubuntu1) ...
update-alternatives: using /usr/bin/g++ to provide /usr/bin/c++ (c++) in auto mode
Setting up make (4.1-6) ...
Setting up libdpkg-perl (1.18.4ubuntu1.1) ...
Setting up dpkg-dev (1.18.4ubuntu1.1) ...
Setting up build-essential (12.1ubuntu2) ...
Setting up checkinstall (1.6.2-4ubuntu1) ...
Setting up libfakeroot:amd64 (1.20.2-1ubuntu1) ...
Setting up fakeroot (1.20.2-1ubuntu1) ...
update-alternatives: using /usr/bin/fakeroot-sysv to provide /usr/bin/fakeroot (fakeroot) in auto mode
Setting up libalgorithm-diff-perl (1.19.03-1) ...
Setting up libalgorithm-diff-xs-perl (0.04-4build1) ...
Setting up libalgorithm-merge-perl (0.08-3) ...
Setting up libfile-fcntllock-perl (0.22-3) ...
Setting up manpages-dev (4.04-2) ...
Processing triggers for libc-bin (2.23-0ubuntu7) ...