Article
Full entry |
PDF
(0.4 MB)
Feedback
PDF
(0.4 MB)
Feedback
Keywords:
max-plus algebra; max-plus linear systems; sparsity; set covering; mixed integer linear programming
max-plus algebra; max-plus linear systems; sparsity; set covering; mixed integer linear programming
Summary:
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.
References:
[1] Baccelli, F., Cohen, G., Olsder, G. J., Quadrat, J. P.: Synchronization and Linearity: An Algebra for Discrete Event Systems. Wiley, Chichester 1992. MR 1204266
[2] Butkovič, P.: Max-linear Systems: Theory and Algorithms. Springer, Berlin 2010. MR 2681232 | Zbl 1202.15032
[3] Cuninghame-Green, R. A.: Minimax Algebra, Lecture Notes in Economics and Mathematical Systems, Vol. 166. Springer, Berlin 1979. MR 0580321
[4] Gondran, M., Minoux, M.: Graphs, Dioids and Semirings: New Models and Algorithms. Springer, New York 2008. MR 2389137 | Zbl 1201.16038
[5] Gotoh, J., Uryasev, S.: Two pairs of families of polyhedral norms versus $\ell_p$-norms: proximity and applications in optimization. Math. Program. 156 (2016), 391-431. DOI | MR 3459206
[6] Heidergott, B., Olsder, G. J., Woude, J. van der: Max Plus at Work: Modeling and Analysis of Synchronized Systems. Princeton University Press, Princeton 2005. MR 2188299
[7] Joswig, M.: Essentials of Tropical Combinatorics. American Mathematical Society, 2021. MR 4423372
[8] Krivulin, N.: Methods of Idempotent Algebra for Problems in Modeling and Analysis of Complex Systems. Saint Petersburg University Press, St. Petersburg 2009. (in Russian)
[9] Krivulin, N.: Solution of linear equations and inequalities in idempotent vector spaces. Int. J. Appl. Math. Inform. 7 (2013), 14-23.
[10] Li, P.: A note on resolving the inconsistency of one-sided max-plus linear equations. Kybernetika 55 (2019), 531-539. DOI | MR 4015997
[11] Li, P.: Solving the sensor cover energy problem via integer linear programming. Kybernetika 57 (2021), 568-593. DOI
[12] Li, P.: Linear optimization over the approximate solutions of a system of max-min equations. Fuzzy Sets Systems 484 (2024), 108946. DOI | MR 4721551
[13] Li, P., Fang, S. C.: 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 | MR 2403173 | Zbl 1169.90493
[14] Tsiamis, A., Maragos, P.: Sparsity in max-plus algebra and systems. Discrete Event Dynamic Systems 29 (2019), 163-189. DOI | MR 3969320
[15] Tsilivis, N., Tsiamis, A., Maragos, P.: Toward a sparsity theory on weighted lattices. J. Math. Imaging Vision 64 (2022), 705-717. DOI | MR 4476213
Search
Partner of
