An Algorithm for Constructing a Minimal-Volume Ellipsoid

In the article, we propose a new algorithm for constructing a minimal-volume ellipsoid for a given finite collection of points in an m-dimensional Euclidean space. The algorithm is based on a construction of such ellipsoids for the most simple polyhedra.     

一个绘制统筹图的算法

统筹图又叫计划网络图。任给一个其元素叫做工序（或作业或活动）的有限偏序集，要绘制它的一个最优统筹图，限含虚工序数目为最少者，是一个尚未从理论上解决的问题。本文讨论了虚工序产生的原因和如何减少虚工序数量的一些途径；指出了高度为二的编序集其最优统筹图含虚工序数目达到最大且等于该偏序集框图的边数的充分必要条件；本文给出了一个绘制最优统筹图的近似算法，此算法弥补了文[2]和[3]所给算法的一些不足之处。     

An Algorithm Constructing Solutions for a Family of Linear Semi-Infinite Problems

A family of linear semi-infinite problems depending on a parameter is considered. For fixed , a sensitivity analysis of the problem solution is carried out and rules constructing the solutions of this family for in a right-side neighborhood of ₀ are described. Results on the one-sided derivatives of the solution with respect to the parameter are presented. On the basis of the results, an active-set-strategy and a path-following algorithm are suggested.     

求有限集合覆盖的构造方法

在近似算法领域,集合覆盖问题是研究的比较早和比较透彻的问题之一.文中解决与经典SCP不同的另一问题,针对有限集合覆盖的构造,提出一种构造有限集合上的集合覆盖的算法,并且给出了该算法的完备性证明.该算法简单有效,是一种用于构造集合覆盖的规范方法.     

On a k-Tree Containing Specified Leaves in a Graph

A k-tree of a graph is a spanning tree with maximum degree at most k. We give sufficient conditions for a graph G to have a k-tree with specified leaves: Let k,s, and n be integers such that k≥2, 0≤s≤k, and n≥s+1. Suppose that (1) G is (s+1)-connected and the degree sum of any k independent vertices of G is at least |G|+(k−1)s−1, or (2) G is n-connected and the independence number of G is at most (n−s)(k−1)+1. Then for any s specified vertices of G, G has a k-tree containing them as leaves. We also discuss the sharpness of the results. This research was partially supported by the Ministry of Education, Science, Sports and Culture, Grant-in-Aid for Encouragement of Young Scientists, 15740077, 2005 This research was partially supported by the Japan Society for the Promotion of Science for Young Scientists.     

Matroid Enumeration for Incidence Geometry

Matroids are combinatorial abstractions for point configurations and hyperplane arrangements, which are fundamental objects in discrete geometry. Matroids merely encode incidence information of geometric configurations such as collinearity or coplanarity, but they are still enough to describe many problems in discrete geometry, which are called incidence problems. We investigate two kinds of incidence problem, the points–lines–planes conjecture and the so-called Sylvester–Gallai type problems derived from the Sylvester–Gallai theorem, by developing a new algorithm for the enumeration of non-isomorphic matroids. We confirm the conjectures of Welsh–Seymour on ≤11 points in ℝ³ and that of Motzkin on ≤12 lines in ℝ², extending previous results. With respect to matroids, this algorithm succeeds to enumerate a complete list of the isomorph-free rank 4 matroids on 10 elements. When geometric configurations corresponding to specific matroids are of interest in some incidence problems, they should be analyzed on oriented matroids. Using an encoding of oriented matroid axioms as a boolean satisfiability (SAT) problem, we also enumerate oriented matroids from the matroids of rank 3 on n≤12 elements and rank 4 on n≤9 elements. We further list several new minimal non-orientable matroids.     

On the Structure of a k-Connected Graph

For a k-connected graph G, we introduce the notion of a block and construct a block tree. This construction generalizes, for , the known constructions for blocks of a connected graph. We apply the introduced notions to describe the set of vertices of a k-connected graph G such that the graph remains k-connected after deleting these vertices. We discuss some problems related to simultaneous deleting of vertices of a k-connected graph without loss of k-connectivity. Bibliography: 5 titles.     

树与偏k—的乘积的树宽

本文确宇了一棵树与一个k-连通偏k-树的乘积图的树宽。其中,偏k-树是一个树宽为k的图。     

构造Lax表示的新算法

基于微分特征列法和微分带余除法,给出了利用拟微分算子构造非线性发展方程1+1维和2+1维Lax表示的新算法.新算法减少了运算步骤,简化了计算过程,是微分特征列法在可积系统领域一个新的应用.     

构造二维双曲型方程完全守恒差分格式的一种方法

§1 许多物理过程(例如气动力学,激光等离子体相互作用,磁流体力学,基本粒子输运等)的数学模型均可写成偏导数形式的二维不定常偏微分方程组:     

Algorithms for Measuring Perturbability in Matroid Optimization

perturbability function of a matroid measures the maximum increase in the weight of its minimum weight bases that can be produced by increases of a given total cost on the weights of its elements. We present an algorithm for computing this function that runs in strongly polynomial time for matroids in which independence can be tested in strongly polynomial time. Furthermore, for the case of transversal matroids we are able to take advantage of their special structure to design a faster algorithm for computing the perturbability function. Received: June 13, 1997     

Geometric Lower Bounds for Parametric Matroid Optimization

We relate the sequence of minimum bases of a matroid with linearly varying weights to three problems from combinatorial geometry: k -sets, lower envelopes of line segments, and convex polygons in line arrangements. Using these relations we show new lower bounds on the number of base changes in such sequences: Ω(nr ^1/3 ) for a general n -element matroid with rank r , and Ω(mα(n)) for the special case of parametric graph minimum spanning trees. The only previous lower bound was Ω(n log r) for uniform matroids; upper bounds of O(mn ^1/2 ) for arbitrary matroids and O(mn ^1/2 / log ^* n) for uniform matroids were also known. Received November 12, 1996, and in revised form February 19, 1997.     

求最大匹配的一个新算法

简单无向图G的最大匹配问题分为二部图和一般图的最大匹配两类。前者主要采用可增广路的思想解决,〔1〕中已经详述;本文主要讨论有关后者的算法。 定义 设G=(V,E)是简单无向图,在G的所有匹配M′中,若M=max|M′|,则称M是G的一个最大匹配。     

The Lattice of Cyclic Flats of a Matroid

A flat of a matroid is cyclic if it is a union of circuits. The cyclic flats of a matroid form a lattice under inclusion. We study these lattices and explore matroids from the perspective of cyclic flats. In particular, we show that every lattice is isomorphic to the lattice of cyclic flats of a matroid. We give a necessary and sufficient condition for a lattice of sets and a function to be the lattice of cyclic flats of a matroid and the restriction of the corresponding rank function to . We apply this perspective to give an alternative view of the free product of matroids and we show how to compute the Tutte polynomial of the free product in terms of the Tutte polynomials of the constituent matroids. We define cyclic width and show that this concept gives rise to minor-closed, dual-closed classes of matroids, two of which contain only transversal matroids. Received May 29, 2005     

Weight Distribution of the Bases of a Matroid

Given a weighted graph, let w₁, w₂, . . . ,w_n denote the increasing sequence of all possible distinct spanning tree weights. In 1992, Mayr and Plaxton proved the following conjecture proposed by Kano: every spanning tree of weight w₁ is at most k−1 edge swaps away from some spanning tree of weight w_k. In this paper, we extend this result for matroids. We also prove that all the four conjectures due to Kano hold for matroids provided one partitions the bases of a matroid by the weight distribution of its elements instead of their weight. The author was partially supported by CNPq (Grant No. 302195/02-5) and ProNEx/CNPq (Grant No. 664107/97-4)     

Algorithm for Constructing a Guaranteeing Program Package in a Control Problem with Incomplete Information

A package control problem is considered for a target set at a moment of time. The dynamic system under control is described by linear differential equations, the control area is a convex compact, and the target set is convex and closed. A version of the subsequent approximations method in extended space is proposed for constructing elements of a guaranteeing program package in the case of regular clusters.     

分形曲面的构造算法研究

以分形理论为依据 ,根据分形几何描绘自然界景物的基本思想 ,结合解析几何中旋转曲面的构造 ,把已生成的二维平面分形曲线绕着同一平面上的直线旋转 ,获得一类三维旋转曲面的构造算法 ,给出了相应的三维迭代函数系统和三维仿射变换矩阵 ,并进行了深入的理论分析 .本文的研究为分形曲面的构造探求了一种简易算法 ,并为分形曲面的生成和实践应用提供了理论依据 .