(min, + ) Matrix and Vector Products for Inputs Decomposable into Few Monotone Subsequences
(2024) 29th International Computing and Combinatorics Conference, COCOON 2023 In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 14423 LNCS. p.55-68- Abstract
We study the time complexity of computing the (min, + ) matrix product of two n× n integer matrices in terms of n and the number of monotone subsequences the rows of the first matrix and the columns of the second matrix can be decomposed into. In particular, we show that if each row of the first matrix can be decomposed into at most m1 monotone subsequences and each column of the second matrix can be decomposed into at most m2 monotone subsequences such that all the subsequences are non-decreasing or all of them are non-increasing then the (min, + ) product of the matrices can be computed in O(m1m2n2.569) time. On the other hand, we observe that if all the rows of the first matrix... (More)
We study the time complexity of computing the (min, + ) matrix product of two n× n integer matrices in terms of n and the number of monotone subsequences the rows of the first matrix and the columns of the second matrix can be decomposed into. In particular, we show that if each row of the first matrix can be decomposed into at most m1 monotone subsequences and each column of the second matrix can be decomposed into at most m2 monotone subsequences such that all the subsequences are non-decreasing or all of them are non-increasing then the (min, + ) product of the matrices can be computed in O(m1m2n2.569) time. On the other hand, we observe that if all the rows of the first matrix are non-decreasing and all columns of the second matrix are non-increasing or vice versa then this case is as hard as the general one. Similarly, we also study the time complexity of computing the (min, + ) convolution of two n-dimensional integer vectors in terms of n and the number of monotone subsequences the two vectors can be decomposed into. We show that if the first vector can be decomposed into at most m1 monotone subsequences and the second vector can be decomposed into at most m2 subsequences such that all the subsequences of the first vector are non-decreasing and all the subsequences of the second vector are non-increasing or vice versa then their (min, + ) convolution can be computed in O~ (m1m2n1.5) time. On the other, the case when both vectors are non-decreasing or both of them are non-increasing is as hard as the general case.
(Less)
- author
- Lingas, Andrzej LU and Persson, Mia LU
- organization
- publishing date
- 2024
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- host publication
- Computing and Combinatorics - 29th International Conference, COCOON 2023, Proceedings
- series title
- Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
- editor
- Wu, Weili and Tong, Guangmo
- volume
- 14423 LNCS
- pages
- 14 pages
- publisher
- Springer Science and Business Media B.V.
- conference name
- 29th International Computing and Combinatorics Conference, COCOON 2023
- conference location
- Hawaii, United States
- conference dates
- 2023-12-15 - 2023-12-17
- external identifiers
-
- scopus:85180531292
- ISSN
- 0302-9743
- 1611-3349
- ISBN
- 9783031491924
- DOI
- 10.1007/978-3-031-49193-1_5
- language
- English
- LU publication?
- yes
- id
- 3db16d83-c174-435c-a50f-6b0649f1a89b
- date added to LUP
- 2025-01-15 12:15:03
- date last changed
- 2025-07-31 04:57:56
@inproceedings{3db16d83-c174-435c-a50f-6b0649f1a89b,
abstract = {{<p>We study the time complexity of computing the (min, + ) matrix product of two n× n integer matrices in terms of n and the number of monotone subsequences the rows of the first matrix and the columns of the second matrix can be decomposed into. In particular, we show that if each row of the first matrix can be decomposed into at most m<sub>1</sub> monotone subsequences and each column of the second matrix can be decomposed into at most m<sub>2</sub> monotone subsequences such that all the subsequences are non-decreasing or all of them are non-increasing then the (min, + ) product of the matrices can be computed in O(m<sub>1</sub>m<sub>2</sub>n<sup>2.569</sup>) time. On the other hand, we observe that if all the rows of the first matrix are non-decreasing and all columns of the second matrix are non-increasing or vice versa then this case is as hard as the general one. Similarly, we also study the time complexity of computing the (min, + ) convolution of two n-dimensional integer vectors in terms of n and the number of monotone subsequences the two vectors can be decomposed into. We show that if the first vector can be decomposed into at most m<sub>1</sub> monotone subsequences and the second vector can be decomposed into at most m<sub>2</sub> subsequences such that all the subsequences of the first vector are non-decreasing and all the subsequences of the second vector are non-increasing or vice versa then their (min, + ) convolution can be computed in O~ (m<sub>1</sub>m<sub>2</sub>n<sup>1.5</sup>) time. On the other, the case when both vectors are non-decreasing or both of them are non-increasing is as hard as the general case.</p>}},
author = {{Lingas, Andrzej and Persson, Mia}},
booktitle = {{Computing and Combinatorics - 29th International Conference, COCOON 2023, Proceedings}},
editor = {{Wu, Weili and Tong, Guangmo}},
isbn = {{9783031491924}},
issn = {{0302-9743}},
language = {{eng}},
pages = {{55--68}},
publisher = {{Springer Science and Business Media B.V.}},
series = {{Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)}},
title = {{(min, + ) Matrix and Vector Products for Inputs Decomposable into Few Monotone Subsequences}},
url = {{http://dx.doi.org/10.1007/978-3-031-49193-1_5}},
doi = {{10.1007/978-3-031-49193-1_5}},
volume = {{14423 LNCS}},
year = {{2024}},
}