经典群集编辑问题（也称为相关群集）要求将给定图转换为少数边缘修改的群体（群集）的不相交联盟。当应用于顶点 - 彩色的图表（表示子组的颜色）时，NP-Hard群集编辑问题的标准算法可以产生偏向于数据的修改数量的数据（例如，人口组）的子组（例如，人口统计组）的子组的解决方案子组的成员。我们提出了一个修改公平限制，确保了对每个子组的编辑数量与其大小成正比。首先，我们研究具有两个顶点颜色的图形修改公平群集编辑。我们表明，即使只能在子组内插入边缘，问题也是np-solly;请注意，在经典的“非公平”设置中，这种情况是琐碎的多项式可解决。然而，在更通用的编辑形式中，修改公平的变体仍然是关于边缘编辑的数量的固定参数。我们补充了这些和进一步的理论结果，对我们在真实社交网络上的模型的实证分析，我们发现修改公平性的价格令人惊讶地低，即最佳修改公平的成本与最佳成本不同“非公平”解决方案只有小百分比。

We study the problem of graph clustering under a broad class of objectives in which the quality of a cluster is defined based on the ratio between the number of edges in the cluster, and the total weight of vertices in the cluster. We show that our definition is closely related to popular clustering measures, namely normalized associations, which is a dual of the normalized cut objective, and normalized modularity. We give a linear time constant-approximate algorithm for our objective, which implies the first constant-factor approximation algorithms for normalized modularity and normalized associations.

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

在聚类问题中，中央决策者通过顶点给出完整的公制图，并且必须提供最小化某些目标函数的顶点的聚类。在公平的聚类问题中，顶点以颜色（例如，组中的成员身份）赋予，并且有效群集的功能也可能包括该群集中的颜色的表示。在公平集群中的事先工作假设完全了解集团成员资格。在本文中，我们通过假设通过概率分配不完美了解集团成员资格的知识。我们在此具有近似率保证的更常规设置中呈现聚类算法。我们还解决了“公制成员资格”的问题，其中不同的群体的概念和距离。使用我们所提出的算法以及基线进行实验，以验证我们的方法，并且当组成员资格不确定时，验证我们的方法以及表面细微的问题。

了解训练具有整流线性单元（RELUS）的训练简单神经网络的计算复杂性最近是一项深入研究的主题。缩小差距和文献的补充结果，我们提供了有关训练两层relu网络的参数复杂性相对于各种损失函数的几个结果。经过对其他参数的简要讨论，我们着重分析培训数据对计算复杂性的尺寸$ d $的影响。我们根据w [1]的参数$ d $提供运行时间的下限，并证明已知的蛮力策略基本上是最佳的（假设指数时间假设）。与以前的工作相比，我们的结果适用于广泛（ER）范围的损失功能，包括[0，\ infty] $中的所有$ p \ for $ \ ell^p $ -loss。特别是，我们将已知的多项式时间算法扩展到常数$ d $，并将凸损失函数扩展到更一般的损耗函数，在这些情况下，我们的运行时间下限也匹配。

$ k $ -means和$ k $ -median集群是强大的无监督机器学习技术。但是，由于对所有功能的复杂依赖性，解释生成的群集分配是挑战性的。 Moshkovitz，Dasgupta，Rashtchian和Frost [ICML 2020]提出了一个优雅的可解释$ K $ -means和$ K $ -Median聚类型号。在此模型中，具有$ k $叶子的决策树提供了集群中的数据的直接表征。我们研究了关于可解释的聚类的两个自然算法问题。 （1）对于给定的群集，如何通过使用$ k $叶的决策树找到“最佳解释”？ （2）对于一套给定的点，如何找到一个以美元的决策树，最小化$ k $ -means / median目标的可解释的聚类？要解决第一个问题，我们介绍了一个新的可解释群集模型。我们的型号受到强大统计数据的异常值概念的启发，是以下情况。我们正在寻求少数积分（异常值），其删除使现有的聚类良好可解释。为了解决第二个问题，我们开始研究Moshkovitz等人的模型。从多元复杂性的角度来看。我们严格的算法分析揭示了参数的影响，如数据的输入大小，尺寸，异常值的数量，簇数，近似比，呈现可解释的聚类的计算复杂度。

因果鉴定是因果推理文献的核心，在该文献中提出了完整的算法来识别感兴趣的因果问题。这些算法的有效性取决于访问正确指定的因果结构的限制性假设。在这项工作中，我们研究了可获得因果结构概率模型的环境。具体而言，因果图中的边缘是分配的概率，例如，可能代表来自领域专家的信念程度。另外，关于边缘的不确定的可能反映了特定统计检验的置信度。在这种情况下自然出现的问题是：给定这样的概率图和感兴趣的特定因果效应，哪些具有最高合理性的子图是什么？我们表明回答这个问题减少了解决NP-HARD组合优化问题，我们称之为边缘ID问题。我们提出有效的算法来近似此问题，并评估我们针对现实世界网络和随机生成图的算法。

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

在本文中，我们提出了一个自然的单个偏好（IP）稳定性的概念，该概念要求每个数据点平均更接近其自身集群中的点，而不是其他群集中的点。我们的概念可以从几个角度的动机，包括游戏理论和算法公平。我们研究了与我们提出的概念有关的几个问题。我们首先表明，确定给定数据集通常允许进行IP稳定的聚类通常是NP-HARD。结果，我们探索了在某些受限度量空间中查找IP稳定聚类的有效算法的设计。我们提出了一种poly Time算法，以在实际线路上找到满足精确IP稳定性的聚类，并有效地算法来找到针对树度量的IP稳定2聚类。我们还考虑放松稳定性约束，即，与其他任何集群相比，每个数据点都不应太远。在这种情况下，我们提供具有不同保证的多时间算法。我们在实际数据集上评估了一些算法和几种标准聚类方法。

我们考虑经典的1中心问题：给定度量空间中的n个点P，找到p中的点，最小化到P的其他要点的最大距离。我们研究了D维$ \中这个问题的复杂性。 ell_p $ -metrics和编辑和ulam度量串的长度d。我们的1中心问题的结果可以根据D分类如下。 $ \ bullet $ small d：我们提供固定维度$ \ ell_1 $指标中的1中心问题的第一线性时间算法。另一方面，假设击中集猜测（HSC），我们显示，当$ d =ω（\ log n）$时，没有子种式算法可以在任何$ \ ell_p $ -metrics中解决1中心问题，或者在编辑或ulam指标中。 $ \ bullet $大d。当$ d =ω（n）$时，我们将条件下限扩展到编辑度量标准中的1中心问题的子四分之一算法（假设量化SETH）。另一方面，我们给出了一个$（1+ \ epsilon）$ - ulam度量标准中的1美元逼近，运行时间$ \ tilde {o _ {\ epsilon}}（nd + n ^ 2 \ sqrt {d}） $。我们还通过允许近似或通过减小维度D来加强一些上述下限，而是仅针对列出所有必要解决方案的较弱的算法类别。此外，我们扩展了我们的硬度结果，以便在编辑度量标准中排除次级学习的1中位问题的亚级算法，其中给出了一组长度n的n个字符串，目标是在集合中找到一个字符串这最小化了集合中的其余字符串的编辑距离之和。

图形上的分层聚类是数据挖掘和机器学习中的一项基本任务，并在系统发育学，社交网络分析和信息检索等领域中进行了应用。具体而言，我们考虑了由于Dasgupta引起的层次聚类的最近普及的目标函数。以前（大约）最小化此目标函数的算法需要线性时间/空间复杂性。在许多应用程序中，底层图的大小可能很大，即使使用线性时间/空间算法，也可以在计算上具有挑战性。结果，人们对设计只能使用sublinear资源执行全局计算的算法有浓厚的兴趣。这项工作的重点是在三个经过良好的sublinear计算模型下研究大量图的层次聚类，分别侧重于时空，时间和通信，作为要优化的主要资源：（1）（动态）流模型。边缘作为流，（2）查询模型表示，其中使用邻居和度查询查询图形，（3）MPC模型，其中图边缘通过通信通道连接的几台机器进行了分区。我们在上面的所有三个模型中设计用于层次聚类的sublinear算法。我们算法结果的核心是图表中的剪切方面的视图，这使我们能够使用宽松的剪刀示意图进行分层聚类，同时仅引入目标函数中的较小失真。然后，我们的主要算法贡献是如何在查询模型和MPC模型中有效地构建所需形式的切割稀疏器。我们通过建立几乎匹配的下限来补充我们的算法结果，该界限排除了在每个模型中设计更好的算法的可能性。

我们介绍了$（p，q）$ - 公平集群问题。在这个问题中，我们给出了一组点数$ p $和不同重量函数的集合$ w $。我们想找到一个群集，最小化$ \ ell_q $ -norm的$ \ ell_p $-norm的$ \ ell_p $ -norms的$ p $从中心。这概括了各种聚类问题，包括社会博览会$ k $ -Median和$ k $ - emeans，并且与其他问题紧密相连，如Densest $ K $ -subgraph和Min $ K $ -Union。我们利用凸编程技术来估计$（p，q）$ - 为$ p $和$ q $的不同价值观达到公平的聚类问题。当$ p \ geq q $时，我们得到$ o（k ^ {（pq）/（2pq）}）$，它几乎匹配$ k ^ {\ omega（（pq）/（pq））} $低于基于Min $ K $ -Union和其他问题的猜想硬度的束缚。当$ q \ geq p $时，我们得到一个近似，它与界限$ p，q $的输入的大小无关，也与最近的$ o相匹配（（\ log n /（\ log \ log n）） ^ {1 / p}）$ - $（p，\ infty）$ - makarychev和vakilian（colt 2021）的公平聚类。

Cohn and Umans proposed a framework for developing fast matrix multiplication algorithms based on the embedding computation in certain groups algebras. In subsequent work with Kleinberg and Szegedy, they connected this to the search for combinatorial objects called strong uniquely solvable puzzles (strong USPs). We begin a systematic computer-aided search for these objects. We develop and implement constraint-based algorithms build on reductions to $\mathrm{SAT}$ and $\mathrm{IP}$ to verify that puzzles are strong USPs, and to search for large strong USPs. We produce tight bounds on the maximum size of a strong USP for width $k \le 5$, construct puzzles of small width that are larger than previous work, and improve the upper bounds on strong USP size for $k \le 12$. Although our work only deals with puzzles of small-constant width, the strong USPs we find imply matrix multiplication algorithms that run in $O(n^\omega)$ time with exponent $\omega \le 2.66$. While our algorithms do not beat the fastest algorithms, our work provides evidence and, perhaps, a path to finding families of strong USPs that imply matrix multiplication algorithms that are more efficient than those currently known.

分层聚类研究将数据集的递归分区设置为连续较小尺寸的簇，并且是数据分析中的基本问题。在这项工作中，我们研究了Dasgupta引入的分层聚类的成本函数，并呈现了两个多项式时间近似算法：我们的第一个结果是高度电导率图的$ O（1）$ - 近似算法。我们简单的建筑绕过了在文献中已知的稀疏切割的复杂递归常规。我们的第二个和主要结果是一个US（1）$ - 用于展示群集明确结构的宽族图形的近似算法。该结果推出了以前的最先进的，该现有技术仅适用于从随机模型产生的图表。通过对合成和现实世界数据集的实证分析，我们所呈现的算法的实证分析表明了我们的工作的重要性，以其具有明确定义的集群结构的先前所提出的图表算法。

相关聚类是无监督的机器学习中无处不在的范式，在这种学习中解决不公平是一个主要的挑战。在此激励的情况下，我们研究了数据点可能属于不同保护组的公平相关聚类，目标是确保跨簇的所有组公平代表。我们的论文显着概括并改善了Ahmadi等人先前工作的质量保证。和Ahmadian等。如下。 - 我们允许用户指定群集中每个组表示的任意上限。 - 我们的算法允许个人具有多个受保护的功能，并确保所有这些特征同时公平。 - 我们证明，在这种一般环境中，可以保证质量和公平性。此外，这改善了先前工作中研究的特殊情况的结果。我们对现实世界数据的实验表明，与最佳解决方案相比，我们的聚类质量要比理论结果所建议的要好得多。

最近在组合问题中寻找多样化的解决方案，最近受到了相当大的关注（Baste等人2020; Fomin等人2020; Hanaka等。2021）。在本文中，我们研究了以下类型的问题：给出了整数$ k $，问题询问了$ k $解决方案，使得这些解决方案之间的成对和汉明距离的总和最大化。这种解决方案称为各种解决方案。我们介绍了一种用于查找加权定向图中的多样性最短$ ST $ -Paths的多项式时间算法。此外，我们研究了其他经典组合问题的多样化版本，如不同的加权麦芽碱，不同加权树丛和多样化的双链匹配。我们表明这些问题也可以在多项式时间内解决。为了评估我们寻找多样性最短$ ST $ ST -Paths的算法的实际表现，我们进行了合成和现实世界的计算实验。实验表明，我们的算法在合理的计算时间内成功计算了各种解决方案。

Pearl's Do Colculus是一种完整的公理方法，可以从观察数据中学习可识别的因果效应。如果无法识别这种效果，则有必要在系统中执行经常昂贵的干预措施以学习因果效应。在这项工作中，我们考虑了设计干预措施以最低成本来确定所需效果的问题。首先，我们证明了这个问题是NP-HARD，随后提出了一种可以找到最佳解或对数因子近似值的算法。这是通过在我们的问题和最小击球设置问题之间建立联系来完成的。此外，我们提出了几种多项式启发式算法来解决问题的计算复杂性。尽管这些算法可能会偶然发现亚最佳解决方案，但我们的模拟表明它们在随机图上产生了小的遗憾。

我们考虑测定点过程（DPP）的产物，该点过程，其概率质量与多矩阵的主要成本的产物成比例，作为DPP的天然有希望的推广。我们研究计算其归一化常量的计算复杂性，这是最重要的概率推理任务。我们的复杂性 - 理论结果（差不多）排除了该任务的有效算法的存在，除非输入矩阵被迫具有有利的结构。特别是，我们证明了以下内容：（1）计算$ \ sum_s \ det（{\ bf a} _ {s，s，s}）^ p $完全针对每个（固定）阳性甚至整数$ p $ up-hard和Mod $ _3 $ p-hard，它给Kulesza和Taskar提出的打开问题给出了否定答案。 （2）$ \ sum_s \ det（{\ bf a} _ {s，s}）\ det（{\ bf b} _ {s，s}）\ det（{\ bf c} _ {s，s} ）$ IS难以在2 ^ {o（| i | i | ^ {1- \ epsilon}）} $或$ 2 ^ {o（n ^ {1 / epsilon}）} $的任何一个$ \ epsilon> 0 $，其中$ | i | $是输入大小，$ n $是输入矩阵的顺序。这种结果比Gillenwater导出的两个矩阵的#P硬度强。 （3）有$ k ^ {o（k）} n ^ {o（1）} $ - 计算$ \ sum_s \ det的时间算法（{\ bf a} _ {s，s}）\ det（ {\ bf b} _ {s，s}）$，其中$ k $是$ \ bf a $和$ \ bf b $的最大等级，或者由$ \ bf a $的非零表项形成的图表的树宽和$ \ bf b $。据说这种参数化算法是固定参数的易解。这些结果可以扩展到固定尺寸的情况。此外，我们介绍了两个固定参数批量算法的应用程序给定矩阵$ \ bf a $ treewidth $ w $：（4）我们可以计算$ 2 ^ {\ frac {n} {2p-1} $ - 近似值到$ \ sum_s \ det（{\ bf a} _ {s，s}）^ p $ for任何分数$ p> 1 $以$ w ^ {o（wp）} n ^ {o（1）} $时间。 （5）我们可以在$ w ^ {o（w \ sqrt n）} n ^ {

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

相关聚类是基于成对相似性和不同分数的数据集的框架，并且已用于生物信息学，社交网络分析和计算机视觉中的不同应用。尽管已经为该问题设计了许多近似算法，但是最好的理论结果依赖于通过昂贵的线性编程松弛获得下限。在本文中，我们证明了与强三合会封闭原理相关的相关聚类问题与边缘标签问题的新关系。我们使用这些连接来开发新的近似算法，用于具有确定性恒因子近似保证并避免规范线性编程放松的相关聚类。我们的方法还扩展到称为集群删除的相关聚类的变体，严格禁止将负边缘放入簇中。我们的结果包括基于简化的线性程序的集群删除和相关聚类的4个近似算法，其限制的限制性远远超过规范放松。更重要的是，我们基于在某些辅助图和超图中的计算最大匹配基于计算最大匹配来发展纯组合的更快技术。这导致组合6 - 近似用于完整的未加权关联聚类，这是任何不依赖线性编程的方法的最佳确定性结果。我们还介绍了集群删除的第一个组合常数因子近似。