We consider a generalized poset sorting problem (GPS), in which we are given a query graph $G = (V, E)$ and an unknown poset $\mathcal{P}(V, \prec)$ that is defined on the same vertex set $V$, and the goal is to make as few queries as possible to edges in $G$ in order to fully recover $\mathcal{P}$, where each query $(u, v)$ returns the relation between $u, v$, i.e., $u \prec v$, $v \prec u$ or $u \not \sim v$. This generalizes both the poset sorting problem [Faigle et al., SICOMP 88] and the generalized sorting problem [Huang et al., FOCS 11]. We give algorithms with $\tilde{O}(n\cdot \mathrm{poly}(k))$ query complexity when $G$ is a complete bipartite graph or $G$ is stochastic under the \ER model, where $k$ is the \emph{width} of the poset, and these generalize [Daskalakis et al., SICOMP 11] which only studies complete graph $G$. Both results are based on a unified framework that reduces the poset sorting to partitioning the vertices with respect to a given pivot element, which may be of independent interest. Our study of GPS also leads to a new $\tilde{O}(n^{1 - 1 / (2W)})$ competitive ratio for the so-called weighted generalized sorting problem where $W$ is the number of distinct weights in the query graph. This problem was considered as an open question in [Charikar et al., JCSS 02], and our result makes important progress as it yields the first nontrivial $\tilde{O}(n)$ ratio for general weighted query graphs (and better ratio if $W$ is bounded). We obtain this via an $\tilde{O}(nk + n^{1.5})$ query complexity algorithm for the case where every edge in $G$ is guaranteed to be comparable in the poset, which generalizes the state-of-the-art $\tilde{O}(n^{1.5})$ bound for generalized sorting [Huang et al., FOCS 11].
翻译:广义偏序排序问题的算法
翻译后的摘要:
我们考虑广义偏序排序问题 (GPS),其中我们有一个查询图 $G=(V,E)$ 和一个未知偏序 $\mathcal{P}(V,\prec)$,该偏序定义在相同的顶点集 $V$ 上,目标是尽可能少地查询 $G$ 中的边,以完全恢复 $\mathcal {P}$,其中每个查询 $(u,v)$ 返回 $u$ 和 $v$ 之间的关系,即 $u \prec v$,$v \prec u$ 或 $u \not \sim v$。这个问题既可以推广为偏序排序问题[Faigle等人,SICOMP 88],也可以推广为广义排序问题[Huang等人,FOCS 11]。我们给出了算法,当 $G$ 是完全二分图或 $G$ 在 \ER 模型下为随机时它们的查询复杂度具有 $\tilde{O}(n\cdot \mathrm{poly}(k))$ 的复杂度,其中 $k$ 是偏序的\emph{宽度},这些一般化结果超越了仅研究完全图 $G$ 的[Daskalakis等人,SICOMP 11]。这两个结果都基于一个统一的框架,将偏序排序归约到相对于给定枢轴元素的顶点划分,这可能具有独立的兴趣。我们对GPS的研究还引导了加权广义排序问题的新的 $\tilde{O}(n^{1 - 1 / (2W)})$ 竞争比,其中 $W$ 是查询图中不同权重的数量。这个问题在[Charikar等人,JCSS 02]中被视为一个开放问题,我们的结果取得了重要进展,因为它为一般加权查询图提供了第一个非平凡的 $\tilde{O}(n)$ 比率(如果 $W$ 有界,则可以得到更好的比率)。我们通过一个 $\tilde{O}(nk + n^{1.5})$ 的查询复杂度算法来处理每个边在偏序中都保证是可比较的情况,这一算法一般化了广义排序的现有最优 $\tilde{O}(n^{1.5})$ 边界[Huang等人,FOCS 11]。