排名聚合算法在少量长列表聚合中的性能比较分析

排名聚合将多个排名列表聚合成一个综合排名列表,可应用于推荐系统、链路预测、元搜索、提案评选等.当前已有工作从不同角度对不同排名聚合算法进行了综述、比较,但存在算法种类较少、数据统计特性不清晰、评价指标不够合理等局限性.不同排名聚合算法在提出时均声称优于已有算法,但是用于比较的方法不同,测试的数据不同,应用的场景不同,因此何种算法最能适应某一任务在很多情况下仍不甚清楚.本文基于Mallows模型,提出一套生成统计特性可控的不同类型的排名列表的算法,使用一个可应用于不同类型排名列表的通用评价指标,介绍9种排名聚合算法以及它们在聚合少量长列表时的表现.结果发现启发式方法虽然简单,但是在排名列表相似度较高、列表相对简单的情况下,能够接近甚至超过一些优化类方法的结果;列表中平局数量的增长会降低聚合排名的一致性并增加波动;列表数量的增加对聚合效果的影响呈现非单调性.整体而言,基于距离优化的分支定界方法 (FAST)优于其他各类算法,在不同类型的排名列表中表现非常稳定,能够很好地完成少量长列表的排名聚合.     

单链表在离子发动机光学系统粒子模拟中的应用

 目前离子发动机光学系统数值模拟大多采用PIC方法，由于该方法需要跟踪单个粒子的运动，因此需要存储每个粒子的位置信息与运动信息。传统的粒子模拟程序中，保存粒子信息大多采用数组的方式，但是采用这种方式存在弊端，例如对粒子总数变化的自适应不好。基于此开发了一种使用链式存储结构的粒子模拟程序，该程序使用带头节点的单向链表存储粒子信息。使用基于链式存储结构的PIC方法对离子发动机光学系统进行了粒子模拟，验证了链式粒子信息存储方法在粒子模拟中的可用性。模拟表明：（1）在粒子模拟中采用链式存储结构存储粒子信息，无需预先指定最大粒子总数，程序可自适应粒子总数的变化，因此无需进行试算，节省了计算时间；（2）在粒子模拟中采用链式存储结构，由于不存在内存资源的浪费，因而可显著提高程序的存储效率与计算效率。     

θ*r,s,t-图与唯一2-列表染色图的特征化

如果一个图G存在一个k-列表安排使得G具有一个唯一列表染色,则称 G是唯一列表可染色图,简称UkLC图．我们称图G具有M(k)性质当且仅当G不 是UkLC图．本文在借鉴θr,s,t-图概念的基础上引入θr,s,t-图的定义,并证明:除了 r=s=t=2以外,θr,s,t-图都是U2LC图．利用如上结果我们给出M．Mahdian and E．S．Mahmoodian对U2LC图所作特征化的一个简单证明．     

胺、醇、醚类化合物电离能的自相关拓扑研究

原子的染色序数 fi 定义为 :fi=gi·xi,式中 gi 为原子i在分子中的序数 ,xi 为其染色系数 .基于fi 建立改进的原子序数自相关拓扑指数mF ,其中的1F对烷烃及其衍生物具有良好的结构选择性 .使用第一电离能 (Ip)与0 F ,1F的数量关系模型对 32种脂肪族胺、醇、醚进行估算、预测 ,结果令人满意     

Analysis of Early Medieval Glass Beads – The Raw Materials to Produce Green, Orange and Brown Colours

 Monochrome coloured glass beads of the Merovingians (5^th–7^th cent. AD) have been examined by different analytical methods. The elemental composition of a large number of mostly unprepared beads have been measured non-destructively by X-ray fluorescence analysis. After subtracting the content of the colouring oxides of the glass beads and normalising the residual values to 100% an identical soda-lime-glass matrix was obtained. X-ray diffraction was used for the identification of the crystalline colouring and opacifying pigments (SnO₂, Cu, Cu₂O, PbSnO₃), and scanning electron microscopy as well as electron probe microanalysis were applied to study the microstructure and the composition of white, brown, green, orange and yellow coloured glass beads. Oxidised metals, alloys (lead, copper, bronze, brass and mixtures of them) and iron smelting slag have been identified as raw materials to colour the soda-lime-glass.     

Colourings of cubic graphs inducing isomorphic monochromatic subgraphs

A -bisection of a bridgeless cubic graph is a -colouring of its vertex set such that the colour classes have the same cardinality and all connected components in the two subgraphs induced by the colour classes ( monochromatic components in what follows) have order at most . Ban and Linial Conjectured that every bridgeless cubic graph admits a -bisection except for the Petersen graph. A similar problem for the edge set of cubic graphs has been studied: Wormald conjectured that every cubic graph with has a -edge colouring such that the two monochromatic subgraphs are isomorphic linear forests (ie, a forest whose components are paths). Finally, Ando conjectured that every cubic graph admits a bisection such that the two induced monochromatic subgraphs are isomorphic. In this paper, we provide evidence of a strong relation of the conjectures of Ban-Linial and Wormald with Ando's Conjecture. Furthermore, we also give computational and theoretical evidence in their support. As a result, we pose some open problems stronger than the above-mentioned conjectures. Moreover, we prove Ban-Linial's Conjecture for cubic-cycle permutation graphs. As a by-product of studying -edge colourings of cubic graphs having linear forests as monochromatic components, we also give a negative answer to a problem posed by Jackson and Wormald about certain decompositions of cubic graphs into linear forests.     

Asymptotically optimal neighbour sum distinguishing colourings of graphs

Consider a simple graph G = (V,E) and its proper edge colouring c with the elements of the set {1,2,…,k}. The colouring c is said to be neighbour sum distinguishing if for every pair of vertices u, v adjacent in G, the sum of colours of the edges incident with u is distinct from the corresponding sum for v. The smallest integer k for which such colouring exists is known as the neighbour sum distinguishing index of a graph and denoted by . The definition of this parameter, which makes sense for graphs containing no isolated edges, immediately implies that , where Δ is the maximum degree of G. On the other hand, it was conjectured by Flandrin et al. that for all those graphs, except for C₅. We prove this bound to be asymptotically correct by showing that . The main idea of our argument relays on a random assignment of the colours, where the choice for every edge is biased by so called attractors, randomly assigned to the vertices. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 776–791, 2015     

两台恒速机上的MapReduce排序算法研究

研究源自于MapReduce系统的一类排序问题。给定两台恒速机和一组按列表到达的工件，每个工件包含两类任务：Map Task和Reduce Task。假设Map任务和Reduce任务都是不可中断的，Map任务可以并行处理，即可以任意分割成若干小的任务并在两台机器上同时处理，而Reduce任务只可以在单台机器上处理。一旦工件到达，必须为其指派机器和开工时间，目标是使得最后完工时间最小。对LSc算法的竞争比进行了分析，得到其一般情形下的竞争比当$s\geq（1+\sqrt{5}）/2$时为$1+1/s$，否则为$1+s/（s+1）$。而当每个工件$J_j$都满足其Map任务总长大于等于Reduce任务总长时，其竞争比当$s\geq（1+\sqrt{3}）/2$时不超过$1+1/（2s）$，否则为不超过$1+s/（2s+1）$。