On Approximating the Dynamic and Discrete Network Flow Problem
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917650008899584 |
|---|---|
| author | Manna, Bubai Roy, Bodhayan Suppakitpaisarn, Vorapong |
| author_facet | Manna, Bubai Roy, Bodhayan Suppakitpaisarn, Vorapong |
| contents | We examine the dynamic network flow problem under the assumption that the flow consists of discrete units. The dynamic network flow problem is commonly addressed in the context of developing evacuation plans, where the flow is typically treated as a continuous quantity. However, real-world scenarios often involve moving groups, such as families, as single units. We demonstrate that solving the dynamic flow problem with this consideration is APX-hard. Conversely, we present a PTAS for instances where the base graph is a path with a constant number of nodes. We introduce a `ready time' constraint to the minsum bin packing problem, meaning certain items cannot be placed in specific bins, develop a PTAS for this modified problem, and apply our algorithms to the discrete and dynamic flow problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_16329 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On Approximating the Dynamic and Discrete Network Flow Problem Manna, Bubai Roy, Bodhayan Suppakitpaisarn, Vorapong Data Structures and Algorithms Computational Complexity Computational Geometry We examine the dynamic network flow problem under the assumption that the flow consists of discrete units. The dynamic network flow problem is commonly addressed in the context of developing evacuation plans, where the flow is typically treated as a continuous quantity. However, real-world scenarios often involve moving groups, such as families, as single units. We demonstrate that solving the dynamic flow problem with this consideration is APX-hard. Conversely, we present a PTAS for instances where the base graph is a path with a constant number of nodes. We introduce a `ready time' constraint to the minsum bin packing problem, meaning certain items cannot be placed in specific bins, develop a PTAS for this modified problem, and apply our algorithms to the discrete and dynamic flow problem. |
| title | On Approximating the Dynamic and Discrete Network Flow Problem |
| topic | Data Structures and Algorithms Computational Complexity Computational Geometry |
| url | https://arxiv.org/abs/2404.16329 |