On the complexity of bandwidth allocation in radio networks

We define and study an optimization problem that is motivated by bandwidth allocation in radio networks. Because radio transmissions are subject to interference constraints in radio networks, physical space is a common resource that the nodes have to share in such a way, that concurrent transmissions do not interfere. The bandwidth allocation problem we study under these constraints is the following. Given bandwidth (traffic) demands between the nodes of the network, the objective is to schedule the radio transmissions in such a way that the traffic demands are satisfied. The problem is similar to a multicommodity flow problem, where the capacity constraints are replaced by the more complex notion of non-interfering transmissions. We provide a formal specification of the problem that we call round weighting  . By modeling non-interfering radio transmissions as independent sets, we relate the complexity of round weighting to the complexity of various independent set problems (e.g. maximum weight independent set, vertex coloring, fractional coloring). From this relation, we deduce that in general, round weighting is hard to approximate within n^1−ε$n^{1-\epsilon }$ (n$n$ being the size of the radio network). We also provide polynomial (exact or approximation) algorithms e.g. in the following two cases: (a) when the interference constraints are specific (for instance for a network whose vertices belong to the Euclidean space), or (b) when the traffic demands are directed towards a unique node in the network (also called gathering, analogous to single commodity flow).     

Formulations and exact algorithms for the vehicle routing problem with time windows

In this paper we review the exact algorithms proposed in the last three decades for the solution of the vehicle routing problem with time windows (VRPTW). The exact algorithms for the VRPTW are in many aspects inherited from work on the traveling salesman problem (TSP). In recognition of this fact this paper is structured relative to four seminal papers concerning the formulation and exact solution of the TSP, i.e. the arc formulation, the arc-node formulation, the spanning tree formulation, and the path formulation. We give a detailed analysis of the formulations of the VRPTW and a review of the literature related to the different formulations. There are two main lines of development in relation to the exact algorithms for the VRPTW. One is concerned with the general decomposition approach and the solution to certain dual problems associated with the VRPTW. Another more recent direction is concerned with the analysis of the polyhedral structure of the VRPTW. We conclude by examining possible future lines of research in the area of the VRPTW.     

A two-stage hardware scheduler combining greedy and optimal scheduling

Greedy scheduling heuristics provide a low complexity and scalable albeit particularly sub-optimal strategy for hardware-based crossbar schedulers. In contrast, the maximum matching algorithm for Bipartite graphs can be used to provide optimal scheduling for crossbar-based interconnection networks with a significant complexity and scalability cost. In this paper, we show how maximum matching can be reformulated in terms of Boolean operations rather than the more traditional formulations. By leveraging the inherent parallelism available in custom hardware design, we reformulate maximum matching in terms of Boolean operations rather than matrix computations and introduce three maximum matching implementations in hardware. Specifically, we examine a Pure Logic Scheduler with three dimensions of parallelism, a Matrix Scheduler with two dimensions of parallelism and a Vector Scheduler with one dimension of parallelism. These designs reduce the algorithmic complexity for an N×N$N\times N$ network from O(N³)$O\left(N^3\right)$ to O(1)$O\left(1\right)$, O(K)$O\left(K\right)$, and O(KN)$O\left(KN\right)$, respectively, where K$K$ is the number of optimization steps. While an optimal scheduling algorithm requires K=2N−1$K=2N-1$ steps, by starting with our hardware-based greedy strategy to generate an initial schedule, our simulation results show that the maximum matching scheduler can achieve 99% of the optimal schedule when K=9$K=9$. We examine hardware and time complexity of these architectures for crossbar sizes of up to N=1024$N=1024$. Using FPGA synthesis results, we show that a greedy schedule for crossbars, ranging from 8×8 to 256×256, can be optimized in less than 20 ns per optimization step. For crossbars reaching 1024×1024 the scheduling can be completed in approximately 10 μs with current technology and could reach under 90 ns with future technologies.     

Region-Based Hierarchical Image Matching

This paper presents an approach to region-based hierarchical image matching, where, given two images, the goal is to identify the largest part in image 1 and its match in image 2 having the maximum similarity measure defined in terms of geometric and photometric properties of regions (e.g., area, boundary shape, and color), as well as region topology (e.g., recursive embedding of regions). To this end, each image is represented by a tree of recursively embedded regions, obtained by a multiscale segmentation algorithm. This allows us to pose image matching as the tree matching problem. To overcome imaging noise, one-to-one, many-to-one, and many-to-many node correspondences are allowed. The trees are first augmented with new nodes generated by merging adjacent sibling nodes, which produces directed acyclic graphs (DAGs). Then, transitive closures of the DAGs are constructed, and the tree matching problem reformulated as finding a bijection between the two transitive closures on DAGs, while preserving the connectivity and ancestor-descendant relationships of the original trees. The proposed approach is validated on real images showing similar objects, captured under different types of noise, including differences in lighting conditions, scales, or viewpoints, amidst limited occlusion and clutter.     

基于XWiki的科研协作管理支撑平台

针对传统科研活动环境中信息资源相对孤立、项目成员间协作性差、项目管理和协作过程复杂以及整体效率低下等问题,提出一种基于XWiki的科研协作管理支撑平台架构设计方案,并对其进行具体实现。该平台便于科研项目管理,实现了科研团体内部知识的高效共享,并提高了科研协作管理效率,有效推动了科研协作管理信息化进程。     

智能搜索算法求解最大团问题研究

最大团问题MCP（Maximum Clique Problem）在国外得到了广泛的研究,在国内刚起步,是一类NP完全问题。传统的确定性算法不能有效地进行求解。定义了MCP;介绍了使用启发式算法求解MCP的研究进展;综述了几种典型的智能搜索算法;分析了使用这些典型算法求解MCP的基本思想;研究了这些智能算法在求解MCP时的特点及性能。     

基于动态序列图像的汽车碰撞分析系统的实现

提出一种基于动态序列图像的汽车碰撞分析系统的实现方法,并就其中关键技术进行了讨论:引入基于大气物理模型的图像复原方法,消减天气对现场采集的图像质量的影响;提出了背景差分与时间差分融合的方法,实现对运动目标(车辆)的快速检测;利用编码技术实现对车身特定点的自动识别、匹配和跟踪;运用DLT算法进行摄像机标定,进行图像测量.本系统应用于碰撞过程的定性和定量分析,结果表明了其有效性.     

基于最大熵模型的中文名词短语识别

中文名词短语识别在自然语言处理已经得到了广泛应用。该文首先对名词短语识别问题进行描述,然后利用最大熵模型建立名词短语识别系统,通过实验选取最大熵模型的特征,最后利用选取的特征进行名词短语识别,实验结果表明系统达到了较高的准确率和召回率。     

基于模板引擎的XML模式与关系模式的相互映射

XML已迅速成为了Intemet数据描述和数据交换的标准,如何准确全面地实现XML模式与关系模式的相互映射转换已成了一个重要的研究课题,针对目前基于XML的数据交换问题,研究XML模式与关系模式的相互映射规则,提出利用Velocity模板引擎实现两者相互映射转换的方法,并通过例子说明其映射过程,而且在一定程度上保留了数据完整性。     

汉语名物化复合词识别

名物化复合词的识别是汉语复合词识别中的难点.困难之处在于汉语动词和名词共现时既可以构成动词短语也可以构成名物化复合词.传统的汉语复合词识别往往只使用语料统计特征,效果往往不怎么理想.基于最大熵模型,在基准上下文特征的基础上,采用了词汇特征与Web特征对动词和名词共现时的名物化候选进行判定,取得了较好的实验结果.其中,Precision达到了86.31%,Recall达到了70.00%.