Knapsacks, Max-Flow and Circular Mapper Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915067623112704 |
|---|---|
| author | Pegoraro, Matteo Fajstrup, Lisbeth |
| author_facet | Pegoraro, Matteo Fajstrup, Lisbeth |
| contents | Motivated by the challenge of analyzing data sets with periodic boundary conditions to investigate transportation properties, we introduce a concept of circular max-flow for graphs mapped onto the circle. Unlike classical max-flow formulations, circular max-flow does not require the specification of a source and a target. Instead, it is defined by considering the flow through the slices of graph obtained via the fibers of its associated map onto the circle. Circular max-flow can be formulated as a minimum-cost circulation problem, allowing for an Integer Flow Theorem to be derived directly from classical results concerning negative cost cycles. While we hypothesize that all minimum-cost circulation problems with integer costs can be reformulated as circular flow problems, this broader equivalence is left for future exploration. In the core section of this work, we investigate the relationship between circular max-flow and the flow obtained by stacking infinite copies of the considered graph. We establish an equivalence between these two flows, which also provides an alternative proof of the Integer Flow Theorem. Additionally, we demonstrate connections between circular max-flow and a specific family of multidimensional knapsack problems. This connection shows that for this class of knapsack problems, solving the relaxed version is sufficient, avoiding the need for integer optimization. Finally, we test our definitions in some simulated scenarios related to the initial data analysis problem, extending a pipeline appeared previous works in materials science. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_04357 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Knapsacks, Max-Flow and Circular Mapper Graphs Pegoraro, Matteo Fajstrup, Lisbeth Algebraic Topology Motivated by the challenge of analyzing data sets with periodic boundary conditions to investigate transportation properties, we introduce a concept of circular max-flow for graphs mapped onto the circle. Unlike classical max-flow formulations, circular max-flow does not require the specification of a source and a target. Instead, it is defined by considering the flow through the slices of graph obtained via the fibers of its associated map onto the circle. Circular max-flow can be formulated as a minimum-cost circulation problem, allowing for an Integer Flow Theorem to be derived directly from classical results concerning negative cost cycles. While we hypothesize that all minimum-cost circulation problems with integer costs can be reformulated as circular flow problems, this broader equivalence is left for future exploration. In the core section of this work, we investigate the relationship between circular max-flow and the flow obtained by stacking infinite copies of the considered graph. We establish an equivalence between these two flows, which also provides an alternative proof of the Integer Flow Theorem. Additionally, we demonstrate connections between circular max-flow and a specific family of multidimensional knapsack problems. This connection shows that for this class of knapsack problems, solving the relaxed version is sufficient, avoiding the need for integer optimization. Finally, we test our definitions in some simulated scenarios related to the initial data analysis problem, extending a pipeline appeared previous works in materials science. |
| title | Knapsacks, Max-Flow and Circular Mapper Graphs |
| topic | Algebraic Topology |
| url | https://arxiv.org/abs/2312.04357 |