This paper presents our solution for optimization task of the 3rd ACM-China IPCC. By the complexity analysis, we identified three time-consuming subroutines of original algorithm: marking edges, computing pseudo inverse and sorting edges. These subroutines becomes the main performance bottleneck owing to their super-linear time complexity. To address this, we proposed LGRASS, a linear graph spectral sparsification algorithm to run in strictly linear time. LGRASS takes advantage of spanning tree properties and efficient algorithms to optimize bottleneck subroutines. Furthermore, we crafted a parallel processing scheme for LGRASS to make full use of multi-processor hardware. Experiment shows that our proposed method fulfils the task in dozens of milliseconds on official test cases and keep its linearity as graph size scales up on random test cases.
翻译:本文介绍了我们为第三次ACM-中国气候专委会的优化任务提出的解决方案。 通过复杂分析,我们确定了原始算法的三个耗时的子程序:标记边缘、计算假反向和分类边缘。这些子程序因其超线性时间复杂性而成为主要的性能瓶颈。为了解决这个问题,我们建议使用LGRASS,即线性图光谱透析算法,在严格的线性时间运行。 LGRASS利用横跨树形特性和高效算法优化瓶颈子路程。此外,我们为LGRASS设计了一个平行的处理方案,以充分利用多处理器硬件。实验显示,我们所提议的方法在正式测试案例上以数十毫秒的速度完成了任务,并在随机测试案例上保持其线性作为图形大小缩略度。