Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2511.18099 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918214963822592 |
|---|---|
| author | Gokavarapu, Chandrasekhar Rao, D. Madhusudhana |
| author_facet | Gokavarapu, Chandrasekhar Rao, D. Madhusudhana |
| contents | Classical shortest-path methods rely on binary tropical semirings $(\min,+)$, whose dyadic structure limits them to pairwise cost interactions. However, many real-world systems, including logistics, supply chains, communication networks, and reliability-aware infrastructures, exhibit inherently ternary dependencies among cost, time, and risk that cannot be decomposed into pairwise components.
This paper introduces the \emph{Ternary Tropical Gamma Semiring} (TTGS), a $Γ$-indexed algebraic structure that generalizes tropical semirings by replacing binary additive composition with a non-separable ternary operator. We establish the axioms of TTGS, prove associativity, distributivity, and monotonicity, and show that TTGS forms a well-structured foundation for multi-parameter optimization.
Building on this framework, we develop TTGS-Pathfinder, a ternary analogue of the Bellman--Ford algorithm. We derive its dynamic-programming recurrence, prove correctness through an invariant-based argument, analyze convergence under the TTGS order, and obtain an $O(n^2 m)$ complexity bound.
Applications demonstrate that TTGS naturally models systems whose behaviour depends on triadic cost interactions, offering a principled alternative to binary tropical, vector, or scalarized multi-objective methods. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_18099 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Ternary Gamma Semiring Framework for Solving Multi-Objective Network Optimization Problems Gokavarapu, Chandrasekhar Rao, D. Madhusudhana Optimization and Control 16Y60, 08A72, Secondary: 90C35, 68W40, 15A80 Classical shortest-path methods rely on binary tropical semirings $(\min,+)$, whose dyadic structure limits them to pairwise cost interactions. However, many real-world systems, including logistics, supply chains, communication networks, and reliability-aware infrastructures, exhibit inherently ternary dependencies among cost, time, and risk that cannot be decomposed into pairwise components. This paper introduces the \emph{Ternary Tropical Gamma Semiring} (TTGS), a $Γ$-indexed algebraic structure that generalizes tropical semirings by replacing binary additive composition with a non-separable ternary operator. We establish the axioms of TTGS, prove associativity, distributivity, and monotonicity, and show that TTGS forms a well-structured foundation for multi-parameter optimization. Building on this framework, we develop TTGS-Pathfinder, a ternary analogue of the Bellman--Ford algorithm. We derive its dynamic-programming recurrence, prove correctness through an invariant-based argument, analyze convergence under the TTGS order, and obtain an $O(n^2 m)$ complexity bound. Applications demonstrate that TTGS naturally models systems whose behaviour depends on triadic cost interactions, offering a principled alternative to binary tropical, vector, or scalarized multi-objective methods. |
| title | A Ternary Gamma Semiring Framework for Solving Multi-Objective Network Optimization Problems |
| topic | Optimization and Control 16Y60, 08A72, Secondary: 90C35, 68W40, 15A80 |
| url | https://arxiv.org/abs/2511.18099 |