Approximation and Exact Algorithms for Constructing Minimum Ultrametric Trees from Distance Matrices

An edge-weighted tree is called ultrametric if the distances from the root to all the leaves in the tree are equal. For an n by n distance matrix M, the minimum ultrametric tree for M is an ultrametric tree T = (V, E, w) with leaf set {1,..., n} such that d_T(i, j) M[i, j] for all i, j and is minimum, where d_T(i, j) is the distance between i and j on T. Constructing minimum ultrametric trees from distance matrices is an important problem in computational biology. In this paper, we examine its computational complexity and approximability. When the distances satisfy the triangle inequality, we show that the minimum ultrametric tree problem can be approximated in polynomial time with error ratio 1.5(1 + log n), where n is the number of species. We also develop an efficient branch-and-bound algorithm for constructing the minimum ultrametric tree for both metric and non-metric inputs. The experimental results show that it can find an optimal solution for 25 species within reasonable time, while, to the best of our knowledge, there is no report of algorithms solving the problem even for 12 species.     

A Novel Evolutionary Formulation of the Maximum Independent Set Problem

We introduce a novel evolutionary formulation of the problem of finding a maximum independent set of a graph. The new formulation is based on the relationship that exists between a graphs independence number and its acyclic orientations. It views such orientations as individuals and evolves them with the aid of evolutionary operators that are very heavily based on the structure of the graph and its acyclic orientations. The resulting heuristic has been tested on some of the Second DIMACS Implementation Challenge benchmark graphs, and has been found to be competitive when compared to several of the other heuristics that have also been tested on those graphs.     

Two Novel Evolutionary Formulations of the Graph Coloring Problem

We introduce two novel evolutionary formulations of the problem of coloring the nodes of a graph. The first formulation is based on the relationship that exists between a graph's chromatic number and its acyclic orientations. It views such orientations as individuals and evolves them with the aid of evolutionary operators that are very heavily based on the structure of the graph and its acyclic orientations. The second formulation, unlike the first one, does not tackle one graph at a time, but rather aims at evolving a program to color all graphs belonging to a class whose members all have the same number of nodes and other common attributes. The heuristics that result from these formulations have been tested on some of the Second DIMACS Implementation Challenge benchmark graphs, and have been found to be competitive when compared to the several other heuristics that have also been tested on those graphs.     

政府治理视角下平台电商信用监管的动态演化博弈研究

为破解不完全信息下平台电商的信用“监管困局”,本研究在平台电商、消费者与政府三元主体联动关系的基础上,分别构建政府动态惩罚机制与激励机制下平台电商与消费者的演化博弈模型,并分析平台电商与消费者之间策略选择的影响因素及演化路径。研究表明：在政府监管下,平台电商与消费者通过长期的反复博弈、调整的过程,最终博弈系统演化轨迹呈逐渐收敛的趋势。具体而言,政府动态惩罚机制下,当政府惩罚力度逐渐增加时,平台电商倾向于选择“自律”策略;政府动态激励机制下,当政府对平台电商的激励逐渐增加时,平台电商倾向于选择“自律”策略。更为重要的是,当政府的惩罚力度大于激励政策力度时,政府实施惩罚性政策但没有激励政策的效果要优于政府实施激励政策但不实施惩罚性政策的效果。而当政府的惩罚力度小于激励政策力度时,政府实施激励政策但不实施惩罚性政策的效果与政府实施惩罚性政策但没有激励政策的效果几乎接近。由此可见,政府应将惩罚机制与激励机制相结合适度监管,以此追求信用监管的动态平衡。另外,消费者对平台电商的声誉评价具有两面性：当消费者对平台电商声誉评价越高时,平台电商倾向于选择“自律”策略;而消费者对平台电商声誉评价越低,平台电商反而倾向于选择“不自律”策略。