基于最小最大割算法的阈值分割算法

近年来,建立在图论基础上的谱聚类算法作为一种新型的工具被应用于图像分割。其本质是将图像分割转化为最优化问题,其中的最小最大割算法(Min-max cut)能充分满足聚类算法的准则。算法实现过程中,把最优化准则转化为特征系统进行求解。该实现方法计算复杂,随着图像尺寸的增加,所需存储空间和计算时间复杂度都会增加。在实现最小最大割算法时,用基于灰度级的权值矩阵代替通常所用的基于图像像素的权值矩阵来描述图像各像素的关系,确定分割的阈值。实验表明,此方法实现的最小最大割算法实现简单、实时性高,具有自动分割等优越的分割性能。     

几类特殊图中的最小最大多路割

给定边具有正权的无向图,并指定若干个称为终端的顶点,最小最大多路割问题是要得到所有顶点的一个聚类,要求每个子类恰好包含一个终端,并使得所有子类的最大费用最小。子类的费用定义为该子类边界上所有边的权之和。最小最大多路割问题源于对等网络中的数据放置,是传统多路割问题的一个变形。当给定无向图是树图时,这一问题已经是强NP难解的。对于链图和环图,给出了线性时间的精确算法,该算法同时也使得所有子类的总费用最小。对于树图和限制树宽图,给出了(2-1/2k2)-近似算法,k表示终端的数目。     

Minimum degree triangulation for rectangular domains

This paper describes an optimal triangulation algorithm for rectangles. We derive lower bounds on the maximum degree of triangulation, and show that our triangulation algorithm matches the lower bounds. Several important observations are also made, including a zig-zag condition that can verify whether a triangulation can minimizes the maximum degree to 4 or not. In addition, this paper identifies the necessary and sufficient condition that there exists a maximum degree 4 triangulation for convex polygons, and gives a linear time checking algorithm.     

Inverse problems of biological systems using multi-objective optimization

Mathematical modeling for dynamic biological systems is a central theme in systems biology. There are still many challenges in using time-course data to obtain an inverse problem of nonlinear dynamic biological systems. In this study, a multi-objective optimization technique is introduced to determine kinetic parameter values of biochemical reaction systems. The multi-objective parameter estimation was converted into the minimax problem through the satisfying trade-off method. The aspiration value was assigned as the minimum solution to the corresponding single objective estimation. The aim of this trade-off estimation was to obtain a compromised result by simultaneously minimizing both concentration and slope error criteria. Hybrid differential evolution was applied to solve the minimax problem and to yield a global estimation.     

Piecewise affinity of min-max MPC with bounded additive uncertainties and a quadratic criterion

This brief shows how a min-max MPC with bounded additive uncertainties and a quadratic cost function results in a piecewise affine and continuous control law. Proofs based on properties of the cost function and the optimization problem are given. The boundaries of the regions in which the state space can be partitioned are also treated. The results are illustrated by an example.