Source Coding with Free Bits and the Multi-Way Number Partitioning Problem
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2020
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908794506706944 |
|---|---|
| author | Ahmadypour, Niloufar Gohari, Amin |
| author_facet | Ahmadypour, Niloufar Gohari, Amin |
| contents | We introduce a new variant of variable-length source coding for sending a source over two parallel channels, one of which is costly and the other free. We give a complete solution to this problem. Next, we relate the problem to the number partitioning problem, which is the task of dividing a given list of numbers into a pre-specified number of subsets such that the sum of the numbers in each subset is as nearly equal as possible. We introduce two new objective functions for this problem and show that an adapted version of the Huffman coding algorithm (with a runtime of $\mathcal{O}(n \log n)$ for input size $n$) produces the optimal solution for one objective function, and a nearly optimal solution for the other objective function. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2009_02710 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | Source Coding with Free Bits and the Multi-Way Number Partitioning Problem Ahmadypour, Niloufar Gohari, Amin Data Structures and Algorithms Information Theory Combinatorics We introduce a new variant of variable-length source coding for sending a source over two parallel channels, one of which is costly and the other free. We give a complete solution to this problem. Next, we relate the problem to the number partitioning problem, which is the task of dividing a given list of numbers into a pre-specified number of subsets such that the sum of the numbers in each subset is as nearly equal as possible. We introduce two new objective functions for this problem and show that an adapted version of the Huffman coding algorithm (with a runtime of $\mathcal{O}(n \log n)$ for input size $n$) produces the optimal solution for one objective function, and a nearly optimal solution for the other objective function. |
| title | Source Coding with Free Bits and the Multi-Way Number Partitioning Problem |
| topic | Data Structures and Algorithms Information Theory Combinatorics |
| url | https://arxiv.org/abs/2009.02710 |