← 研踪 PaperTrailarXiv:2611.03212 · v1
Approximating Submodular Orienteering via Rooted Subgraph Decomposition
首次提交 2026-11-02 22:35
版本更新 2026-11-02 22:35
雷达观测 2026-11-04 23:41
摘要
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.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-02 22:35 · 最新观测版本
Approximating Submodular Orienteering via Rooted Subgraph Decomposition
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.
查看此版本解读 →查看此版本原文 ↗