Efficient Algorithms for Variants of Weighted Matching and Assignment Problems

Obtaining a matching in a graph satisfying a certain objective is an important class of graph problems. Matching algorithms have received attention for several decades. However, while there are efficient algorithms to obtain a maximum weight matching, not much is known about the maximum weight maximum cardinality, and maximum cardinality maximum weight matching problems for general graphs. Our contribution in this work is to show that for bounded weight input graphs one can obtain an algorithm for both maximum weight maximum cardinality (for real weights), and maximum cardinality maximum weight matching (for integer weights) by modifying the input and running the existing maximum weight matching algorithm. Also, given the current state of the art in maximum weight matching algorithms, we show that, for bounded weight input graphs, both maximum weight maximum cardinality, and maximum cardinality maximum weight matching have algorithms of similar complexities to that of maximum weight matching. Subsequently, we also obtain approximation algorithms for maximum weight maximum cardinality, and maximum cardinality maximum weight matching.      

多属性决策的组合赋权优化方法

针对多属性决策中属性权重的确定问题，提出了一种主观权重与客观权重的集成方法。对每个决策属性，将各个决策者给出的主观权重和客观权重作为样本点，采用规划的方法来集成主观权重和客观权重，使决策结果更加可靠、可信。     

综合评价中权数的函数性质及其生成研究

通过对权数进行系统的研究,本文认为从"权数的性质"这个角度出发,权数具有"重要性"、"模糊性"、"主观性"和"时序性".将区域因素考虑进去,提出了权数具有"空间性","时空性"的观点.进一步,随着时间或区域的连续变化时,若权数也连续取值,则此时权数可以看成函数的形式,并给出两种具体的方法求权函数.特别针对权函数取值范围在0和1之间,将其进行函数变换后,通过新函数(权函数的Logit函数)的函数生成方法,进而得出权函数的生成方法.最后通过例子说明该方法比较符合权数的实际取值.     

一种新型的多属性决策权重计算方法

如何科学、合理地确定指标权重，关系到多属性决策结果的可靠性与正确性。现有多属性决策方法大多不能反映不同决策矩阵规范化方法对指标权重计算的影响，针对这一问题，本文提出了基于不同规范化矩阵确定指标权重的思想，进而推导了一种以全部方案总体效能最小为目标的指标权重模糊优化迭代算法。以向量规范法和线性变换法为例，对某战斗机性能多属性决策问题进行了权重计算。计算结果表明，该方法能够快速收敛到优化权重，从而为多属性决策的权重计算问题提供了新的解决方案。     

Classification of simple weight Virasoro modules with a finite-dimensional weight space

We show that the support of a simple weight module over the Virasoro algebra, which has an infinite-dimensional weight space, coincides with the weight lattice and that all non-trivial weight spaces of such module are infinite-dimensional. As a corollary we obtain that every simple weight module over the Virasoro algebra, having a non-trivial finite-dimensional weight space, is a Harish-Chandra module (and hence is either a simple highest or lowest weight module or a simple module from the intermediate series). This implies positive answers to two conjectures about simple pointed and simple mixed modules over the Virasoro algebra.     

The structure of linear codes of constant weight

In this paper we determine completely the structure of linear codes over of constant weight. Namely, we determine exactly which modules underlie linear codes of constant weight, and we describe the coordinate functionals involved. The weight functions considered are: Hamming weight, Lee weight, two forms of Euclidean weight, and pre-homogeneous weights. We prove a general uniqueness theorem for virtual linear codes of constant weight. Existence is settled on a case by case basis.

     

Mathematical modelling and computational analysis of enzymatic degradation of xenobiotic polymers

We study the enzymatic degradation of xenobiotic polymers mathematically. As a mathematical model, we derive a linear second-order hyperbolic partial differential equation which governs the evolution of the weight distribution with respect to the molecular weight. Given an initial weight distribution and a final weight distribution, we formulate a problem to determine a degradation rate. We establish a necessary and sufficient condition for which the problem has a local solution. We also introduce a numerical technique based on our analysis, and present a numerical result that we obtained applying weight distributions before and after enzymatic degradation of polyvinyl alcohol.     

小麦茎秆与单穗重的相关性分析

主要是分析茎秆与单穗重和产量的相关性.以6个小麦品种为材料,分别测取了穗下茎长,茎粗,穗长,株高,节壁厚,节重及单穗重,对茎质与穗重进行了相关分析,结果表明:茎秆性状与穗重存在不同程度的相关性.其中,茎粗与单穗重呈正相关;节壁厚与单穗重呈正相关;节壁重与单穗重呈正相关;而株高和茎长与单穗重的关系不明显且较为复杂,应分情况讨论.     

一种新的变权向量及其应用

在对常权综合和变权综合进行分析的基础上,结合变权的初衷,构造了一个新的变权向量用于变权综合.构造的变权满足变权向量的公理条件和加型综合函数的定义,运用这个变权公式进行加权综合分析时,综合决策值等于加权均值减去加权方差的一半,具有很好的实际意义.     

连续偏序集及其Smyth幂的几个等权定理

推广连续D om a in的权的概念到连续偏序集上,探讨连续偏序集的权、相应内蕴拓扑的权、定向完备化的权以及Sm yth幂D om a in的权间的关系。得到了几个等权定理:(1)连续偏序集的权与其上Scott拓扑、L aw son拓扑的权相等;(2)连续偏序集的权与其定向完备化的权相等;(3)无穷连续D om a in的权与其Sm yth幂D om a in的权相等;(4)有限D om a in的权小于或等于它的Sm yth幂D om a in的权。     

Joint extension of two theorems of Kotzig on 3-polytopes

The weight of an edge in a graph is the sum of the degrees of its end-vertices. It is proved that in each 3-polytope there exists either an edge of weight at most 13 for which both incident faces are triangles, or an edge of weight at most 10 which is incident with a triangle, or else an edge of weight at most 8. All the bounds 13, 10, and 8 are sharp and attained independently of each other.     

分维权重样条插值预测算法及应用

基于高维数据预测方法的应用,提出一种分维权重样条插值预测算法.通过高维数据的各维,建立样本各维数据与对应权重的网络结构关系,网络的结点个数与样本的个数无关.通过训练样本各维权重所满足的线性方程组得到各维的权值,再根据样本的各维数据值和所得到的对应权值进行三次样条插值,得到各维数据值的权值函数,而不是传统方法的常数,这克服了个别数据变化所带来的整体度量值发生较大变化的缺点.数值仿真实验表明:分维权重样条插值预测算法不失是一种稳定而灵活的算法,而且预测的精度较高,可以根据样条插值函数得到样本各维的权值.     

Optimal layout of cantilever trusses

For given allowable stress, Michell (Ref. 1) has investigated the optimal design of a cantilever truss that is to transmit a given load to two given fixed points of support. Disregarding the weight of the connections between the bars, he found that the truss of minimum weight is a truss-like continuum with an infinity of joints, and with bars that are mostly of infinitesimal length. In the present paper, a finite number of joints is enforced by including in the structural weight, which is to be minimized, not only the weight of the bars but also the weight of their connections, which is assumed to be proportional to the number of joints. The concept of two adjoint trusses is introduced, each of which coincides with the Maxwell diagram of the other truss. Two adjoint trusses have the same weight, and an optimal truss is therefore self-adjoint. The optimal configurations of 6-joint and 11-joint cantilever trusses are discussed, and the range of the weight of the typical joint is determined for which the 6-joint truss is optimal.     

基于差分的等级依赖效用模型行为决策权重扩展(英文)

基于等级依赖期望效用模型(RDEU),提供了一个简单但有效的行为决策权重扩展.因结果序列具有直线增长趋势,介绍一种基于一阶差分的新权重,并证明其对拆分效应的有效性.差分权重和RDEU权重的凸组合构成最终决策权重命名为D'-RDEU权重,它不仅可继承RDEU的优点,也可克服RDEU的两个不足.特别是,它通过拆分获得随机优势,可从理论上解释拆分效应.也提供了连续形式的D'-RDEU模型,连续模型的存在证明D'-RDEU比D-RDEU更实用.     

Finiteness of circulant weighing matrices of fixed weight

Let n be a fixed positive integer. Every circulant weighing matrix of weight n arises from what we call an irreducible orthogonal family of weight n. We show that the number of irreducible orthogonal families of weight n is finite and thus obtain a finite algorithm for classifying all circulant weighing matrices of weight n. We also show that, for every odd prime power q, there are at most finitely many proper circulant weighing matrices of weight q.     

Classification of Irreducible Weight Modules with a Finite-dimensional Weight Space over Twisted Heisenberg-Virasoro Algebra

We show that the support of an irreducible weight module over the twisted Heisenberg-Virasoro algebra, which has an infinite-dimensional weight space, coincides with the weight lattice and that all nontrivial weight spaces of such a module are infinite dimensional. As a corollary, we obtain that every irreducible weight module over the twisted Heisenber-Virasoro algebra, having a nontrivial finite-dimensional weight space, is a Harish-Chandra module （and hence is either an irreducible highest or lowest weight module or an irreducible module from the intermediate series）.     

山西省高速公路计重收费标准仿真研究

顺应全国统一治理公路非法超载超限运输的形势,结合山西省特点,确定适应山西省开放式干线公路计重收费的费率标准.建立开放式公路计重收费数学模型,通过Excel设置控件进行动态仿真,并对数学模型进行实证分析.     

城市可持续发展评价体系中指标群组赋权方法研究

在指标赋权的各种方法中,AHP法运用最为广泛,为使各指标权数更具客观性,往往采用群组决策的形式进行判断矩阵的构建。文中以各专家给出的判断矩阵为基础,利用统计分析法进行专家的选择,利用模糊聚类分析原理对专家进行分类、赋权,利用指标序列进行指标增减时的权数修正。最后,以“城市可持续指数”中“城市环境质量”评价为例．对其各指标加以赋权,详细探讨该方法的实施过程。     

Partially dynamic maintenance of minimum weight hyperpaths

We address the problem of dynamically maintaining minimum weight hyperpaths in a directed hypergraph in a decremental setting. For such a problem, we provide a new efficient algorithm that works for a wide class of hyperpath weight measures. This algorithm explicitly updates minimum weight hyperpaths in

Full-size image

worst case time under a sequence of L hyperarc weight increments and hyperarc deletions, where C is the maximum weight of minimum hyperpaths in and is the size of the representation of the hypergraph. Hyperpath weight measures are only required to belong to the class of strict weakly superior functions.