On sparsity of approximate solutions to max-plus linear systems

Pingke Li

Kybernetika (2024)

  • Issue: 3, page 412-425
  • ISSN: 0023-5954

Abstract

top
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 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.

How to cite

top

Li, Pingke. "On sparsity of approximate solutions to max-plus linear systems." Kybernetika (2024): 412-425. <http://eudml.org/doc/299290>.

@article{Li2024,
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.},
author = {Li, Pingke},
journal = {Kybernetika},
keywords = {max-plus algebra; max-plus linear systems; sparsity; set covering; mixed integer linear programming},
language = {eng},
number = {3},
pages = {412-425},
publisher = {Institute of Information Theory and Automation AS CR},
title = {On sparsity of approximate solutions to max-plus linear systems},
url = {http://eudml.org/doc/299290},
year = {2024},
}

TY - JOUR
AU - Li, Pingke
TI - On sparsity of approximate solutions to max-plus linear systems
JO - Kybernetika
PY - 2024
PB - Institute of Information Theory and Automation AS CR
IS - 3
SP - 412
EP - 425
AB - 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.
LA - eng
KW - max-plus algebra; max-plus linear systems; sparsity; set covering; mixed integer linear programming
UR - http://eudml.org/doc/299290
ER -

References

top
  1. Baccelli, F., Cohen, G., Olsder, G. J., Quadrat, J. P., Synchronization and Linearity: An Algebra for Discrete Event Systems., Wiley, Chichester 1992. MR1204266
  2. Butkovič, P., Max-linear Systems: Theory and Algorithms., Springer, Berlin 2010. Zbl1202.15032MR2681232
  3. Cuninghame-Green, R. A., Minimax Algebra, Lecture Notes in Economics and Mathematical Systems, Vol. 166., Springer, Berlin 1979. MR0580321
  4. Gondran, M., Minoux, M., Graphs, Dioids and Semirings: New Models and Algorithms., Springer, New York 2008. Zbl1201.16038MR2389137
  5. Gotoh, J., Uryasev, S., , Math. Program. 156 (2016), 391-431. MR3459206DOI
  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. MR2188299
  7. Joswig, M., Essentials of Tropical Combinatorics., American Mathematical Society, 2021. MR4423372
  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., , Kybernetika 55 (2019), 531-539. MR4015997DOI
  11. Li, P., , Kybernetika 57 (2021), 568-593. DOI
  12. Li, P., , Fuzzy Sets Systems 484 (2024), 108946. MR4721551DOI
  13. Li, P., Fang, S. C., , Fuzzy Optim. Decision Making 7 (2008), 169-214. Zbl1169.90493MR2403173DOI
  14. Tsiamis, A., Maragos, P., , Discrete Event Dynamic Systems 29 (2019), 163-189. MR3969320DOI
  15. Tsilivis, N., Tsiamis, A., Maragos, P., , J. Math. Imaging Vision 64 (2022), 705-717. MR4476213DOI

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.