When　a　system　of　one-sided　max-plus　linear　equations　is　inconsistent,　the　approximate　solutions　within　an　admissible　error　bound　may　be　desired　instead,　particularly　with　some　sparsity　property.　It　is　demonstrated　in　this　paper　that　obtaining　the　sparsest　approximate　solution　within　a　given　L∞　error　bound　may　be　transformed　in　polynomial　time　into　the　set　covering　problem,　which　is　known　to　be　NP-hard.　Besides,　the　problem　of　obtaining　the　sparsest　approximate　solution　within　a　given　L1　error　bound　may　be　reformulated　as　a　polynomial-sized　mixed　integer　linear　programming　problem,　which　may　be　regarded　as　a　special　scenario　of　the　facility　location-allocation　problem.　By　this　reformulation　approach,　this　paper　reveals　some　interesting　connections　between　the　sparsest　approximate　solution　problems　in　max-plus　algebra　and　some　well　known　problems　in　discrete　and　combinatorial　optimization.　©　2024　Institute　of　Information　Theory　and　Automation　of　The　Czech　Academy　of　Sciences.　All　rights　reserved.