Kybernetika 60 no. 3, 412-425, 2024

On sparsity of approximate solutions to max-plus linear systems

Pingke LiDOI: 10.14736/kyb-2024-3-0412

Abstract:

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_{\infty}$ 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 $L_1$ 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.

Keywords:

max-plus algebra, sparsity, max-plus linear systems, set covering, mixed integer linear programming

Classification:

15A80, 90C24, 90C11

paper.pdf

References:

  1. F. Baccelli, G. Cohen, G. J. Olsder and J. P. Quadrat: Synchronization and Linearity: An Algebra for Discrete Event Systems. Wiley, Chichester 1992.   CrossRef
  2. P. Butkovič: Max-linear Systems: Theory and Algorithms. Springer, Berlin 2010.   CrossRef
  3. R. A. Cuninghame-Green: Minimax Algebra, Lecture Notes in Economics and Mathematical Systems, Vol. 166. Springer, Berlin 1979.   CrossRef
  4. M. Gondran and M. Minoux: Graphs, Dioids and Semirings: New Models and Algorithms. Springer, New York 2008.   CrossRef
  5. J. Gotoh and S. Uryasev: Two pairs of families of polyhedral norms versus $\ell_p$-norms: proximity and applications in optimization. Math. Program. 156 (2016), 391-431.   DOI:10.1007/s10107-015-0899-9
  6. B. Heidergott, G. J. Olsder and J. van der Woude: Max Plus at Work: Modeling and Analysis of Synchronized Systems. Princeton University Press, Princeton 2005.   CrossRef
  7. M. Joswig: Essentials of Tropical Combinatorics. American Mathematical Society, 2021.   CrossRef
  8. N. Krivulin: Methods of Idempotent Algebra for Problems in Modeling and Analysis of Complex Systems. Saint Petersburg University Press, St. Petersburg 2009. (in Russian)   CrossRef
  9. N. Krivulin: Solution of linear equations and inequalities in idempotent vector spaces. Int. J. Appl. Math. Inform. 7 (2013), 14-23.   CrossRef
  10. P. Li: A note on resolving the inconsistency of one-sided max-plus linear equations. Kybernetika 55 (2019), 531-539.   DOI:10.14736/kyb-2019-3-0531
  11. P. Li: Solving the sensor cover energy problem via integer linear programming. Kybernetika 57 (2021), 568-593.   DOI:10.14736/kyb-2021-4-0568
  12. P. Li: Linear optimization over the approximate solutions of a system of max-min equations. Fuzzy Sets Systems 484 (2024), 108946.   DOI:10.1016/j.fss.2024.108946
  13. P. Li and S. C. Fang: On the resolution and optimization of a system of fuzzy relational equations with sup-$T$ composition. Fuzzy Optim. Decision Making 7 (2008), 169-214.   DOI:10.1007/s10700-008-9029-y
  14. A. Tsiamis and P. Maragos: Sparsity in max-plus algebra and systems. Discrete Event Dynamic Systems 29 (2019), 163-189.   DOI:10.1007/s10626-019-00281-1
  15. N. Tsilivis, A. Tsiamis and P. Maragos: Toward a sparsity theory on weighted lattices. J. Math. Imaging Vision 64 (2022), 705-717.   DOI:10.1007/s10851-022-01075-1