Minsum Problem for Discrete and Weighted Set Flow on Dynamic Path Network
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_ | 1866913414147735552 |
|---|---|
| author | Manna, Bubai Roy, Bodhayan Suppakitpaisarn, Vorapong |
| author_facet | Manna, Bubai Roy, Bodhayan Suppakitpaisarn, Vorapong |
| contents | In this research, we examine the minsum flow problem in dynamic path networks where flows are represented as discrete and weighted sets. The minsum flow problem has been widely studied for its relevance in finding evacuation routes during emergencies such as earthquakes. However, previous approaches often assume that individuals are separable and identical, which does not adequately account for the fact that some groups of people, such as families, need to move together and that some groups may be more important than others. To address these limitations, we modify the minsum flow problem to support flows represented as discrete and weighted sets. We also propose a 2-approximation pseudo-polynomial time algorithm to solve this modified problem for path networks with uniform capacity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_02177 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Minsum Problem for Discrete and Weighted Set Flow on Dynamic Path Network Manna, Bubai Roy, Bodhayan Suppakitpaisarn, Vorapong Data Structures and Algorithms Discrete Mathematics In this research, we examine the minsum flow problem in dynamic path networks where flows are represented as discrete and weighted sets. The minsum flow problem has been widely studied for its relevance in finding evacuation routes during emergencies such as earthquakes. However, previous approaches often assume that individuals are separable and identical, which does not adequately account for the fact that some groups of people, such as families, need to move together and that some groups may be more important than others. To address these limitations, we modify the minsum flow problem to support flows represented as discrete and weighted sets. We also propose a 2-approximation pseudo-polynomial time algorithm to solve this modified problem for path networks with uniform capacity. |
| title | Minsum Problem for Discrete and Weighted Set Flow on Dynamic Path Network |
| topic | Data Structures and Algorithms Discrete Mathematics |
| url | https://arxiv.org/abs/2407.02177 |