Development of Optimal Algorithms for Partitioning Geometric Data

几何数据分区最优算法的开发

• 批准号: 10680353
• 负责人: KATOH Naoki
• 金额: $ 1.02万
• 依托单位: KYOTO UNIVERSITY
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 1998
• 资助国家: 日本
• 起止时间: 1998 至 1999
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-10680353/
• 关键词: optimal partition; geometric data; vehicle routing; approximation algorithm; data mining; semidefinite programming; 車両配送計画; 最適二次元相関ルール; 計算幾何学; 耳両配送計画; クラス間分散; クラスタリング

Over the last two years, we have tried to develop efficient algorithms for optimally partitioning geometric data such as point set in the plane and pixel data on two-dimensional grid. The problems we studied and results we obtained are summarized as follows.(1) we deal with a vehicle routing on a tree-shaped network with a single depot. Customers are located on vertices of the tree, and each customer has a positive demand. Demands of customers are served by a fleet of identical vehicles with limited capacity. It is assumed that the demand of a customer is splittable. We considered the problem for finding a set of tours with minimum total lengths. In the first year, we showed that the problem is NP-complete and proposed a 1.5-approximation algorithm for the problem. We also performed some computational experiments. In the second year, the approximation ration is improved to 1.35 by further refining the first algorithm.(2) We considered the problem of finding an optimal interval in one-dimensional array and a region in two-dimensional array under several optimality criteria. In particular, we shall consider the problem of finding an interval I∈[1,n] that maximizes the interclass variance. We shall present an O(n log n)time algorithm for this problem. We then extend this algorithm to two-dimensional case. Namely, given a N×N two-dimensional array, the problem seeks to find a rectangular subarray R with maximum interclass variance. We developed an O(NィイD13ィエD1)algorithm.(3) We considered the problem of finding two-dimensional association rules for categorical attributes and developed an algorithm based on semidefinite programming.

在过去的两年中，我们必须开发最佳分区的算法，例如平面中的ASET和二维网格的数据，并总结了我们所研究的结果。单个仓库的需求。 -porte and proted A Approximation算法对于问题，我们在第二年进行了一些计算。 t在严重程度标准下的一维数组和artegion。然后，我们将此算法扩展到二维情况，我们开发了O（N -I D13 YIE D1）。基于编程的算法。

项目成果

Mashe Dror,J.Blazewice,W.Kubiak,N.Katoh,H.Rock: "Rescue Constraind Chain Scheduling and Serializability Problem." Operations Research. Vol.46,NO.5. 742-746 (1998)

Mashe Dror、J.Blazewice、W.Kubiak、N.Katoh、H.Rock：“救援约束链调度和可串行性问题。”

浅野 哲夫: "木構造ネットワーク上の車両配送計画問題の新しい近似解法"情報処理学会研究報告. 99-AL-68. (1999)

Tetsuo Asano：“树结构网络上车辆交付规划问题的一种新的近似解决方法”，日本信息处理协会研究报告 99-AL-68。

N.Katoh: "Finding an Optimal Region in One-and Two-Dimensional Arrays"IEICE Transactions on Fundamentals, March. (2000)

N.Katoh：“在一维和二维数组中寻找最佳区域”IEICE 基础交易，三月。

S.Hamaguchi,N.Katoh: "A vehicle scheduling problem on a tree" Proc.of ISAAC'98,Springer-Verag. 397-406 (1998)

S.Hamaguchi，N.Katoh：“树上的车辆调度问题”Proc.of ISAAC98，Springer-Verag。

N.Katoh: "Parametric polymatroid optimization and its geometric applications"Proc. of 9th ASM/SIAM Symposium on Discrete Algorithms. 517-526 (1999)

N.Katoh：“参数多拟阵优化及其几何应用”Proc。