演講公告

演講主題：Counting various types of separable partitions for points in d-space
主講人：黃光明教授 (交通大學退休講座教授)
演講日期：98年10月13日(星期二) <br>下午2:00 - 3:20
演講地點：(光復校區)科學一館223室
摘要內容：
The problem is to partition a set of n points in d-space into p disjoint subsets (called parts) to maximize (or minimize) a given objective function. An example is the clustering problem which seeks to minimize the within-part distances. It is in general very difficult to find optimal partitions and heuristic solutions are given in most cases. Our approach is to show that there exists an optimal partition in a class of partitions (usually characterized by a geometric property) whose size is polynomial in n. Then we can search for an optimal partition in that class in polynomial time.
Given a partition π, let π_1, … , π_ p denote its p parts and conv(π_ j) the convex hull of π_ j. Then π is called separable if for any j, k from 1 to p, conv(π_ j) ∩ conv(π_ k) = Ø. π is called almost separable if the above intersection can consist of at most one point which must be a vertex of both convex hulls. There are two other classes “cone-separable” and “sphere-separable” to be defined in the talk. We will count the numbers of partitions in all four classes and show that they are all polynomial.
相關檔案：演講981013.pdf

$返回$ go back