Extending Robinson Spaces: Complexity and Algorithmic Solutions for Non-Symmetric Dissimilarity Spaces
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912145477730304 |
|---|---|
| author | Brucker, Francois Préa, Pascal Caro, Christopher Thraves |
| author_facet | Brucker, Francois Préa, Pascal Caro, Christopher Thraves |
| contents | In this work, we extend the concept of Robinson spaces to asymmetric dissimilarities, enhancing their applicability in representing and analyzing complex data. Within this generalized framework, we introduce two different problems that extend the classical seriation problem: an optimization problem and a decision problem. We establish that these problems are NP-hard and NP-complete, respectively. Despite this complexity results, we identify several non-trivial instances where these problems can be solved in polynomial time, providing valuable insights into their tractability. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_04118 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Extending Robinson Spaces: Complexity and Algorithmic Solutions for Non-Symmetric Dissimilarity Spaces Brucker, Francois Préa, Pascal Caro, Christopher Thraves Discrete Mathematics Combinatorics In this work, we extend the concept of Robinson spaces to asymmetric dissimilarities, enhancing their applicability in representing and analyzing complex data. Within this generalized framework, we introduce two different problems that extend the classical seriation problem: an optimization problem and a decision problem. We establish that these problems are NP-hard and NP-complete, respectively. Despite this complexity results, we identify several non-trivial instances where these problems can be solved in polynomial time, providing valuable insights into their tractability. |
| title | Extending Robinson Spaces: Complexity and Algorithmic Solutions for Non-Symmetric Dissimilarity Spaces |
| topic | Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2412.04118 |