Approximating Node Connectivity Problems via Set Covers

Given a graph (directed or undirected) with costs on the edges, and an integer $k$, we consider the problem of finding a $k$-node connected spanning subgraph of minimum cost. For the general instance of the problem (directed or undirected), there is a simple $2k$-approximation algorithm. Better algorithms are known for various ranges of $n,k$. For undirected graphs with metric costs Khuller and Raghavachari gave a $( 2+{2(k-1)}/{n})$-approximation algorithm. We obtain the following results: (i) For arbitrary costs, a $k$-approximation algorithm for undirected graphs and a $(k+1)$-approximation algorithm for directed graphs. (ii) For metric costs, a $(2+({k-1})/{n})$-approximation algorithm for undirected graphs and a $(2+{k}/{n})$-approximation algorithm for directed graphs. For undirected graphs and $k=6,7$, we further improve the approximation ratio from $k$ to $\lceil (k+1)/2 \rceil=4$; previously, $\lceil (k+1)/2 \rceil$-approximation algorithms were known only for $k \leq 5$. We also give a fast $3$-approximation algorithm for $k=4$. The multiroot problem generalizes the min-cost $k$-connected subgraph problem. In the multiroot problem, requirements $k_u$ for every node $u$ are given, and the aim is to find a minimum-cost subgraph that contains $\max\{k_u,k_v\}$ internally disjoint paths between every pair of nodes $u,v$. For the general instance of the problem, the best known algorithm has approximation ratio $2k$, where $k=\max k_u$. For metric costs there is a 3-approximation algorithm. We consider the case of metric costs, and, using our techniques, improve for $k \leq 7$ the approximation guarantee from $3$ to $2+{\lfloor (k-1)/2 \rfloor}/{k} < 2.5$.     

Satellite-Based Energy Balance for Mapping Evapotranspiration with Internalized Calibration (METRIC)—Applications

Recent satellite image processing developments have provided the means to calculate evapotranspiration (ET) as a residual of the surface energy balance to produce ET “maps.” These ET maps (i.e., images) provide the means to quantify ET on a field by field basis in terms of both the rate and spatial distribution. The ET images show a progression of ET during the year or growing season as well as its spatial distribution. The mapping evapotranspiration at high resolution with internalized calibration (METRIC) is a satellite-based image-processing procedure for calculating ET. METRIC has been applied with high resolution Landsat images in southern Idaho, southern California, and New Mexico to quantify monthly and seasonal ET for water rights accounting, operation of ground water models, and determination of crop coefficient populations and mean curves for common crops. Comparisons between ET by METRIC, ET measured by lysimeter, and ET predicted using traditional methods have been made on a daily and monthly basis for a variety of crop types and land uses. Error in estimated growing season ET was 4% for irrigated meadow in the Bear River basin of Idaho and 1% for an irrigated sugar beet crop near Kimberly, Id. Standard deviation of error for time periods represented by each satellite image averaged about 13 to 20% in both applications. The results indicate that METRIC and similar methods such as SEBAL hold substantial promise as efficient, accurate, and inexpensive procedures to estimate actual evaporation fluxes from irrigated lands throughout growing seasons.     

超分辨重建图像质量评价算法

超分辨率图像重建技术可以提高图像分辨率,但是通常会给图像带来相应的尺寸变化,如何评价质量提升是个难题。目前常用的图像质量评价算法很少涉及图像的尺寸变化。基于结构相似度（SSIM）和尺度空间理论（SIFT）,提出了一种针对超分辨率重建图像的弱参考质量评价算法,算法将SSIM与SIFT融合,能够适用图像尺寸的变化。通过仿真和实验证明了该算法的有效性。实验结果表明,该算法能够很好地适应图像尺寸的变化,可以客观地评价超分辨重建图像质量的好坏。     

On indexing metric spaces using cut-regions

After two decades of research, the techniques for efficient similarity search in metric spaces have combined virtually all the available tricks resulting in many structural index designs. As the representative state-of-the-art metric access methods (also called metric indexes) that vary in the usage of filtering rules and in structural designs, we could mention the M-tree, the M-Index and the List of Clusters, to name a few. In this paper, we present the concept of cut-regions that could heavily improve the performance of metric indexes that were originally designed to employ simple ball-regions. We show that the shape of cut-regions is far more compact than that of ball-regions, yet preserving simple and concise representation. We present three re-designed metric indexes originating from the above-mentioned ones but utilizing cut-regions instead of ball-regions. We show that cut-regions can be fully utilized in the index structure, positively affecting not only query processing but also the index construction. In the experiments we show that the re-designed metric indexes significantly outperform their original versions.     

A unified approach to pattern recognition

The paper is an outline of a new approach to pattern recognition developed by the author. A fuller introduction to the approach will appear soon.⁽¹⁾ Within the proposed framework the two principal approaches to pattern recognition—vector and syntactic—are unified.     

软件过程中的度量数据收集方法研究

度量数据收集在软件过程改善实践中起着重要作用,但是往往在研究中受到忽视。介绍了软件过程数据收集方法和技术的发展历程,提出了软件过程度量数据收集方法的评价准则,给出了一个软件过程度量数据自动收集的框架,并且列举了四种实现方法。     

一种基于概念格的软件过程改进算法

概念格是一种优良的形式化分析工具,其具有的层次性和直观性,使之广泛应用于人工智能、数据挖掘、知识提取等领域。软件过程改善是软件工业化生产的一个关键,将概念格引入到了软件过程改善研究,提出了一种基于概念格的软件过程改进方法,并做了实验分析,证明了采用此方法对软件过程的改进具有推动作用。