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]。

0
下载
关闭预览

相关内容

专知会员服务
50+阅读 · 2020年12月14日
【大规模数据系统,552页ppt】Large-scale Data Systems
专知会员服务
60+阅读 · 2019年12月21日
论文浅尝 | Temporal Knowledge Graph Completion Using Box Embeddings
开放知识图谱
1+阅读 · 2022年11月4日
Flutter 组件: Autocomplete 自动填充 | 开发者说·DTalk
谷歌开发者
0+阅读 · 2022年10月28日
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
AI界的State of the Art都在这里了
机器之心
12+阅读 · 2018年12月10日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Arxiv
0+阅读 · 2023年5月23日
Arxiv
0+阅读 · 2023年5月22日
Arxiv
0+阅读 · 2023年5月19日
VIP会员
相关资讯
论文浅尝 | Temporal Knowledge Graph Completion Using Box Embeddings
开放知识图谱
1+阅读 · 2022年11月4日
Flutter 组件: Autocomplete 自动填充 | 开发者说·DTalk
谷歌开发者
0+阅读 · 2022年10月28日
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
AI界的State of the Art都在这里了
机器之心
12+阅读 · 2018年12月10日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
相关基金
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Top
微信扫码咨询专知VIP会员