论文标题
新的近似和硬度分区问题的硬度结果
New Approximations and Hardness Results for Submodular Partitioning Problems
论文作者
论文摘要
We consider the following class of submodular k-multiway partitioning problems: (Sub-$k$-MP) $\min \sum_{i=1}^k f(S_i): S_1 \uplus S_2 \uplus \cdots \uplus S_k = V \mbox{ and } S_i \neq \emptyset \mbox{ for all }i\in [k] $。这里$ f $是一种非负suppoular函数，$ \ uplus $表示脱节集合的结合。因此，目标是将$ v $划分为$ k $ non-nen-nter-sets $ s_1，s_2，\ ldots，s_k $，以便最小化$ \ sum_ {i = 1}^k f（s_i）$。这些问题由Zhao等人引入。部分是由应用于网络可靠性分析，VLSI设计，削减超图和其他分区问题的动机。 在这项工作中，我们重新审视了这类问题，并在价值Oracle模型中的近似硬度上阐明了一些启示。在功能$ f $是单调或对称的特殊设置中，我们为子$ K $ -MP提供了新的无条件硬度结果。对于对称函数，我们显示的是，给定任何$ε> 0 $，任何实现$（2 -ε）$ - 近似的算法都需要在值Oracle模型中指数级的查询。对于单调目标，我们表明，给定任何$ε> 0 $，任何实现$（4/3-ε）$ - 近似值的算法都需要在值Oracle模型中呈指数级的查询。 然后，我们将sub-k $ -mp扩展到更大的分区问题，其中$ f_i（s_i）$可能会有所不同，并且有一个更一般的分区约束$ s_1 \ uplus s_2 \ uplus s_2 \ uplus \ cdots \ cdots \ cdots \ cdots \ cdots \ uplus s_k \ in \ in \ mathcal $ nmats $ sub for \ nationq for \ nationq for \ nationq for \ nationq for in \ maths $ s for {可行的套装。我们提供了一个黑匣子减少，使我们能够利用文献中的几个现有结果；导致此类问题的新近似值。
We consider the following class of submodular k-multiway partitioning problems: (Sub-$k$-MP) $\min \sum_{i=1}^k f(S_i): S_1 \uplus S_2 \uplus \cdots \uplus S_k = V \mbox{ and } S_i \neq \emptyset \mbox{ for all }i\in [k]$. Here $f$ is a non-negative submodular function, and $\uplus$ denotes the union of disjoint sets. Hence the goal is to partition $V$ into $k$ non-empty sets $S_1,S_2,\ldots,S_k$ such that $\sum_{i=1}^k f(S_i)$ is minimized. These problems were introduced by Zhao et al. partly motivated by applications to network reliability analysis, VLSI design, hypergraph cut, and other partitioning problems. In this work we revisit this class of problems and shed some light onto their hardness of approximation in the value oracle model. We provide new unconditional hardness results for Sub-$k$-MP in the special settings where the function $f$ is either monotone or symmetric. For symmetric functions we show that given any $ε> 0$, any algorithm achieving a $(2 - ε)$-approximation requires exponentially many queries in the value oracle model. For monotone objectives we show that given any $ε> 0$, any algorithm achieving a $(4/3 - ε)$-approximation requires exponentially many queries in the value oracle model. We then extend Sub-$k$-MP to a larger class of partitioning problems, where the functions $f_i(S_i)$ can be different, and there is a more general partitioning constraint $ S_1 \uplus S_2 \uplus \cdots \uplus S_k \in \mathcal{F}$ for some family $\mathcal{F} \subseteq 2^V$ of feasible sets. We provide a black box reduction that allows us to leverage several existing results from the literature; leading to new approximations for this class of problems.
