当考虑$ N $标记的机器人的运动计划时，我们需要通过一系列平行，连续的，无碰撞的机器人运动来重新布置给定的启动配置为所需的目标配置。目的是在最短的时间内达到新配置；一个重要的约束是始终保持群体连接。以前已经考虑过这种类型的问题，最近值得注意的结果可实现不一定连接的重新配置：如果将起始配置映射到目标配置，则需要最大的曼哈顿距离$ D $，则总体时间表的总持续时间可以是限制为$ \ Mathcal {O}（d）$，这是最佳选择的恒定因素。但是，只有在允许断开连接的重新配置或用于缩放的配置（通过将给定对象的所有维度通过相同的乘法因子增加到相同的乘法因子增加）时，才能实现恒定拉伸。我们通过（1）建立$ \ omega（\ sqrt {n}）$的下限来解决这些主要的开放问题可以实现重新配置。此外，我们表明（3）决定是否可以实现2个制造物，而可以检查多项式时间是否可以实现1个制造pan。

两种尺寸的模块化机器人的良好理论模型是边缘连接的方形模块配置，可以通过所谓的滑动移动重新配置。 Dumitrescu和Pach [图形和Combinatorics，2006]证明，始终可以将N $ Squares的一个边缘连接配置重新配置为任何其他使用$ O（n ^ 2）$滑动移动，同时保持配置连接每时每刻。对于某些配置，重新配置可能需要$ \ omega（n ^ 2）$滑动移动。然而，可能就足够较少。我们证明它是难以最小化给定对边缘连接配置的滑动移动的数量。在正面，我们呈现收集和紧凑，一个输入敏感的就地算法只需要$ O（\ bar {p} n）$ slide移动，将一个配置转换为另一个配置，其中$ \ bar {p} $两个边界框的最大周边。正方形仅在边界盒内移动，除了可以通过与边界框相邻的位置移动的时间最多的一个正方形。 $ O（\ bar {p} n）$绑定永远不会超过$ o（n ^ 2）$，并且在只需$ n $和$ \ bar {p} $ 。我们的算法建立在基本原理上，可以有效地转换模块化机器人的良好连接的组件。因此，我们迭代地提高配置内的连接，最终到达一个固体$ xy $-monotone组件。我们实施了聚集＆紧凑，并通过实验进行了比较了Moreno和Searist的原始修改，Dumitrescu和PACH算法（MSDP）的[Eurocg 2020]。我们的实验表明，在所有类型的方形配置上，聚集和紧凑始终如一地优于MSDP。

重新配置图中的两个最短路径意味着通过一次改变一个顶点来修改一个最短的路径，使得所有中间路径也是最短路径。这个问题有几个自然应用，即：（a）改造道路网络，（b）在同步多处理设置中重新排出数据包，（c）运输集装箱存货问题，以及（d）列车编组问题。在作为图形问题的建模时，（a）是最常规的情况而（b），（c）和（d）是对不同图形类的限制。我们表明（a）是棘手的，即使对于问题的轻松变体也是如此。对于（b），（c）和（d），我们提出了有效的算法来解决各自的问题。我们还将问题概括为当最多$ k $（对于固定整数$ k \ geq k \ ge $ k \ geq 2 $）一次连续的顶点一次可以一次更改。

近年来，在平衡（超级）图分配算法的设计和评估中取得了重大进展。我们调查了过去十年的实用算法的趋势，用于平衡（超级）图形分区以及未来的研究方向。我们的工作是对先前有关该主题的调查的更新。特别是，该调查还通过涵盖了超图形分区和流算法来扩展先前的调查，并额外关注并行算法。

结构分解方法，例如普遍的高树木分解，已成功用于解决约束满意度问题（CSP）。由于可以重复使用分解以求解具有相同约束范围的CSP，因此即使计算本身很难，将资源投资于计算良好的分解是有益的。不幸的是，即使示波器仅略有变化，当前方法也需要计算全新的分解。在本文中，我们迈出了解决CSP $ P $分解的问题的第一步，以使其成为由$ P $修改产生的新CSP $ P'$的有效分解。即使从理论上讲问题很难，我们还是提出并实施了一个有效更新GHD的框架。我们算法的实验评估强烈提出了实际适用性。

本文研究了人工神经网络（NNS）与整流线性单元的表现力。为了将它们作为实际计算的模型，我们介绍了最大仿射算术计划的概念，并显示了它们与NNS之间的等效性有关自然复杂度措施。然后我们使用此结果表明，使用多项式NNS可以解决两个基本组合优化问题，这相当于非常特殊的强多项式时间算法。首先，我们显示，对于带有N $节点的任何无向图形，有一个NN大小$ \ Mathcal {O}（n ^ 3）$，它将边缘权重用为输入，计算最小生成树的值图表。其次，我们显示，对于任何带有$ N $节点和$ M $弧的任何定向图，都有一个尺寸$ \ mathcal {o}（m ^ 2n ^ 2）$，它将电弧容量作为输入和计算最大流量。这些结果尤其尤其暗示，相应的参数优化问题的解决方案可以在多项式空间中编码所有边缘权重或电弧容量的方法，并在多项式时间中进行评估，并且由NN提供这种编码。

Amoebot模型将主动的可编程物质抽象为简单的计算元素的集合，称为Amoebot，它们在本地交互以集体完成协调和运动任务。自2014年SPAA推出以来，越来越多的文献已经改编了其对各种问题的假设。但是，如果没有标准化的假设层次结构，则很难对Amoebot模型下的结果进行精确的系统比较。我们提出了规范的Amoebot模型，该模型是一个更新的形式化，可区分核心模型特征和假设变体系列。规范Amoebot模型解决的关键改进是并发。现有的许多文献隐含地假设Amoebot动作是孤立且可靠的，将分析降低到一个顺序设置，其中最多一次是Amoebot活跃的。但是，实际可编程系统是并发的。 Canonical Amoebot模型将所有Amoebot通信形式化为消息传递，利用并发执行的对抗激活模型。在这种颗粒状的时间处理下，我们采用两种互补方法来并发算法设计。我们首先在任何并发执行下建立一组足够的条件，以实现算法正确性，将并发控制直接嵌入算法设计中。然后，我们提出了一个并发控制框架，该框架使用锁来转换在顺序设置中终止的Amoebot算法，并满足某些约定在并发设置中表现出等效行为的算法中的某些约定。作为案例研究，我们使用简单的六边形形成算法证明了这两种方法。共同的Amoebot模型以及这些并发算法设计的互补方法设计开放的新方向，用于分布式计算可编程问题。

Graph clustering is a fundamental problem in unsupervised learning, with numerous applications in computer science and in analysing real-world data. In many real-world applications, we find that the clusters have a significant high-level structure. This is often overlooked in the design and analysis of graph clustering algorithms which make strong simplifying assumptions about the structure of the graph. This thesis addresses the natural question of whether the structure of clusters can be learned efficiently and describes four new algorithmic results for learning such structure in graphs and hypergraphs. All of the presented theoretical results are extensively evaluated on both synthetic and real-word datasets of different domains, including image classification and segmentation, migration networks, co-authorship networks, and natural language processing. These experimental results demonstrate that the newly developed algorithms are practical, effective, and immediately applicable for learning the structure of clusters in real-world data.

Despite recent progress on trajectory planning of multiple robots and path planning of a single tethered robot, planning of multiple tethered robots to reach their individual targets without entanglements remains a challenging problem. In this paper, we present a complete approach to address this problem. Firstly, we propose a multi-robot tether-aware representation of homotopy, using which we can efficiently evaluate the feasibility and safety of a potential path in terms of (1) the cable length required to reach a target following the path, and (2) the risk of entanglements with the cables of other robots. Then, the proposed representation is applied in a decentralized and online planning framework that includes a graph-based kinodynamic trajectory finder and an optimization-based trajectory refinement, to generate entanglement-free, collision-free and dynamically feasible trajectories. The efficiency of the proposed homotopy representation is compared against existing single and multiple tethered robot planning approaches. Simulations with up to 8 UAVs show the effectiveness of the approach in entanglement prevention and its real-time capabilities. Flight experiments using 3 tethered UAVs verify the practicality of the presented approach.

可以部署一组合作的空中机器人，以有效地巡逻地形，每个机器人都会在指定区域飞行，并定期与邻居共享信息，以保护或监督它。为了确保鲁棒性，以前对这些同步系统的作品提出了将机器人发送到相邻区域的情况，以防它检测到故障。为了处理不可预测性并提高确定性巡逻计划的效率，本文提出了随机策略，以涵盖在代理之间分配的领域。首先，在本文中针对两个指标进行了对随机过程的理论研究：\ emph {闲置时间}，这是两个连续观察到地形的任何点和\ emph {隔离时间}之间的预期时间，预期的时间}，预期的时间机器人没有与任何其他机器人通信的时间。之后，将随机策略与添加另一个指标的确定性策略进行了比较：\ emph {广播时间}，从机器人发出消息的那一刻，直到团队的所有其他机器人收到消息。模拟表明，理论结果与模拟和随机策略的表现非常吻合，其行为与文献中提出的确定性协议获得的行为相比。

In the Priority $k$-Center problem, the input consists of a metric space $(X,d)$, an integer $k$, and for each point $v \in X$ a priority radius $r(v)$. The goal is to choose $k$-centers $S \subseteq X$ to minimize $\max_{v \in X} \frac{1}{r(v)} d(v,S)$. If all $r(v)$'s are uniform, one obtains the $k$-Center problem. Plesn\'ik [Plesn\'ik, Disc. Appl. Math. 1987] introduced the Priority $k$-Center problem and gave a $2$-approximation algorithm matching the best possible algorithm for $k$-Center. We show how the problem is related to two different notions of fair clustering [Harris et al., NeurIPS 2018; Jung et al., FORC 2020]. Motivated by these developments we revisit the problem and, in our main technical contribution, develop a framework that yields constant factor approximation algorithms for Priority $k$-Center with outliers. Our framework extends to generalizations of Priority $k$-Center to matroid and knapsack constraints, and as a corollary, also yields algorithms with fairness guarantees in the lottery model of Harris et al [Harris et al, JMLR 2019].

我们根据计算一个扎根于每个顶点的某个加权树的家族而构成的相似性得分提出了一种有效的图形匹配算法。对于两个erd \ h {o} s-r \'enyi图$ \ mathcal {g}（n，q）$，其边缘通过潜在顶点通信相关联，我们表明该算法正确地匹配了所有范围的范围，除了所有的vertices分数外，有了很高的概率，前提是$ nq \ to \ infty $，而边缘相关系数$ \ rho $满足$ \ rho^2> \ alpha \ ailpha \大约0.338 $，其中$ \ alpha $是Otter的树木计数常数。此外，在理论上是必需的额外条件下，可以精确地匹配。这是第一个以显式常数相关性成功的多项式图匹配算法，并适用于稀疏和密集图。相比之下，以前的方法要么需要$ \ rho = 1-o（1）$，要么仅限于稀疏图。该算法的症结是一个经过精心策划的植根树的家族，称为吊灯，它可以有效地从同一树的计数中提取图形相关性，同时抑制不同树木之间的不良相关性。

K-MEDIAN和K-MEACE是聚类算法的两个最受欢迎的目标。尽管有密集的努力，但对这些目标的近似性很好地了解，特别是在$ \ ell_p $ -metrics中，仍然是一个重大的开放问题。在本文中，我们在$ \ ell_p $ -metrics中显着提高了文献中已知的近似因素的硬度。我们介绍了一个名为Johnson覆盖假说（JCH）的新假设，这大致断言设定系统上的良好的Max K-Coverage问题难以近似于1-1 / e，即使是成员图形设置系统是Johnson图的子图。然后，我们展示了Cohen-Addad和Karthik引入的嵌入技术的概括（Focs'19），JCH意味着K-MEDIAN和K-MERION在$ \ ell_p $ -metrics中的近似结果的近似值的硬度为近距离对于一般指标获得的人。特别地，假设JCH我们表明很难近似K-Meator目标：$ \ Bullet $离散情况：$ \ ell_1 $ 3.94 - $ \ ell_2中的1.73因素为1.73倍$$ - 这分别在UGC下获得了1.56和1.17的先前因子。 $ \ bullet $持续案例：$ \ ell_1 $ 2210 - $ \ ell_2 $的$ \ ell_1 $ 210。$ \ ell_2 $-metric;这在UGC下获得的$ \ ell_2 $的$ \ ell_2 $的先前因子提高了1.07。对于K-Median目标，我们还获得了类似的改进。此外，我们使用Dinure等人的工作证明了JCH的弱版本。 （Sicomp'05）在超图顶点封面上，恢复Cohen-Addad和Karthik（Focs'19 Focs'19）上面的所有结果（近）相同的不可识别因素，但现在在标准的NP $ \ NEQ $ P假设下（代替UGC）。

In this paper, we consider the multi-robot path execution problem where a group of robots move on predefined paths from their initial to target positions while avoiding collisions and deadlocks in the face of asynchrony. We first show that this problem can be reformulated as a distributed resource allocation problem and, in particular, as an instance of the well-known Drinking Philosophers Problem (DrPP). By careful construction of the drinking sessions capturing shared resources, we show that any existing solutions to DrPP can be used to design robot control policies that are collectively collision and deadlock-free. We then propose modifications to an existing DrPP algorithm to allow more concurrent behavior, and provide conditions under which our method is deadlock-free. Our method does not require robots to know or to estimate the speed profiles of other robots and results in distributed control policies. We demonstrate the efficacy of our method on simulation examples, which show competitive performance against the state-of-the-art.

我们检查机器学习中出现的组合概念与立方/单纯几何形状中的拓扑概念之间的连接。这些连接使得从几何形状导出到机器学习的结果。我们的第一个主要结果是基于Tracy Hall（2004）的几何结构，其局部炮击的交叉多容院不能延伸。我们使用它来得出最大类别的VC尺寸3，没有角落。从过去11年来，这反驳了在机器学习中的几个工作。特别地，它意味着最佳类别的最佳未标记的样本压缩方案的所有先前结构都是错误的。在积极的一面，我们为最大类提供了一个未标记的样品压缩方案的新建。我们打开我们的未标记的样品压缩方案是否延伸到充足（A.K.A.不平衡或极值）课程，这代表了最大类的自然和深远的概括。在解决这个问题方面，我们就关联立方体复合物的1骷髅的独特宿前方向提供了几何特征。

这项工作提出了一个新的路径分类标准，以几何和拓扑区分路径与工作空间区分路径，该路径通过细胞分解分开，生成内侧轴状的骨骼结构。我们使用此信息以及机器人的拓扑来绑定和对配置空间中的不同路径进行分类。我们表明，所提出的方法找到的路径类等于和比路径同遵循的路径类更细。拟议的路径类易于计算，比较，并且可用于各种计划目的。该分类在机器人的拓扑结构和工作空间的几何形状上大大建立，从而导致了对配置空间的替代基于纤维束的描述。我们介绍了一个计划框架，以使用建议的路径分类方法和所得路径类克服障碍和狭窄的段落。

Motivated by alignment of correlated sparse random graphs, we introduce a hypothesis testing problem of deciding whether or not two random trees are correlated. We obtain sufficient conditions under which this testing is impossible or feasible. We propose MPAlign, a message-passing algorithm for graph alignment inspired by the tree correlation detection problem. We prove MPAlign to succeed in polynomial time at partial alignment whenever tree detection is feasible. As a result our analysis of tree detection reveals new ranges of parameters for which partial alignment of sparse random graphs is feasible in polynomial time. We then conjecture that graph alignment is not feasible in polynomial time when the associated tree detection problem is impossible. If true, this conjecture together with our sufficient conditions on tree detection impossibility would imply the existence of a hard phase for graph alignment, i.e. a parameter range where alignment cannot be done in polynomial time even though it is known to be feasible in non-polynomial time.

The stochastic block model (SBM) is a random graph model with planted clusters. It is widely employed as a canonical model to study clustering and community detection, and provides generally a fertile ground to study the statistical and computational tradeoffs that arise in network and data sciences.This note surveys the recent developments that establish the fundamental limits for community detection in the SBM, both with respect to information-theoretic and computational thresholds, and for various recovery requirements such as exact, partial and weak recovery (a.k.a., detection). The main results discussed are the phase transitions for exact recovery at the Chernoff-Hellinger threshold, the phase transition for weak recovery at the Kesten-Stigum threshold, the optimal distortion-SNR tradeoff for partial recovery, the learning of the SBM parameters and the gap between information-theoretic and computational thresholds.The note also covers some of the algorithms developed in the quest of achieving the limits, in particular two-round algorithms via graph-splitting, semi-definite programming, linearized belief propagation, classical and nonbacktracking spectral methods. A few open problems are also discussed.

我们考虑从数据学习树结构ising模型的问题，使得使用模型计算的后续预测是准确的。具体而言，我们的目标是学习一个模型，使得小组变量$ S $的后海报$ p（x_i | x_s）$。自推出超过50年以来，有效计算最大似然树的Chow-Liu算法一直是学习树结构图形模型的基准算法。 [BK19]示出了关于以预测的局部总变化损耗的CHOW-LIU算法的样本复杂性的界限。虽然这些结果表明，即使在恢复真正的基础图中也可以学习有用的模型是不可能的，它们的绑定取决于相互作用的最大强度，因此不会达到信息理论的最佳选择。在本文中，我们介绍了一种新的算法，仔细结合了Chow-Liu算法的元素，以便在预测的损失下有效地和最佳地学习树ising模型。我们的算法对模型拼写和对抗损坏具有鲁棒性。相比之下，我们表明庆祝的Chow-Liu算法可以任意次优。

为了在标记的设置下实现高效，大规模的无人驾驶汽车（UAV）的协调，在这项工作中，我们开发了第一种多项式时间算法，用于在三维空间中重新配置许多移动物体，并提供可证明的$ 1.x $在高机器人密度下，渐近制造pan最佳保证。更准确地说，在$ m_1 \ times m_2 \ times m_3 $ grid，$ m_1 \ ge m_2 \ ge m_3 $，我们的方法计算解决方案最多可将$ \ frac {m_1m_2m_3} {3} {3} {3} $唯一的随机机器人分布式开始和目标配置在$ M_1 +2M_2 +2M_3 +O（M_1）$的MakePAN中，概率很高。因为此类实例的makepan下限为$ m_1+m_2+m_3 -o（m_1）$，也有很高的可能性，如$ m_1 \ to \ infty $，$ \ frac {m_1+2m_2+2m_2+2m_3} {m_1+m_1+m_1+m_2+m_2 +M_3} $最佳保证。 $ \ frac {m_1+2m_2+2m_3} {m_1+m_2+m_3} \ in（1，\ frac {5} {3}] $，产生$ 1.x $ optimality。相比 - 机动体路径计划是最佳解决的NP。在数值评估中，我们的方法很容易缩放以支持超过100,000美元的3D机器人的运动计划，同时达到$ 1.x $ optimality。我们证明了我们的方法在协调方面的应用许多四肢中的二重奏和硬件实验。