多样性最大化是数据汇总，Web搜索和推荐系统中广泛应用的基本问题。给定$ n $元素的$ x $元素，它要求选择一个$ k \ ll n $元素的子集$ s $，具有最大\ emph {多样性}，这是由$ s $中元素之间的差异量化的。在本文中，我们关注流媒体环境中公平限制的多样性最大化问题。具体而言，我们考虑了最大值的多样性目标，该目标选择了一个子集$ s $，该子集$ s $最大化了其中任何一对不同元素之间的最小距离（不同）。假设集合$ x $通过某些敏感属性（例如性别或种族）将$ m $ discoint组分为$ m $ discoint组，确保\ emph {fairness}要求所选的子集$ s $包含每个组$ i的$ k_i $ e元素\在[1，m] $中。流算法应在一个通过中顺序处理$ x $，并返回具有最大\ emph {多样性}的子集，同时保证公平约束。尽管对多样性的最大化进行了广泛的研究，但唯一可以与最大值多样性目标和公平性约束的唯一已知算法对数据流非常低效。由于多样性最大化通常是NP-HARD，因此我们提出了两个在数据流中最大化的公平多样性的近似算法，其中第一个是$ \ frac {1- \ varepsilon} {4} {4} $ - 近似于$ m = 2 $，其中$ \ varepsilon \ in（0,1）$，第二个实现了$ \ frac {1- \ varepsilon} {3m+2} $ - 任意$ m $的近似值。现实世界和合成数据集的实验结果表明，两种算法都提供了与最新算法相当的质量解决方案，同时在流式设置中运行多个数量级。

我们重新审视了Chierichetti等人首先引入的公平聚类问题，该问题要求每个受保护的属性在每个集群中具有近似平等的表示。即，余额财产。现有的公平聚类解决方案要么是不可扩展的，要么无法在聚类目标和公平之间实现最佳权衡。在本文中，我们提出了一种新的公平概念，我们称之为$ tau $ $ $ - fair公平，严格概括了余额财产，并实现了良好的效率与公平折衷。此外，我们表明，简单的基于贪婪的圆形算法有效地实现了这一权衡。在更一般的多价受保护属性的设置下，我们严格地分析了算法的理论特性。我们的实验结果表明，所提出的解决方案的表现优于所有最新算法，即使对于大量簇，也可以很好地工作。

在机器学习中最大化的是一项基本任务，在本文中，我们研究了经典的Matroid约束下的删除功能强大版本。在这里，目标是提取数据集的小尺寸摘要，即使在对手删除了一些元素之后，该数据集包含高价值独立集。我们提出了恒定因素近似算法，其空间复杂性取决于矩阵的等级$ k $和已删除元素的数字$ d $。在集中式设置中，我们提出$（4.597+o（\ varepsilon））$ - 近似算法，带有摘要大小$ o（\ frac {k+d} {\ varepsilon^2} \ log \ log \ frac \ frac {k} }）$将$（3.582 + o（\ varepsilon））$（k + \ frac {d} {\ varepsilon^2} \ log \ frac {k} {k} {\ varepsilon}） $摘要大小是单调的。在流设置中，我们提供$（9.435 + o（\ varepsilon））$ - 带有摘要大小和内存$ o的近似算法$（k + \ frac {d} {\ varepsilon^2} \ log \ log \ frac {k} {k} {k} {k} {k} {k} { \ varepsilon}）$;然后，将近似因子提高到单调盒中的$（5.582+o（\ varepsilon））$。

我们研究动态算法，以便在$ N $插入和删除流中最大化单调子模块功能的问题。我们显示任何维护$（0.5+ epsilon）$ - 在基数约束下的近似解决方案的算法，对于任何常数$ \ epsilon> 0 $，必须具有$ \ mathit {polynomial} $的摊销查询复杂性$ n $。此外，需要线性摊销查询复杂性，以维持0.584美元 - 批量的解决方案。这与近期[LMNF + 20，MON20]的最近动态算法相比，达到$（0.5- \ epsilon）$ - 近似值，与$ \ mathsf {poly} \ log（n）$摊销查询复杂性。在正面，当流是仅插入的时候，我们在基数约束下的问题和近似的Matroid约束下提供有效的算法，近似保证$ 1-1 / e-\ epsilon $和摊销查询复杂性$ \ smash {o （\ log（k / \ epsilon）/ \ epsilon ^ 2）} $和$ \ smash {k ^ {\ tilde {o}（1 / \ epsilon ^ 2）} \ log n} $，其中$ k $表示基数参数或Matroid的等级。

Clustering is a fundamental problem in many areas, which aims to partition a given data set into groups based on some distance measure, such that the data points in the same group are similar while that in different groups are dissimilar. Due to its importance and NP-hardness, a lot of methods have been proposed, among which evolutionary algorithms are a class of popular ones. Evolutionary clustering has found many successful applications, but all the results are empirical, lacking theoretical support. This paper fills this gap by proving that the approximation performance of the GSEMO (a simple multi-objective evolutionary algorithm) for solving the three popular formulations of clustering, i.e., $k$-center, $k$-median and $k$-means, can be theoretically guaranteed. Furthermore, we prove that evolutionary clustering can have theoretical guarantees even when considering fairness, which tries to avoid algorithmic bias, and has recently been an important research topic in machine learning.

基于中心的聚类（例如，$ k $ -means，$ k $ -Medians）和使用线性子空间的聚类是两种最受欢迎的技术，可以将真实数据分配到较小的群集中。但是，当数据由敏感人群组组成时，不同敏感组的每点的聚集成本显着不同，可能会导致与公平相关的危害（例如，服务质量不同）。社会公平聚类的目的是最大程度地降低所有组中每点聚类的最大成本。在这项工作中，我们提出了一个统一的框架，以解决社会公平的基于中心的聚类和线性子空间聚类，并为这些问题提供实用，高效的近似算法。我们进行了广泛的实验，以表明在多个基准数据集上，我们的算法要么紧密匹配或超越最先进的基线。

我们研究社会上公平$（\ ell_p，k）$的近似算法 - $ m $组的聚类问题，其特殊案例包括社会公平的$ k $ -Median（$ p = 1 $）和社会公平的$ k $ - 均值（$ p = 2 $）问题。我们提出（1）一个多项式时间$（5+2 \ sqrt {6}）^p $ - approximation，最多$ k+m $中心（2）a $（5+2 \ sqrt {6}+\ \ \ \ \ \ \ \ \ \ \ \ \ \\ epsilon）^p $ - approximation with $ k $中心$ n^{2^{o（p）} \ cdot m^2} $，和（3）a $（15+6 \ sqrt {6}） ^p $ k $中心的时间$ k^{m} \ cdot \ text {poly}（n）$。第一个结果是通过使用一系列线性程序的迭代圆形方法的细化来获得的。后两个结果是通过将最多$ K+M $中心的解决方案转换为使用（2）的稀疏方法的$ K $中心的解决方案，并通过详尽的搜索（3）。我们还将算法的性能与现有的双色算法以及基准数据集中的$ K $中心近似算法的恰好比较，并发现我们的算法在实践中也优于现有方法。

单调可行的算法的开发，受基数约束（SMCC）的基本最大化产生了两个单独的研究方向：具有低自适应复杂性的集中算法，需要随机访问整个数据集；并分布式MAPREDUCE（MR）模型算法，这些算法使用少量的MR回合计算。目前，众所周知，没有MR Model算法使用均值的自适应回合，从而限制了其实际性能。我们在分布式设置中研究了SMCC问题，并介绍了三种单独的MR模型算法，这些算法在分布式设置中引入了sublinear适应性。我们的主要算法，Dash实现了$ \ frac {1} {2} {2}（1-1/e- \ varepsilon）$的近似值，而使用一个MR圆形，而其多轮变体元数据启用MR模型算法可以在大型上运行。以前不可能的基数约束。使用一个和$（$ \ frac {3} {8} {8} - \ varepsilon $）和（$ 1-1/e- \ varepsilon $）的两种附加算法T-DASH和G-DASH提供了改进的比率为（$ \ frac {3} {8} - \ varepsilon $） 1/\ Varepsilon）$ MR ROUNDS。我们所有提出的算法都具有肌关系的自适应复杂性，我们提供了广泛的经验证据来确定：仪表率是比最先进的分布式算法快的数量级，同时产生了几乎相同的溶液值；并验证仪表板在集中和分布式数据上获得可行解决方案时的多功能性。

指标$ k $-$ -center聚类是一个根本无人监督的学习原始。虽然广泛使用，但这种原语受到数据中噪声的严重影响，因此更明智的变体寻求最佳解决方案，这些解决方案忽略了数据集的给定数字$ Z $的Z $。我们为在滑动窗口设置下的流模型中提供有效的算法，在滑动窗口设置下，在每个时间步骤中，要群集的数据集是窗口$ W $的最新数据项。我们的算法达到$ O（1）$近似，显着要求在$ k + z $和logarithmic中以$ k + z $和logarithmic提供的工作内存线性。作为一个副产品，我们展示了如何估计窗口的有效直径$ W $，这是窗口点传播的衡量标准，忽略了给定的嘈杂距离的一部分。我们还提供了我们理论结果的实际可行性的实验证据。

在本文中，我们介绍了对非对称确定点处理（NDPP）的在线和流媒体地图推断和学习问题，其中数据点以任意顺序到达，并且算法被约束以使用单次通过数据以及子线性存储器。在线设置有额外要求在任何时间点维护有效的解决方案。为了解决这些新问题，我们提出了具有理论担保的算法，在几个真实的数据集中评估它们，并显示它们对最先进的离线算法提供了可比的性能，该算法将整个数据存储在内存中并采取多次传递超过它。

Evolutionary algorithms (EAs) are a kind of nature-inspired general-purpose optimization algorithm, and have shown empirically good performance in solving various real-word optimization problems. During the past two decades, promising results on the running time analysis (one essential theoretical aspect) of EAs have been obtained, while most of them focused on isolated combinatorial optimization problems, which do not reflect the general-purpose nature of EAs. To provide a general theoretical explanation of the behavior of EAs, it is desirable to study their performance on general classes of combinatorial optimization problems. To the best of our knowledge, the only result towards this direction is the provably good approximation guarantees of EAs for the problem class of maximizing monotone submodular functions with matroid constraints. The aim of this work is to contribute to this line of research. Considering that many combinatorial optimization problems involve non-monotone or non-submodular objective functions, we study the general problem classes, maximizing submodular functions with/without a size constraint and maximizing monotone approximately submodular functions with a size constraint. We prove that a simple multi-objective EA called GSEMO-C can generally achieve good approximation guarantees in polynomial expected running time.

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

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

随着机器学习变得普遍，减轻培训数据中存在的任何不公平性变得至关重要。在公平的各种概念中，本文的重点是众所周知的个人公平，该公平规定应该对类似的人进行类似的对待。虽然在训练模型（对处理）时可以提高个人公平性，但我们认为在模型培训（预处理）之前修复数据是一个更基本的解决方案。特别是，我们表明标签翻转是改善个人公平性的有效预处理技术。我们的系统IFLIPPER解决了限制了个人公平性违规行为的最小翻转标签的优化问题，当培训数据中的两个类似示例具有不同的标签时，发生违规情况。我们首先证明问题是NP-HARD。然后，我们提出了一种近似的线性编程算法，并提供理论保证其结果与标签翻转数量有关的结果与最佳解决方案有多近。我们还提出了使线性编程解决方案更加最佳的技术，而不会超过违规限制。实际数据集上的实验表明，在看不见的测试集的个人公平和准确性方面，IFLIPPER显着优于其他预处理基线。此外，IFLIPPER可以与处理中的技术结合使用，以获得更好的结果。

在本文中，我们研究了经典的少量最大化问题，但在非自适应和适应性环境下都受到群体公平限制。已经表明，许多机器学习应用程序的效用函数，包括数据汇总，影响社交网络中的最大化和个性化建议，都满足了子义的属性。因此，在许多应用程序的核心中可以找到受到各种限制的最大化函数。在高水平上，少量最大化旨在选择一组大多数代表性项目（例如，数据点）。但是，大多数现有算法的设计并未包含公平的约束，从而导致某些特定组的不足或过分代表。这激发了我们研究公平的supsodular最大化问题，我们旨在选择一组项目，以最大化（可能是非单调的）suppodular效用功能，但要受群体公平约束。为此，我们为此问题开发了第一个常数因子近似算法。我们的算法的设计足够强大，可以扩展到更复杂的自适应设置下解决suppodular的最大化问题。此外，我们将研究进一步扩展到整合全球基础性约束。

本文展示了如何适应$ k $ -MEANS问题的几种简单和经典的基于采样的算法，以使用离群值设置。最近，Bhaskara等人。 （Neurips 2019）展示了如何将古典$ K $ -MEANS ++算法适应与异常值的设置。但是，他们的算法需要输出$ o（\ log（k）\ cdot z）$ outiers，其中$ z $是true Outliers的数量，以匹配$ o（\ log k）$ - 近似值的$ k的近似保证$ -Means ++。在本文中，我们以他们的想法为基础，并展示了如何适应几个顺序和分布式的$ k $ - 均值算法，但使用离群值来设置，但具有更强的理论保证：我们的算法输出$（1+ \ VAREPSILON）z $ OUTLIERS Z $ OUTLIERS在实现$ o（1 / \ varepsilon）$ - 近似目标函数的同时。在顺序世界中，我们通过改编Lattanzi和Sohler的最新算法来实现这一目标（ICML 2019）。在分布式设置中，我们适应了Guha等人的简单算法。 （IEEE Trans。知道和数据工程2003）以及Bahmani等人的流行$ K $ -Means $ \ | $。 （PVLDB 2012）。我们技术的理论应用是一种具有运行时间$ \ tilde {o}（nk^2/z）$的算法，假设$ k \ ll z \ ll n $。这与Omacle模型中此问题的$ \ Omega（NK^2/z）$的匹配下限相互补。

Multi-label classification is becoming increasingly ubiquitous, but not much attention has been paid to interpretability. In this paper, we develop a multi-label classifier that can be represented as a concise set of simple "if-then" rules, and thus, it offers better interpretability compared to black-box models. Notably, our method is able to find a small set of relevant patterns that lead to accurate multi-label classification, while existing rule-based classifiers are myopic and wasteful in searching rules,requiring a large number of rules to achieve high accuracy. In particular, we formulate the problem of choosing multi-label rules to maximize a target function, which considers not only discrimination ability with respect to labels, but also diversity. Accounting for diversity helps to avoid redundancy, and thus, to control the number of rules in the solution set. To tackle the said maximization problem we propose a 2-approximation algorithm, which relies on a novel technique to sample high-quality rules. In addition to our theoretical analysis, we provide a thorough experimental evaluation, which indicates that our approach offers a trade-off between predictive performance and interpretability that is unmatched in previous work.

对于最大化单调的问题，子模块功能相对于基数限制为$ K $ k $ k $ k $ $ n $ n $，我们提供了一种在其经验性能和其上实现最先进的算法理论属性，就适应性复杂性，查询复杂性和近似率而言;也就是说，它获得了高概率，查询复杂度$ O（n）$的期望，适应$ o（\ log（n））$，近似1-1 / e $的近似比。主要算法由可能是独立兴趣的两个组件组装。我们的算法的第一个组件LineArseq，可用作提高许多算法的查询复杂性的预处理算法。此外，LineArseq的变体显示为具有O $ O（n / k））$的自适应复杂性，其小于文献中的任何先前算法的自适应复杂性。第二组件是一个并行阈值处理过程阈值问题，用于添加具有高于恒定阈值的增益的元素。最后，我们展示了我们的主要算法在运行时，自适应轮次，总查询和客观值方面经验胜过，以前的最先进的算法，以六个子模块物理函数快速评估。

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

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.