On sparsity of approximate solutions to max-plus linear systems
Pingke Li · Kybernetika · 2024
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.