Hypergraphs as algebraic structures

In the last decade, hypergraphs have been intensively used in problems of electrical engineering and network design, multi-index transport problems, computer simulation of complex dynamical systems, representation of complex control systems in manufacturing, and other science applications. Some (for example, multi-index transport) problems are best treated using k-complexes (a special class of hypergraphs in which each edge is incident upon exactly k vertices). The class of extreme 2-complexes is considered. Also, this class is represented as a distributive lattice.     

Multiindex transportation problems with 2-embedded structure

We consider multiindex transportation problems of linear and integer linear programming. As a method of solving them, we propose an approach based on reductions of multiindex transportation problems to min-flow problems. We show that under the reduction scheme we consider, the 2-embeddability condition for multiindex problems is a necessary and sufficient condition for the problem to be reducible to a min-cost flow problem.     

Hypergraph recovery algorithms from a given vector of vertex degrees

Methods of obtaining certain classes of hypergraphs from a given integer vector of vertex degrees are considered. These classes are as follows: hyperedges with unit weight incident upon k vertices; hyperedges with unit weight incident upon k vertices in the case when the vertices may be non-unique; multiple hyperedges incident upon k vertices; and arbitrary hypergraph in which the edges can contain any set of k vertices. For each of these classes, an algorithm is proposed for constructing the hypergraph from an arbitrary vector. If the construction is impossible, the algorithm determines how much the vector should be reduced so that the hypergraph could be constructed.     

A heuristic method for solving integer-valued decompositional multiindex problems

We consider NP-hard integer-valued multiindex problems of transportation type. We distinguish a subclass of polynomially solvable multiindex problems, namely multiindex problems with decomposition structure. We construct a general scheme for a heuristic method to solve a number of similar NP-hard decompositional multiindex problems. For one version of implementation for this scheme, we estimate its deviation from the optimum. We illustrate our results with the example of designing a class schedule.     

Development of Hypergraph Theory

In recent decades, the theory of hypergraphs has been applied to real-life problems. The tools of hypergraph theory can be used for modeling networks, biological networks, data structures, scheduling processes and computations, and many other systems with complex relationships between the entities. From the theoretical point of view, hypergraphs make it possible to generalize certain theorems in graph theory or even replace a number of theorems on graphs by one theorem on hypergraphs. However, the majority of the potentials in the development of hypergraph theory are blocked due to inconsistencies in the basic terms. It is proposed to make up a list of basic terms related to hypergraph theory, which can help standardize this theory.     

三参数区间灰数信息下的动态多属性决策方法

针对方案属性值为三参数区间灰数的动态多属性决策问题, 提出一种基于前景理论的动态多属性决策方法. 定义了三参数区间灰数距离测度和排序方法; 鉴于被评价对象在时序上的差异信息和波动性, 建立基于方差和时间度的确定时间权重的优化模型; 以两两方案互为参考点确定前景价值函数, 由此构建求解最优权向量的优化模型,并通过求解方案的综合前景值对方案进行排序. 实例研究表明了该方法的合理性和有效性.

     

On the Complexity of Strongly Connected Components in Directed Hypergraphs

We study the complexity of some algorithmic problems on directed hypergraphs and their strongly connected components (Sccs). The main contribution is an almost linear time algorithm computing the terminal strongly connected components (i.e. Sccs which do not reach any components but themselves). Almost linear here means that the complexity of the algorithm is linear in the size of the hypergraph up to a factor α(n), where α is the inverse of Ackermann function, and n is the number of vertices. Our motivation to study this problem arises from a recent application of directed hypergraphs to computational tropical geometry. We also discuss the problem of computing all Sccs. We establish a superlinear lower bound on the size of the transitive reduction of the reachability relation in directed hypergraphs, showing that it is combinatorially more complex than in directed graphs. Besides, we prove a linear time reduction from the well-studied problem of finding all minimal sets among a given family to the problem of computing the Sccs. Only subquadratic time algorithms are known for the former problem. These results strongly suggest that the problem of computing the Sccs is harder in directed hypergraphs than in directed graphs.     

Replicated partitioning for undirected hypergraphs

Hypergraph partitioning (HP) and replication are diverse but powerful tools that are traditionally applied separately to minimize the costs of parallel and sequential systems that access related data or process related tasks. When combined together, these two techniques have the potential of achieving significant improvements in performance of many applications. In this study, we provide an approach involving a tool that simultaneously performs replication and partitioning of the vertices of an undirected hypergraph whose vertices represent data and nets represent task dependencies among these data. In this approach, we propose an iterative-improvement-based replicated bipartitioning heuristic, which is capable of move, replication, and unreplication of vertices. In order to utilize our replicated bipartitioning heuristic in a recursive bipartitioning framework, we also propose appropriate cut-net removal, cut-net splitting, and pin selection algorithms to correctly encapsulate the two most commonly used cutsize metrics. We embed our replicated bipartitioning scheme into the state-of-the-art multilevel HP tool PaToH to provide an effective and efficient replicated HP tool, rpPaToH. The performance of the techniques proposed and the tools developed is tested over the undirected hypergraphs that model the communication costs of parallel query processing in information retrieval systems. Our experimental analysis indicates that the proposed technique provides significant improvements in the quality of the partitions, especially under low replication ratios.     

Multiindex resource distributions for hierarchical systems

Resource distribution in hierarchical systems is formulated as a multiindex linear programming problem under transport-type constraints. Conditions under which this problem is reduced to the determination of the minimal-cost circulation in a transport network are stated.     

A global parallel algorithm for the hypergraph transversal problem

We consider the problem of finding all minimal transversals of a hypergraph H⊆V², given by an explicit list of its hyperedges. We give a new decomposition technique for solving the problem with the following advantages: (i) Global parallelism: for certain classes of hypergraphs, e.g., hypergraphs of bounded edge size, and any given integer k, the algorithm outputs k minimal transversals of H in time bounded by polylog(|V|,|H|,k) assuming poly(|V|,|H|,k) number of processors. Except for the case of graphs, none of the previously known algorithms for solving the same problem exhibit this feature. (ii) Using this technique, we also obtain new results on the complexity of generating minimal transversals for new classes of hypergraphs, namely hypergraphs of bounded dual-conformality, and hypergraphs in which every edge intersects every minimal transversal in a bounded number of vertices.     

轨迹和多标签超图配对融合的视频复杂事件检测

视频数据中包含丰富的运动事件信息,从中检测复杂事件,分析其中的高层语义信息,已成为视频研究领域的热点之一。视频复杂事件检测,主要对事件中多语义概念进行检测分析,对多运动目标的特征进行描述,发现底层特征与高层语义概念间的关系,旨在从各类视频特征及相关的原始视频数据中自动提取视频复杂事件中语义概念模式,实现“跨越语义鸿沟”的目标。在超图理论的基础上,提出了针对运动目标特征分别构建轨迹超图和多标签超图,并对其进行配对融合,用于检测视频复杂事件。实验结果证明,同其他方法如基于普通图的事件检测方法和基于超图的多标签半监督学习方法相比,新方法在检测复杂事件结果中具有更高的平均查准率和平均查全率。     

Comprehensive evaluation of new urban transportation systems by AHP

Many different kinds of transportation systems such as ‘group rapid transit’, etc., have recently been presented as ideal urban public transportation systems. When planning to introduce such a new transportation system into a city, it is necessary to select the most desirable system for that city from those that have been proposed. The comprehensive evaluation of transportation systems must reflect various aspects such as the costs of construction and maintenance and the viewpoints or both the system users and the local inhabitants. This makes it one of the most difficult and yet vitally important problems in public transportation planning. The analytic hierarchy process (AHP) developed by T. L Saaty is straightforward and has the feature that it can deal with both qualitative and quantitative factors at the same time, and it is suitable for applying to complex evaluation problems, In this paper, three transportation systems are proposed for one of the newly planned towns in Kansai Cultural and Academic Research Complexes, and a comprehensive evaluation of these systems is performed by applying the AHP. It has been proved through the process of evaluation that information which is very useful in reaching a consensus for choosing a system can be obtained.     

Nearly-perfect hypergraph packing is in NC

Answering a question of Rödl and Thoma, we show that the Nibble Algorithm for finding a collection of disjoint edges covering almost all vertices in an almost regular, uniform hypergraph with negligible pair degrees can be derandomized and parallelized to run in polylog time on polynomially many parallel processors. In other words, the nearly-perfect packing problem on this class of hypergraphs is in the complexity class NC.     

Polyhedral Feasible Set Computation of MPC-Based Optimal Control Problems

Feasible sets play an important role in model predictive control (MPC) optimal control problems (OCPs). This paper proposes a multi-parametric programming-based algorithm to compute the feasible set for OCP derived from MPC-based algorithms involving both spectrahedron (represented by linear matrix inequalities) and polyhedral (represented by a set of inequalities) constraints. According to the geometrical meaning of the inner product of vectors, the maximum length of the projection vector from the feasible set to a unit spherical coordinates vector is computed and the optimal solution has been proved to be one of the vertices of the feasible set. After computing the vertices, the convex hull of these vertices is determined which equals the feasible set. The simulation results show that the proposed method is especially efficient for low dimensional feasible set computation and avoids the non-unicity problem of optimizers as well as the memory consumption problem that encountered by projection algorithms.      

Online coloring of hypergraphs

We give a tight bound on randomized online coloring of hypergraphs. The bound holds even if the algorithm knows the hypergraph in advance (but not the ordering in which it is presented). More specifically, we show that for any n and k, there is a 2-colorable k-uniform hypergraph on n vertices for which any randomized online coloring uses Ω(n/k) colors in expectation.     

Artificial societies for integrated and sustainable development of metropolitan systems

Unfortunately, we can't solve transportation problems by focusing on transportation systems alone. Rather, we must consider the combined effects with other metropolitan systems. Artificial systems, based on artificial societies and agent-modeling technology, are effective tools for this purpose. Metropolitan transportation, logistics, and ecosystems are intrinsically open, dynamic, unpredictable, and complex in their behaviors and effects. We must adopt a management and control strategy for those systems based on continuous investigation and improvement and should use computational experiments with artificial systems to overcome the difficulty of experimenting with real systems.     

Mathematical morphology on hypergraphs,application to similarity and positive kernel

The focus of this article is to develop mathematical morphology on hypergraphs. To this aim, we define lattice structures on hypergraphs on which we build mathematical morphology operators. We show some relations between these operators and the hypergraph structure, considering in particular transversals and duality notions. Then, as another contribution, we show how mathematical morphology can be used for classification or matching problems on data represented by hypergraphs: thanks to dilation operators, we define a similarity measure between hypergraphs, and we show that it is a kernel. A distance is finally introduced using this similarity notion.     

Parallel decomposition of combinatorial optimization problems using electro-optical vector by matrix multiplication architecture

A new state space representation for a class of combinatorial optimization problems, related to minimal Hamiltonian cycles, enables efficient implementation of exhaustive search for the minimal cycle in optimization problems with a relatively small number of vertices and heuristic search for problems with large number of vertices. This paper surveys structures for representing Hamiltonian cycles, the use of these structures in heuristic optimization techniques, and efficient mapping of these structures along with respective operators to a newly proposed electrooptical vector by matrix multiplication (VMM) architecture. Record keeping mechanisms are used to improve solution quality and execution time of these heuristics using the VMM. Finally, the utility of a low-power VMM based implementation is evaluated.     

面向大尺寸货物运送的吊车控制方法综述

随着现代化工业和基础设施建设的飞速发展,面向大尺寸货物运送的吊车系统以其高负载能力、低成本的显著优势广泛应用于集装箱搬运、风机安装、飞机机翼机身移动、水轮发电机转子安装、海上钻井平台搭建等诸多重要领域。然而,相对于传统的点质量单摆吊车系统,面向大尺寸货物运送的吊车系统具有更高的欠驱动程度、更强的状态耦合性和更加复杂的非线性,给大尺寸货物高效、安全的运送控制带来严峻挑战。本文首先简单阐述了面向大尺寸货物运送吊车系统不同吊装形式的建模、优势和缺点;然后,详细介绍了点质量双摆吊车系统、分布式质量双摆吊车系统和多吊车协同运送系统控制的研究现状;最后,对面向大尺寸货物运送吊车系统控制的研究现状进行概括,并对可能存在的关键问题和未来的研究方向进行了讨论和展望。