论文标题
单调下调成本的最短周期
Shortest Cycles With Monotone Submodular Costs
论文作者
论文摘要
我们介绍了最短周期问题的以下supproular概括。对于非导向图$ g $的边缘（或顶点）上定义的非负单调的子模块成本函数$ f $，我们寻求$ c $ c $ c $ c $ in $ g $的最低成本$ \ textsf {optsf {opt} = f（c）$。我们给出了一个算法，该算法给出了$ n $ -vertex图$ g $，parameter $ \ varepsilon> 0 $，以及由oracle代表的函数$ f $，时间$ n^{\ nathcal {\ mathcal {O}（\ log log log 1/\ varepsilon）} $ in Cycy $ c $ in Cycle $ c $ c $ g $ c $ f pe q $ f eq pe q $ f eq pe（c）c）c） （1+ \ varepsilon）\ cdot \ textsf {opt} $。这与密切相关的单调性少数$（S，T）$ - 路径问题的不可Ximimibibibibibibimition形成鲜明对比的是，这需要指数为Oracle，以找到$ n^{2/3- \ varepsilon} $ - 近似[GOEL等人[Goel等人，focs focs focs 2009]。我们使用匹配的下限对算法进行补充。我们表明，在每一个$ \ varepsilon> 0 $中，获得$（1+ \ varepsilon）$ - 近似需要至少$ n^{ω（\ log 1/ \ varepsilon）} $ queries to oracle。当功能$ f $是整数值时，我们的算法会产生成本$ \ textsf {optsf {opt} $的周期，可以在时间$ n^{\ mathcal {o}（\ log \ log \ textsf {opt}）} $中找到。特别是，对于$ \ textsf {opt} = n^{\ mathcal {o}（1）} $，这给出了一个quasipolynomial imial时间算法，计算一个最低supsodular成本的周期。有趣的是，虽然级别化时间算法通常可以很好地表明可以达到多项式时间的复杂性，但我们表明，即使$ n^{\ Mathcal {o}（\ log n）} $查询也需要$ n^{\ Mathcal {o}（\ log n）} $查询。
We introduce the following submodular generalization of the Shortest Cycle problem. For a nonnegative monotone submodular cost function $f$ defined on the edges (or the vertices) of an undirected graph $G$, we seek for a cycle $C$ in $G$ of minimum cost $\textsf{OPT}=f(C)$. We give an algorithm that given an $n$-vertex graph $G$, parameter $\varepsilon > 0$, and the function $f$ represented by an oracle, in time $n^{\mathcal{O}(\log 1/\varepsilon)}$ finds a cycle $C$ in $G$ with $f(C)\leq (1+\varepsilon)\cdot \textsf{OPT}$. This is in sharp contrast with the non-approximability of the closely related Monotone Submodular Shortest $(s,t)$-Path problem, which requires exponentially many queries to the oracle for finding an $n^{2/3-\varepsilon}$-approximation [Goel et al., FOCS 2009]. We complement our algorithm with a matching lower bound. We show that for every $\varepsilon > 0$, obtaining a $(1+\varepsilon)$-approximation requires at least $n^{Ω(\log 1/ \varepsilon)}$ queries to the oracle. When the function $f$ is integer-valued, our algorithm yields that a cycle of cost $\textsf{OPT}$ can be found in time $n^{\mathcal{O}(\log \textsf{OPT})}$. In particular, for $\textsf{OPT}=n^{\mathcal{O}(1)}$ this gives a quasipolynomial-time algorithm computing a cycle of minimum submodular cost. Interestingly, while a quasipolynomial-time algorithm often serves as a good indication that a polynomial time complexity could be achieved, we show a lower bound that $n^{\mathcal{O}(\log n)}$ queries are required even when $\textsf{OPT} = \mathcal{O}(n)$.
