Computing Minimum Cuts by Randomized Search Heuristics

We study the minimum s-t-cut problem in graphs with costs on the edges in the context of evolutionary algorithms. Minimum cut problems belong to the class of basic network optimization problems that occur as crucial subproblems in many real-world optimization problems and have a variety of applications in several different areas. We prove that there exist instances of the minimum s-t-cut problem that cannot be solved by standard single-objective evolutionary algorithms in reasonable time. On the other hand, we develop a bi-criteria approach based on the famous maximum-flow minimum-cut theorem that enables evolutionary algorithms to find an optimal solution in expected polynomial time.     

面向等几何分析的几何计算

等几何分析方法是一种直接基于CAD模型的精确几何表示进行物理性能仿真分析的新方法.文中从几何计算的视角出发,对等几何分析方法的基本框架,以及面向等几何分析的几何设计与计算的相关工作进行了介绍,重点介绍适合分析的计算域参数化、适合分析的新型样条理论、等几何配点法、面向等几何分析的并行计算等4个方向的研究进展.最后对需要进一步深入研究的关键问题进行了探讨.     

Strategies for Computing Minimal Free Resolutions

In the present paper we study algorithms based on the theory of Gröbner bases for computing free resolutions of modules over polynomial rings. We propose a technique which consists in the application of special selection strategies to the Schreyer algorithm. The resulting algorithm is efficient and, in the graded case, allows a straightforward minimalization algorithm. These techniques generalize to factor rings, skew commutative rings, and some non-commutative rings. Finally, the proposed approach is compared with other algorithms by means of an implementation developed in the new system Macaulay2.     

一种快速生成最小浓缩数据立方的算法

语义OLAP技术是近来学者研究的热点之一,浓缩数据立方就是其中一种.本文设计了一个用于快速生成最小浓缩数据立方的算法SQCube.算法分两个阶段：首先利用BottomUpBST算法生成一个非最小的浓缩数据立方,然后对所得到的非最小浓缩数据立方进行后处理,把其中的所有纯BST和隐BST压缩为一条BST,从而生成一个最小浓缩数据立方.实验表明SQCube算法明显优于以往提出的同类算法MinCube.     

第4届全国几何设计与计算学术会议征文通知

2009年8月24—28日中国厦门由中国工业与应用数学学会几何设计与计算专业委员会主办,厦门大学承办的第4届全国几何设计与计算学术会议(CSIAM Geometric Design & Computing 2009)定于2009年8月24—28日在福建省厦门市召开.本次会议将以几何设计和计算理论及其在工业中的应用为主题,结合工业设计中急需解决的关键问题和难点问题,开展广泛的学术交流和讨论.     

基于最小PC构架的可配置计算平台及应用

在机器视觉、军事、航空照相等领域需要在有限的空间内设计出小型化、灵活的、能够完成图像处理功能的系统。文中设计了一种以裁剪了的PC1 0 4构架为基础的可配置计算平台 ,该系统的PCB电路板面积只有 90mm× 6 8mm。以一个目标识别图像处理应用系统为例 ,给出了图像协处理器的7个乘法器并行、7级流水的内部结构设计方案。能够实现任意小于 7× 7模板的 2维图像卷积处理算法 ,获得了较高的图像处理性能     

Computing Minimal Multi-Homogeneous Bezout Numbers Is Hard

The multi-homogeneous Bezout number is a bound for the number of solutions of a system of multi-homogeneous polynomial equations, in a suitable product of projective spaces. Given an arbitrary, not necessarily multi-homogeneous, system, one can ask for the optimal multi-homogenization that would minimize the Bezout number. In this paper it is proved that the problem of computing, or even estimating, the optimal multi-homogeneous Bezout number is actually NP-hard. In terms of approximation theory for combinatorial optimization, the problem of computing the best multi-homogeneous structure does not belong to APX, unless P = NP. Moreover, polynomial-time algorithms for estimating the minimal multi-homogeneous Bezout number up to a fixed factor cannot exist even in a randomized setting, unless BPP ⫆ NP.     

Omnidirectional Robot Vision Using Conformal Geometric Computing

In this paper, we show how to use the conformal geometric algebra (CGA) as a framework to model the different catadioptric systems using the unified model (UM). This framework is well suited since it can not only represent points, lines and planes, but also point pairs, circles and spheres (geometric objects needed in the UM). We define our model using the great expressive capabilities of the CGA in a more general and simpler way, which allows an easier implementation in more complex applications. On the other hand, we also show how to recover the projective invariants from a catadioptric image using the inverse projection of the UM. Finally, we present applications in navigation and object recognition. Carlos Alberto López-Franco is a doctoral student at CINVESTAV, GEOVIS Laboratory, Unidad Guadalajara, México. He received in 2003 the M.S. degree in Computer Science from CINVESTAV, Unidad Guadalajara. His scientific interests are in the fields of computer vision, robotics and the applications of geometric algebra for mobile robots. Eduardo Jose Bayro-Corrochano gained his Ph.D. in Cognitive Computer Science in 1993 from the University of Wales at Cardiff. From 1995 to 1999 he has been Researcher and Lecturer at the Institute for Computer Science, Christian Albrechts University, Kiel, Germany, working on applications of geometric Clifford algebra to cognitive systems. At present is a full professor at CINVESTAV Unidad Guadalajara, México, Department of Electrical Engineering and Computer Science. His current research interest focuses on geometric methods for artificial perception and action systems. It includes geometric neural networks, visually guided robotics, color image processing, Lie bivector algebras for early vision and robot maneuvering. He developed the quaternion wavelet transform for quaternion multi-resolution analysis using the phase concept. He is associate editor of Robotics and Journal of Advanced Robotic Systems and member of the editorial board of Journal of Pattern Recognition, Journal of Mathematical Imaging and Vision, Iberoamerican Journal of Computer and Systems and Journal Of Theoretical And Numerical Approximation. He is editor and author of the following books: Geometric Computing for Perception Action Systems, E. Bayro-Corrochano, Springer Verlag, 2001; Geometric Algebra with Applications in Science and Engineering, E. Bayro-Corrochano and G. Sobczyk (Eds.), Birkahauser 2001; Handbook of Geometric Computing for Pattern Recognition, Computer Vision, Neurocomputing and Robotics, E. Bayro-Corrochano, Springer Verlag, 2005. He has published over 120 refereed journal, book chapters and conference papers.     

Interactive Collaborative Visualization Environment for Geometric Computing

This paper investigates the visualization of geometric computing in heterogeneous distributed environments. We show how focusing in a well-defined domain makes it possible to develop a compact system that is accessible to even naive users. We present a conceptual model and a system, GASP-II, that realizes this model in the geometric domain. The system allows the presentation and interactive exploration of three-dimensional geometric algorithms over the network.     

The Complexity of Computing Minimal Unidirectional Covering Sets

A common thread in the social sciences is to identify sets of alternatives that satisfy certain notions of stability according to some binary dominance relation. Examples can be found in areas as diverse as voting theory, game theory, and argumentation theory. Brandt and Fischer (in Math. Soc. Sci. 56(2):254–268, 2008) proved that it is NP-hard to decide whether an alternative is contained in some inclusion-minimal unidirectional (i.e., either upward or downward) covering set. For both problems, we raise this lower bound to the $\varTheta_{2}^{p}$ level of the polynomial hierarchy and provide a $\varSigma_{2}^{p}$ upper bound. Relatedly, we show that a variety of other natural problems regarding minimal or minimum-size unidirectional covering sets are hard or complete for either of NP, coNP, and  $\varTheta_{2}^{p}$ . An important consequence of our results is that neither minimal upward nor minimal downward covering sets (even when guaranteed to exist) can be computed in polynomial time unless P=NP. This sharply contrasts with Brandt and Fischer’s result that minimal bidirectional covering sets are polynomial-time computable.     

Algorithms for Computing Minimal Unsatisfiable Subsets of Constraints

Much research in the area of constraint processing has recently been focused on extracting small unsatisfiable “cores” from unsatisfiable constraint systems with the goal of finding minimal unsatisfiable subsets (MUSes). While most techniques have provided ways to find an approximation of an MUS (not necessarily minimal), we have developed a sound and complete algorithm for producing all MUSes of an unsatisfiable constraint system. In this paper, we describe a relationship between satisfiable and unsatisfiable subsets of constraints that we subsequently use as the foundation for MUS extraction algorithms, implemented for Boolean satisfiability constraints. The algorithms provide a framework with which many related subproblems can be solved, including relaxations of completeness to handle intractable instances, and we develop several variations of the basic algorithms to illustrate this. Experimental results demonstrate the performance of our algorithms, showing how the base algorithms run quickly on many instances, while the variations are valuable for producing results on instances whose complete results are intractably large. Furthermore, our algorithms are shown to perform better than the existing algorithms for solving either of the two distinct phases of our approach.     

Computing Only Minimal Answers in Disjunctive Deductive Databases

A method is presented for computing minimal answers of the form in disjunctive deductive databases under the disjunctive stable model semantics. Such answers are constructed by repeatedly extending partial answers. Our method is complete (in that every minimal answer can be computed) and does not admit redundancy (in the sense that every partial answer generated can be extended to a minimal answer), thus no non-minimal answer is generated. The method does not (necessarily) require the computation of models of the database in their entirety. A partitioning of the database into extensional and intensional components is employed in order to overcome the problems caused by the possible non-existence of disjunctive stable models, and a form of compilation is presented as a means of simplifying and improving the efficiency of the run-time computation, which then reduces to relatively trivial processing within the extensional database. In addition, the output from this compilation process has the significant advantage of being immune to updates to the extensional database. Other forms of database pre-processing are also considered, and three transformations are presented mapping a database onto an equivalent positive database, non-disjunctive database, and set of conditional facts.     

基于动态极大度的极小碰集求解方法

在计算集合簇的碰集时,结合SE-Tree(set enumeration tree)形式化地表达计算过程,逐步生成所有的极小碰集.并在SE-Tree中添加了终止结点,避免了非极小碰集的产生,并且不会因剪枝而丢失正确的解.提出未扩展元素度的概念和结点度的概念,进而在扩展SE-Tree结点时按照未扩展元素度由大到小的顺序扩展,极早地生成集合簇的碰集,减少枚举树生成的结点个数,并且直接根据结点度得出结点对应的集合是否为集合簇的碰集,避免计算集合是否为集合簇的碰集.实验结果表明,该算法程序容易编制且效率较好.     

3D打印中的几何计算研究进展

3D打印技术改变了传统的减式材料制造模式,带来了制造工艺和生产模式的变革,有力地推动了3D数字化相关技术与研究的发展.文中从3D打印的社会背景与理论背景出发,介绍了3D打印技术的分类、原理与过程.以此为基础,对近几年的3D打印中的几何计算问题给出了全面的综述,根据问题特点将其分为几何优化、结构分析、材料表面效果定制、机构设计、自支撑结构设计、内部结构设计等六大类,并对每一类作了详细的分类介绍,最后对其发展方向作了初步展望.     

Efficient Update Strategies for Geometric Computing with Uncertainty

We consider the problems of computing maximal points and the convex hull of a set of points in two dimensions, when the points are “in motion.” We assume that the point locations (or trajectories) are not known precisely and determining these values exactly is feasible, but expensive. In our model the algorithm only knows areas within which each of the input points lie, and is required to identify the maximal points or points on the convex hull correctly by updating some points (i.e., determining their location exactly). We compare the number of points updated by the algorithm on a given instance to the minimum number of points that must be updated by a nondeterministic strategy in order to compute the answer provably correctly. We give algorithms for both of the above problems that always update at most three times as many points as the nondeterministic strategy, and show that this is the best possible. Our model is similar to that in [3] and [5].     

Maximum Cardinality Search for Computing Minimal Triangulations of Graphs

We present a new algorithm, called MCS-M, for computing minimal triangulations of graphs. Lex-BFS, a seminal algorithm for recognizing chordal graphs, was the genesis for two other classical algorithms: LEX M and MCS. LEX M extends the fundamental concept used in Lex-BFS, resulting in an algorithm that not only recognizes chordality, but also computes a minimal triangulation of an arbitrary graph. MCS simplifies the fundamental concept used in Lex-BFS, resulting in a simpler algorithm for recognizing chordal graphs. The new algorithm MCS-M combines the extension of LEX M with the simplification of MCS, achieving all the results of LEX M in the same time complexity.