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.