On Construction and Evaluation of Parallel and Randomized Algorithms for Network Optimization Problems

在过去的两年中，我们一直试图构建新的并行，随机算法的网络优化问题，特别是最小割问题。近年来，求解最小割问题的并行随机算法的研究取得了很大进展。在这个研究项目中，我们专注于开发简单有效的算法，适用于更广泛的问题，包括最小割问题。此外，我们还研究了最小k-聚类问题，并在最小方差准则下得到了新的理论结果。在本项目中，我们首次提出了一个O（m+nlogn）时间的最小范围割问题算法（n和m是图中节点和顶点的数目）。最小范围切割问题要求在加权无向图中找到一个切割，使切割中最大和最小边权重之间的差异最小化。在此算法的基础上，我们提出了一种求解最小割问题的并行随机算法。然后，我们进行了广泛的计算机实验，以证明我们的近似算法的有效性。因此，我们可以证明，我们的算法计算切割是非常接近的时间比现有的精确算法快得多。最小k-聚类问题要求基于一定的最优性准则找到R^d中给定的n个点的k-划分.在我们的研究中，专注于计算机图形学中出现的颜色量化问题的应用，我们提出了随机算法，以找到最佳的k-分区在一定的最优性标准，适合于此应用程序。

Over the last two years, we have tried to construct new parallel, randomized algorithms for network optimization problems, in particular for minimum cut problems. Recently, there has been much progress in the research of parallel and randomized algorithms for minimum cut problems. In this research project, we have focused on developing simple and efficient algorithms that work for a broader class of problems including minimum cut problems. In addition, we have also studied minimum k-clustering problems and could achieve new theoretical results on the problem under minimum variance criterion.In this project, we have first developed an O (m+nlogn) time algorithm for minimum range cut problems (n and m are the numbers of nodes and vertices in a graph). A minimum range cut problems asks to find a cut in weighted undirected graphs that minimizes the difference between maximum and minimum edge weights in the cut. Based on this algorithm, we developed a parallel, randomized algorithm for minimum cut problems. We then carried out extensive computer experiments to demonstrate the effectiveness of our approximate algorithm. As a result, we could show that our algorithm computes cuts that are very close to exact ones in time much faster than existing exact algorithms. We have further extended this algorithm to minimum k-cut problems and performed similar experiments.A minimum k-clustering problem asks to find a k-partition of a given set of n points in R^d based on certain optimality criteria. In our study, focusing on the application to color quantization problems arising in computer graphics, we have proposed randomized algorithms to find optimal k-partition under certain optimality criteria that are suitable for this application.