I saw this answer - Guide me to a dependable subtitling software that also hard-codes subtitles, but the getdeb links seem to be broken or gone.
I also tried the appImage file for Linux here - Download Avidemux latest release, but it would not execute at all. (I did set the file properties to "executable".)
Also no results on Ubuntu package search.
So is there any currently available solution to run this on 16.04?