- 自适应次模覆盖问题的贪婪近似比的下界
贪婪算法的自适应子模块覆盖近似比率至少为 1.3 *(1 + ln Q),这篇论文否定了 Golovin-Krause 在 `` 自适应子模块性:主动学习和随机优化的新方法 '' 中宣称相同算法具有(1 + ln Q)^2 近似比率的先前结 - 一维投影聚类的简单、可扩展和有效方法
非监督学习中的聚类是一个基础问题,本研究介绍了一种简单的随机聚类算法,它在任意 k 下的期望运行时间为 O (nnz (X) + nlogn),并在 K-means 目标函数上实现了近似比例约为 O (k^4) 的算法,通过实验证明与现有方 - 多项式对数轮次内求解相关聚类问题的三因素近似算法失效
本文研究了用于相关聚类问题的并行算法,其中每个不同实体的每对实体都标记为相似或不相似,旨在将实体分成簇以最小化与标签的不一致性,提出了首个多项式对数深度并行算法,并使用比 3 更好的逼近比计算 (2.4 +ϵ) 逼近解,可以将其转换为 (m - 超模秩:集函数分解与优化
介绍了一个新的概念:在格子上定义函数的超模秩,是把函数分解为超模函数之和所需的最小项数;并且通过对不同偏序关系下定义超模和的方式,描述了具有固定超模秩的函数,以及类似地定义亚模秩;使用亚模分解来优化集合函数用于解决单调集合函数最大化和集合函 - 可扩展和有效的基于传导度的图聚类
本文提出了一个基于 peeling 的图聚类框架 PCon ,并使用该框架提出了两个线性时间和空间复杂度的算法 PCon_core 和 PCon_de ,可以在处理十亿级别的图数据时实现高准确度的聚类效果,而且 PCon_de 的近似度理论 - 具有入场费的设施位置
该论文研究了设施位置博弈中的一种新模型,其中每个代理商的成本由到设施的距离和设施的进入费用组成,介绍了一些新的战略,讨论了利益共享和平等的问题以及可重塑的近似比率。
- 超越最坏情况的调度机制
该论文探讨了两种调度机制(K 和 P 机制)的性能,证明了 K 机制是优于 P 机制的,并在特定条件下给出了它们的平均近似比例收敛值。
- AAAI有效局部搜索增强平衡图边划分
本文研究了图分区中的边划分问题,提出了可调节的边和块的两个新概念,基于此发展了一种贪心启发式和一个利用最大流模型的改进搜索算法,可以大幅度提高图分区的质量和近似比。
- 子模量极大化的 FAST 算法
本篇论文介绍了一种新算法 FAST,旨在通过最大化满足劣模性的子模函数,使逼近比例任意接近 1-1 /e,由 O (log(n)log^2 (log k)) 次适应,总共使用 O(nloglog (k)) 次查询,在处理大数据集方面,该算法 - Ward 方法分析
本文研究了 Ward 方法在分层 k 均值问题中的应用,通过对完全链接的算法进行分析,发现当最优 k 聚类具有良好分离性时,Ward 方法可以计算出 k - 均值目标函数的 2 - 近似解,并证明了当最优聚类满足平衡条件时,Ward 方法完 - 超越基数约束的弱次模最大化:贪心法是否受益于随机化?
本文提出了一种随机贪心算法来最大化弱次模函数在一般拟阵约束下的值,其中距离次模性的距离由参数 γ 衡量,该算法在实践中表现良好,并且是第一个能够约束弱次模函数最大化具有非平凡逼近保证的算法。
- 公民选举:代表性候选人更有效
本文考虑选举中的社会福利和代表性候选人对社会福利的影响,采用度量优先模型来探索社会最佳的程度和度量空间的复杂性对其影响,得到了多个近似比例的下限和上限。
- 在背包约束下最大化有界曲率的单调次模函数
提出一种用于最大化满足背包限制下单调子模函数的算法,并且该算法的多项式时间复杂度为一个取决于输入函数曲率 c 的比率,该算法的近似度为 1-c/e-ε,这一近似度对于任何处于区间 [0,1] 中的 c 值均是紧确的。此外,该研究提供了用于预 - 度量空间中有界倍增维度的多样性最大化的 MapReduce 和 Streaming 算法
该论文在关于点集的度量空间问题中,提出了一种基于流算法和 MapReduce 模型的高效多样性最大化算法,该算法通过核心集合和 α- 近似比的计算,能够在处理大量数据集时获得优秀的近似度。
- 局部搜索在双倍指标下为 k-Means 提供 PTAS
使用局部搜索启发式策略,本文证明了在任何固定维度的欧几里得空间中,k-means 问题均可提供 PTAS。
- 一种基于相似性层次聚类的代价函数
本文介绍了一种适用于一组点之间的层次结构的简单代价函数,该函数基于这些点之间的相似性,克服了现有算法由于缺乏精确客观函数而退化的问题。作者进一步证实该方法在经典实例中表现出良好的性能,并提出了一种上行建设程序,其近似比可以证明是好的。
- k-Median 问题的改进近似算法,以及预算优化中的正相关性
介绍了一个算法,它在依赖取整方案中保证依赖取整的已知特性,对于变量的 "小" 子集具有近似最优的行为,同时显式地处理正相关性,并将李和斯文森在经典 k - 中位数问题的近似比从 2.732+ϵ 改进到 2.675 + ϵ,时间复杂度从 N^ - 具有尖锐保证的凸规划的随机草图
该研究探讨了使用随机投影进行维度降低的方法来近似解决具有凸性质的问题,在计算有限的情况下具有广泛的应用,同时还可以提高隐私保护和降低存储和计算成本。研究证明了该方法的近似比率可以用约束集合的几何特性来界定,对于一类广泛的随机投影,其投影结果 - 模模块极值相遇流式计算:匹配,拟阵等
本文研究了最大子模函数匹配问题,给出了两种空间复杂度均为 O (nlogn) 的半流算法,并探讨了最大加权匹配和多重矩阵交叉的相似性,以求得更普适的解决方案。
- 区间投票的真实近似
研究机制设计的基本问题,即在无货币的情况下,考虑有限数量的备选方案和一般记数偏好下的近似社会福利最大化问题,并提出一种随机的期望真实序数机制来实现其预期社会福利至少是社会最优方案社会福利的 1/m^(3/4)。此外,对于足够多的代理和任何期