Geodesic
On sparsity of approximate solutions to max-plus linear systems
Kybernetika, Tome 60 (2024) no. 3, pp. 412-425
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.14736/kyb-2024-3-0412
Classification : 15A80, 90C11, 90C24
Keywords: max-plus algebra; max-plus linear systems; sparsity; set covering; mixed integer linear programming 
@article{10_14736_kyb_2024_3_0412,
     author = {Li, Pingke},
     title = {On sparsity of approximate solutions to max-plus linear systems},
     journal = {Kybernetika},
     pages = {412--425},
     year = {2024},
     volume = {60},
     number = {3},
     doi = {10.14736/kyb-2024-3-0412},
     mrnumber = {4777316},
     zbl = {07893464},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.14736/kyb-2024-3-0412/}
}
TY  - JOUR
AU  - Li, Pingke
TI  - On sparsity of approximate solutions to max-plus linear systems
JO  - Kybernetika
PY  - 2024
SP  - 412
EP  - 425
VL  - 60
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.14736/kyb-2024-3-0412/
DO  - 10.14736/kyb-2024-3-0412
LA  - en
ID  - 10_14736_kyb_2024_3_0412
ER  - 
%0 Journal Article
%A Li, Pingke
%T On sparsity of approximate solutions to max-plus linear systems
%J Kybernetika
%D 2024
%P 412-425
%V 60
%N 3
%U http://geodesic.mathdoc.fr/articles/10.14736/kyb-2024-3-0412/
%R 10.14736/kyb-2024-3-0412
%G en
%F 10_14736_kyb_2024_3_0412
Li, Pingke. On sparsity of approximate solutions to max-plus linear systems. Kybernetika, Tome 60 (2024) no. 3, pp. 412-425. doi: 10.14736/kyb-2024-3-0412

[1] Baccelli, F., Cohen, G., Olsder, G. J., Quadrat, J. P.: Synchronization and Linearity: An Algebra for Discrete Event Systems. Wiley, Chichester 1992. | MR

[2] Butkovič, P.: Max-linear Systems: Theory and Algorithms. Springer, Berlin 2010. | MR | Zbl

[3] Cuninghame-Green, R. A.: Minimax Algebra, Lecture Notes in Economics and Mathematical Systems, Vol. 166. Springer, Berlin 1979. | MR

[4] Gondran, M., Minoux, M.: Graphs, Dioids and Semirings: New Models and Algorithms. Springer, New York 2008. | MR | Zbl

[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

[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

[7] Joswig, M.: Essentials of Tropical Combinatorics. American Mathematical Society, 2021. | MR

[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

[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

[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 | Zbl

[14] Tsiamis, A., Maragos, P.: Sparsity in max-plus algebra and systems. Discrete Event Dynamic Systems 29 (2019), 163-189. | DOI | MR

[15] Tsilivis, N., Tsiamis, A., Maragos, P.: Toward a sparsity theory on weighted lattices. J. Math. Imaging Vision 64 (2022), 705-717. | DOI | MR

Cité par Sources :