Answers are grounded in this paper and cite their sources.
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 2O(√log n\,loglog n). This improves over the O(n^ε) approximation rate that was previously known for every fixed ε>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.
No takes yet. Share an insight, caveat, or question.
Lars Rohwedder (2026) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: