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

Cité par Sources :