Development of Optimal Algorithms for Partitioning Geometric Data

点击翻译按钮获取中文摘要

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.