一个分布式算法用于解决大规模的p-中位数问题,使用预期最大化
Harsha Gwalani1, Joseph Helsing2, Sultanah M Alshammari3
1Department of Computer Science and Engineering, University of North Texas, Denton, Texas, United States.
我们开发了EM-FI,这是一个用于p-中位数问题的新型分布式算法. 它通过集群目的地有效地解决大规模的问题,在不牺牲解决方案质量的情况下提供显著的速度改进.
科学领域:
- 运营研究 运营研究
- 计算机科学 计算机科学
- 计算优化计算优化
背景情况:
- p-中位数问题旨在通过为n个目的地选择p个源来最大限度地减少平均距离.
- 这是一个NP难题,因为现有的启发式常常缺乏大数据集的可扩展性.
- 当前的快速交换 (FI) 启发式对大规模应用来说是时间效率低下的.
研究的目的:
- 引入一个可扩展和高效的算法来解决大规模的p-中位数问题.
- 在计算时间方面解决现有方法的局限性.
- 为了保持解决方案的质量,同时显著提高处理速度.
主要方法:
- 一个分布式的划分和统治方法,名为EM-FI.
- 使用预期最大化 (EM) 来识别目的地位置的空间集群.
- 同时使用整数编程或FI启发式解决聚类子问题.
主要成果:
- EM-FI 显示了计算时间的数量级改进.
- 算法保持了与最佳或接近最佳结果可比的解决方案质量.
- 在合成和现实世界数据集上都观察到有效的性能.
结论:
- 对于大规模的p-median问题,EM-FI提供了一个高效和可扩展的解决方案.
- 这种方法即使在有限的计算资源下也有效.
- 这种方法提升了解决复杂优化问题的实际可用性.
更多相关视频
09:47Author Spotlight: Advancing Alzheimer's Research – Exploring Early Detection and Multi-Omics Approaches
Published on: December 15, 2023
08:45Mapping Cortical Dynamics Using Simultaneous MEG/EEG and Anatomically-constrained Minimum-norm Estimates: an Auditory Attention Example
Published on: October 24, 2012
相关概念视频
Mechanistic Models: Compartment Models in Algorithms for Numerical Problem Solving
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
Median
Midrange
Simply put, the midrange is half of the data set’s range. Similar to the mean, the midrange is sensitive to the extreme values and hence the prospective outliers. However, unlike the mean, the midrange is not sensitive to all the values of the data set that lie in the middle. Thus, it is prone to...
Expected Value
Measures of Central Tendency
Estimating Population Mean with Unknown Standard Deviation
William S. Gosset (1876–1937) of the...
