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

在过去的两年里，我们试图构建新的并行随机算法来解决网络优化问题，特别是最小割问题。近年来，关于最小割问题的并行和随机化算法的研究取得了很大进展。在这个研究项目中，我们专注于开发简单而高效的算法，这些算法适用于包括最小割问题在内的更广泛类别的问题。此外，我们还研究了最小k-聚类问题，并在最小方差准则下得到了新的理论结果。在这个项目中，我们首次提出了求解最小范围割问题的O(m+nlogn)时间算法(n和m是图中的节点数和顶点数)。最小范围割问题要求在加权无向图中找到一个割，使割中的最大边权和最小边权之差最小。在此基础上，我们提出了一种求解最小割问题的并行随机算法。然后，我们进行了大量的计算机实验，以证明我们的近似算法的有效性。因此，我们可以证明，我们的算法在时间上计算非常接近精确的切割比现有的精确算法快得多。我们进一步将该算法推广到最小k-割问题，并进行了类似的实验。最小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.