A (Weakly) Polynomial Algorithm for AIVF Coding
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911873229651968 |
|---|---|
| author | Dolatabadi, Reza Hosseini Golin, Mordecai J. Zamani, Arian |
| author_facet | Dolatabadi, Reza Hosseini Golin, Mordecai J. Zamani, Arian |
| contents | It is possible to improve upon Tunstall coding using a collection of multiple parse trees. The best such results so far are Iwata and Yamamoto's maximum cost AIVF codes. The most efficient algorithm for designing such codes is an iterative one that could run in exponential time. In this paper, we show that this problem fits into the framework of a newly developed technique that uses linear programming with the Ellipsoid method to solve the minimum cost Markov chain problem. This permits constructing maximum cost AIVF codes in (weakly) polynomial time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_06805 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A (Weakly) Polynomial Algorithm for AIVF Coding Dolatabadi, Reza Hosseini Golin, Mordecai J. Zamani, Arian Data Structures and Algorithms F.2; E.4 It is possible to improve upon Tunstall coding using a collection of multiple parse trees. The best such results so far are Iwata and Yamamoto's maximum cost AIVF codes. The most efficient algorithm for designing such codes is an iterative one that could run in exponential time. In this paper, we show that this problem fits into the framework of a newly developed technique that uses linear programming with the Ellipsoid method to solve the minimum cost Markov chain problem. This permits constructing maximum cost AIVF codes in (weakly) polynomial time. |
| title | A (Weakly) Polynomial Algorithm for AIVF Coding |
| topic | Data Structures and Algorithms F.2; E.4 |
| url | https://arxiv.org/abs/2405.06805 |