Improving graph path optimization with new subgraph decomposition method
Approximating Submodular Orienteering via Rooted Subgraph Decomposition
Data Structures and Algorithms
Summary
This work tackles the problem of finding a path in a network that visits valuable locations under certain travel constraints. The authors improve existing methods by creating a new way to break down a network into smaller parts, making it easier to find better paths efficiently. Their algorithm runs in reasonable time and provides a stronger guarantee on the quality of the solutions compared to previous approaches. This can help in planning routes that maximize collected rewards or information within a travel budget.
What this means in practice
- •For network schedulers: Develop efficient route plans in communication or transportation networks where collected information has diminishing returns.
- •For robotics navigation teams: Enable robots to plan paths that gather valuable data or resources while respecting travel length limits using improved approximation methods.
A theory result. No direct application yet.
Authors
Lars Rohwedder
Abstract
The Submodular Orienteering problem asks for an $s$-$t$ walk in a directed graph that maximizes a monotone submodular function over the visited vertices subject to a bound on its length. We give a deterministic polynomial-time approximation algorithm with subpolynomial approximation rate $2^{O(\sqrt{\log n\,\log\log n})}$. This improves over the $O(n^\varepsilon)$ approximation rate that was previously known for every fixed $\varepsilon>0$. We prove a decomposition lemma that partitions a directed graph into rooted subgraphs such that every path intersects only polylogarithmically many such subgraphs. Our algorithm uses this decomposition to construct its recursive subproblems.