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

网络优化问题并行随机算法的构建与评估

基本信息

批准号：
05680281
负责人：
KATOH Naoki
金额：
$ 1.22万
依托单位：
KOBE UNIVERSITY OF COMMERCE
依托单位国家：
日本
项目类别：
Grant-in-Aid for General Scientific Research (C)
财政年份：
1993
资助国家：
日本
起止时间：
1993 至 1994
项目状态：
已结题

项目摘要

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.

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