Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2501.16911 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913668382326784 |
|---|---|
| author | Vilkas, Timo |
| author_facet | Vilkas, Timo |
| contents | Consider a simple finite graph and its nodes to represent identical water barrels (containing different amounts of water) on a level plane. Each edge corresponds to a (locked, water-filled) pipe connecting two barrels below the plane. We fix one node $v$ and consider the optimization problem relating to the maximum value to which the level in $v$ can be raised without pumps, i.e. by opening/closing pipes in a suitable order. This fairly natural optimization problem originated from the analysis of an opinion formation process and proved to be not only sufficiently intricate in order to be of independent interest, but also difficult from an algorithmic point of view. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_16911 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Water transport on finite graphs Vilkas, Timo Combinatorics Optimization and Control 05C35, 05C85, 91A68 Consider a simple finite graph and its nodes to represent identical water barrels (containing different amounts of water) on a level plane. Each edge corresponds to a (locked, water-filled) pipe connecting two barrels below the plane. We fix one node $v$ and consider the optimization problem relating to the maximum value to which the level in $v$ can be raised without pumps, i.e. by opening/closing pipes in a suitable order. This fairly natural optimization problem originated from the analysis of an opinion formation process and proved to be not only sufficiently intricate in order to be of independent interest, but also difficult from an algorithmic point of view. |
| title | Water transport on finite graphs |
| topic | Combinatorics Optimization and Control 05C35, 05C85, 91A68 |
| url | https://arxiv.org/abs/2501.16911 |