Path Hitting in Acyclic Graphs

An instance of the path hitting problem consists of two families of paths, and ℋ, in a common undirected graph, where each path in ℋ is associated with a non-negative cost. We refer to and ℋ as the sets of demand and hitting paths, respectively. When p∈ℋ and share at least one mutual edge, we say that p hits q. The objective is to find a minimum cost subset of ℋ whose members collectively hit those of . In this paper we provide constant factor approximation algorithms for path hitting, confined to instances in which the underlying graph is a tree, a spider, or a star. Although such restricted settings may appear to be very simple, we demonstrate that they still capture some of the most basic covering problems in graphs. Our approach combines several novel ideas: We extend the algorithm of Garg, Vazirani and Yannakakis (Algorithmica, 18:3–20, 1997) for approximate multicuts and multicommodity flows in trees to prove new integrality properties; we present a reduction that involves multiple calls to this extended algorithm; and we introduce a polynomial-time solvable variant of the edge cover problem, which may be of independent interest. An extended abstract of this paper appeared in Proceedings of the 14th Annual European Symposium on Algorithms, 2006. This work is part of D. Segev’s Ph.D. thesis prepared at Tel-Aviv University under the supervision of Prof. Refael Hassin.     

Approximation algorithms for partially covering with edges

The edge dominating set (EDS) and edge-cover (EC) problems are classical graph covering problems in which one seeks a minimum cost collection of edges which covers the edges or vertices, respectively, of a graph. We consider the generalized partial cover version of these problems, in which failing to cover an edge, in the EDS case, or vertex, in the EC case, induces a penalty. Given a bound on the total amount of penalties that we are permitted to pay, the objective is to find a minimum cost cover with respect to this bound. We give an 8/3-approximation for generalized partial EDS. This result matches the best-known guarantee for the {0,1}-EDS problem, a specialization in which only a specified set of edges need to be covered. Moreover, 8/3 corresponds to the integrality gap of the natural formulation of the {0,1}-EDS problem. Our techniques can also be used to derive an approximation scheme for the generalized partial edge-cover problem, which is -complete even though the uniform penalty version of the partial edge-cover problem is in .     

随机图点覆盖1度顶点核化算法分析

将随机图引入参数计算领域,利用随机图统计和概率分布等特性,从全局和整体上研究参数化点覆盖问题1度点核化过程中问题的核及度分布演变的内在机制和变化规律,并得出关于随机图1度点核化强度与顶点平均度关系及随机图点覆盖问题的决策与度分布关系的两个重要推论.最后分别从MIPS和BIND提取数据进行1度核化实验和分析.初步结果表明,对随机图点覆盖问题的分析方法不仅具有理论上的意义,而且随着问题随机度的大小而对问题有不同程度的把握能力.     

基于C5.0决策树算法的西北干旱区土地覆盖分类研究——以甘肃省武威市为例

西北干旱区面积广阔,由于土地利用类型多样,成因复杂,对环境变化敏感、变化过程快、幅度大、景观差异明显等特点,在影像上表现出的“同物异谱”现象明显 |利用常规目视解译、监督非监督分类、人工参与的决策树分类等方法在效率或精度等方面各有其缺陷。采用机器学习C5.0决策树算法,综合利用地物波谱、NDVI、TC、纹理等信息,根据样本数据自动挖掘分类规则并对整个研究区进行地物分类。机器学习的决策树可以挖掘出更多的分类规则,C5.0算法对采样数据的分布没有要求,可以处理离散和连续数据,生成的规则易于理解,分类精度高,可以满足西北干旱区大面积的土地利用/覆被变化制图的需要。     

Set Cover和Hitting Set问题的研究进展

Set Cover和Hitting Set问题是两个重要的W[2]完全问题。Set Cover问题在大规模集成电路设备的测试和人员调度等领域有着广泛的应用,Hitting Set问题在生物计算等领域有着重要的应用。在引入参数计算和复杂性理论后,Set Cover和Hitting Set问题再次成为研究的热点。首先介绍Set Cover和Hitting Set的各种分类问题及其定义,并对各种分类问题的计算复杂性和相关算法的研究进展加以分析总结,给出(k,h)-Set Cover和(k,d)-Set Cover问题的复杂性证明。最后总结全文并提出进一步研究的方向。     

钢架网+玻璃幕墙=米斯·凡德罗

本文通过对现代主义建筑大师米斯·凡德罗,在现代主义顶峰时期,代表时代建筑特色的建筑和建筑思想文脉的分析,找到确立米斯·凡德罗钢架网+玻璃幕墙建筑形式的来源思想,使我们清晰地了解现代主义的来源和发展,及现代主义在建筑中的体现方式。     

利用植被覆盖度-地表温度特征空间提取厦门市土壤湿度信息

土壤湿度是水文学、气象学以及农业科学研究领域的一个重要参数。利用1989年和1996年两个时相Landsat TM遥感卫星影像来获取厦门的植被覆盖度和地表温度,并由此构建了植被覆盖度和地表温度组成的特征空间,最后利用该特征空间反演了土壤湿度,并分析湿度在两个时相中的变化情况。结果显示,在所研究的时间段内,厦门西南老城区的湿度得到增加。但是在东北部城市建成区扩展的地区,土壤湿度则明显降低。     

基于CHI值特征选取和覆盖的文本分类方法

利用CHI值特征选取和前向神经网络的覆盖算法,通过对文本进行分词的预处理后,实现文本的自动分类。该方法利用CHI值进行特征选取即特征降维,应用覆盖算法进行文本分类。该方法将CHI值特征选取和覆盖算法充分结合,在提高了分类速度的同时还保证了分类的准确度。应用该方法对标准数据集中的文本进行实验,并在不同的维数上与SVM算法、朴素贝叶斯方法的实验结果进行了比较。结果表明,与SVM算法和朴素贝叶斯方法相比较,覆盖算法在准确度上更好。并且,维数的选择对分类的精确度影响很大。     

基于高光谱激光雷达的滞尘叶片光谱特征分析

城市绿植为城市生态系统提供自净功能, 起到净化空气以及滞尘降尘等多种环境保护作用, 而滞尘等因素也 会对绿植产生影响。为了研究滞尘对城市绿植叶片光谱特征的影响, 采集了四种常绿绿植 (八角金盘、石楠、香樟和 玉兰) 叶片样本, 使用高光谱激光雷达系统获取高光谱点云数据, 分析了滞尘对叶片光谱特征的影响。分析结果表明: 对于不同种类叶片, 滞尘对可见光波段反射率均有较大影响; 对于同种类叶片, 滞尘对近红外波段的反射率差异影响 较大, 可见光波段的反射率差异为 1.21%∼3.41%, 近红外为 1.76%∼8.49%; 线性四点内插法计算和光谱导数分析表明 滞尘对四种叶片的红边位置无显著影响; 四种叶片的叶面水含量指数 (LWI) 对滞尘的响应程度最小 (均小于 3.7%), 而 比值植被指数 (RVI) 对滞尘的响应程度最大 (除香樟外, 均大于 20.0%), 红边指数 (SDr)、简单比值指数 (SR) 和叶面叶 绿素指数 (LCI) 的响应程度稳定性较差。进一步建立了滞尘植被指数和响应程度的线性相关性拟合模型并进行了检 验, 其中以 LCI 为自变量建立的模型为最稳定拟合模型, 可表示为 y = −1.527x + 0.6597, 决定系数约为 0.88。     

终端近场通信天线研究北大核心CSCD

近场通信(NFC)已成为无线终端的标配功能,工作范围小、抗干扰性和安全性较高的特性使其被广泛应用于终端的移动支付和虚拟卡片等领域。由于近场天线产生的感应磁场会在临近的金属上耦合出反向涡流,并且金属屏蔽物覆盖会降低收发天线间的磁场耦合,紧凑终端中的电池、主板、外壳等金属元件将大幅影响NFC天线性能。本文从近场通信的历史、标准、系统结构出发,以终端NFC天线工作环境中的金属覆盖情况作为分类依据,对终端近场通信天线的研究进展进行了简要介绍。