Package system is broken (16.04)

Question

I encountered a package management failure, and I don't know how to troubleshoot it. I have tried sudo apt -f install many times, but this errors remains. I have also tried sudo apt autoremove; sudo apt update, sudo apt-get clean; yet the error persists. Is there any way to fix this error?

Here is the error message for sudo apt-get -f install:

Reading package lists... Done 
Building dependency tree        
Reading state information... Done 
Correcting dependencies... failed. 
The following packages have unmet dependencies:  
chromium-browser : Depends: chromium-codecs-ffmpeg-extra (=56.0.2924.76-0ubuntu0.16.04.1268)  
 but 57.0.2987.98-0ubuntu0.16.04.1276 is installed or
 chromium-codecs-ffmpeg (= 56.0.2924.76-0ubuntu0.16.04.1268) but it is not installed   
chromium-browser-l10n : Depends: chromium-browser (>=57.0.2987.98-0ubuntu0.16.04.1276)  
 but 56.0.2924.76-0ubuntu0.16.04.1268 is installed 
E: Error, pkgProblemResolver::Resolve generated breaks, this may be 
caused by held packages. 

E: Unable to correct dependencies

Output of apt policy chromium-browser :

chromium-browser:
  Installed: 56.0.2924.76-0ubuntu0.16.04.1268
  Candidate: 57.0.2987.98-0ubuntu0.16.04.1276
  Version table:
57.0.2987.98-0ubuntu0.16.04.1276 500
        500 http: //us.archive.ubuntu.com/ubuntu xenial-updates/universe amd64 Packages
        500 http: //security.ubuntu.com/ubuntu xenial-security/universe amd64 Packages
***56.0.2924.76-0ubuntu0.16.04.1268 100
        100 /var/lib/dpkg/status
49.0.2623.108-0ubuntu1.1233 500
        500 http://us.archive.ubuntu.com/ubuntu xenial/universe amd64 Packages

Results of sudo apt install chromium-browser=57.0.2987.98-0ubuntu0.16.04.1276

Reading package lists... Done
Building dependency tree       
Reading state information... Done
You might want to run 'apt-get -f install' to correct these:
The following packages have unmet dependencies:
update-manager : Depends: update-manager-core (= 1:16.04.5) but 1:16.04.6 is to be installed
update-manager-core : Depends: python3-update-manager (= 1:16.04.6) but 1:16.04.5 is to be installed
E: Unmet dependencies. Try 'apt-get -f install' with no packages (or specify a solution)

Answer 1

An error message like this one

chromium-browser : Depends: chromium-codecs-ffmpeg-extra (= 56.0.2924.76-0ubuntu0.16.04.1268) but 57.0.2987.98-0ubuntu0.16.04.1276 > is installed

must be interpreted as "your version of chromium-browser depends on an old version of chromium-codecs-ffmpeg-extra". The most likely cause is that the upgrade of chromium-browser failed for some reason, and indeed apt-cache policy chromium-browser confirms that the installed version is not the newest one available. This is a problem because in principle all the packages installed on a system must always be at their latest version.

Thus we must upgrade chromium-browser to its latest version, which as per apt-cache policy is 57.0.2987.98-0ubuntu0.16.04.1276. One way to do this is to run sudo apt install chromium-browser=57.0.2987.98-0ubuntu0.16.04.1276.

Sadly, this did not work because some other packages exhibited the same issue; they must also be manually upgraded by appending them to the apt install command (as opposed to by a separate command) until all out-of-date packages are accounted for.