Steiner trees in uniformly quasi-bipartite graphs

The area of approximation algorithms for the Steiner tree problem in graphs has seen continuous progress over the last years. Currently the best approximation algorithm has a performance ratio of 1.550. This is still far away from 1.0074, the largest known lower bound on the achievable performance ratio. As all instances resulting from known lower bound reductions are uniformly quasi-bipartite, it is interesting whether this special case can be approximated better than the general case. We present an approximation algorithm with performance ratio 73/60<1.217 for the uniformly quasi-bipartite case. This improves on the previously known ratio of 1.279 of Robins and Zelikovsky. We use a new method of analysis that combines ideas from the greedy algorithm for set cover with a matroid-style exchange argument to model the connectivity constraint. As a consequence, we are able to provide a tight instance.     

Approximation algorithm for constructing data aggregation trees for wireless sensor networks

This paper considers the problem of constructing data aggregation trees in wireless sensor networks (WSNs) for a group of sensor nodes to send collected information to a single sink node. The data aggregation tree contains the sink node, all the source nodes, and some other non-source nodes. Our goal of constructing such a data aggregation tree is to minimize the number of non-source nodes to be included in the tree so as to save energies. We prove that the data aggregation tree problem is NP-hard and then propose an approximation algorithm with a performance ratio of four and a greedy algorithm. We also give a distributed version of the approximation algorithm. Extensive simulations are performed to study the performance of the proposed algorithms. The results show that the proposed algorithms can find a tree of a good approximation to the optimal tree and has a high degree of scalability.     

Approximation algorithm for constructing data aggregation trees for wireless sensor networks

This paper considers the problem of constructing data aggregation trees in wireless sensor networks (WSNs) for a group of sensor nodes to send collected information to a single sink node. The data aggregation tree contains the sink node, all the source nodes, and some other non-source nodes. Our goal of constructing such a data aggregation tree is to minimize the number of non-source nodes to be included in the tree so as to save energies. We prove that the data aggregation tree problem is NP-hard and then propose an approximation algorithm with a performance ratio of four and a greedy algorithm. We also give a distributed version of the approximation algorithm. Extensive simulations are performed to study the performance of the proposed algorithms. The results show that the proposed algorithms can find a tree of a good approximation to the optimal tree and has a high degree of scalability.     

Overlapping community detection in labeled graphs

We present a new approach for the problem of finding overlapping communities in graphs and social networks. Our approach consists of a novel problem definition and three accompanying algorithms. We are particularly interested in graphs that have labels on their vertices, although our methods are also applicable to graphs with no labels. Our goal is to find k communities so that the total edge density over all k communities is maximized. In the case of labeled graphs, we require that each community is succinctly described by a set of labels. This requirement provides a better understanding for the discovered communities. The proposed problem formulation leads to the discovery of vertex-overlapping and dense communities that cover as many graph edges as possible. We capture these properties with a simple objective function, which we solve by adapting efficient approximation algorithms for the generalized maximum-coverage problem and the densest-subgraph problem. Our proposed algorithm is a generic greedy scheme. We experiment with three variants of the scheme, obtained by varying the greedy step of finding a dense subgraph. We validate our algorithms by comparing with other state-of-the-art community-detection methods on a variety of performance measures. Our experiments confirm that our algorithms achieve results of high quality in terms of the reported measures, and are practical in terms of performance.     

Fault-tolerant design of wireless sensor networks with directional antennas

A tree structure is often used in wireless sensor networks to deliver sensor data to a sink node. Such a tree can be built using directional antennas as they offer considerable advantage over the omni-directional ones. A tree is adequate for data gathering from all sensor nodes if no node fails. We study the problem of enhancing the fault tolerance of a data gathering tree by adding additional links so that failure of a sensor or a pair of adjacent sensors would not disconnect the tree. We prove that the least-cost tree augmentation problem is NP-complete and provide approximation algorithms one for single node failure and the other for a pair of adjacent node failure, with performance bounds of two and four respectively.     

大图数据上顶点驱动的并行最小生成树算法

最小生成树(minimum spanning tree, MST)是图论中最为经典算法之一.基于MST结构的聚类、分类和最短路径查询等复杂图算法,在效率和结果质量方面均有显著提高.然而,随着互联网的迅猛发展,图数据规模也变得越来越大,包含千万甚至上亿个顶点的大图数据越发常见.因此,如何在大图数据上实现查询处理和数据挖掘算法已成为亟待解决的问题之一.除此之外,由于大图数据的动态性特征,如何动态地维护算法结果也势必成为最受关注的问题之一.针对目前集中式的最小生成树算法无法解决海量和动态图数据的问题,首先提出了分区Prim(partition Prim, PP)算法,基于此提出了顶点驱动的并行MST算法——PB(PP Boruvka)算法,并论证了PB算法的正确性.另外,基于MapReduce和BSP框架实现了PB算法.针对只删除动态图特征,提出了MST维护算法,以实现高效的增量计算.对提出的计算和维护算法进行了代价分析和比较.最后,使用真实和模拟数据集,验证了PB算法和维护算法的有效性、高效性和可扩展性.     

基于最小生成树的图数据库索引算法

对复杂数据进行图模式建模近几年越来越流行,因此,在查询执行的优化过程中图索引技术变得至关重要.研究了图模式的索引问题,并且提出了一种近似的索引方法,称为MSTA方法.MSTA方法利用最小生成树结构作为索引特征,依据最小生成树边序列的包含关系和基于最大公共子图的图距离度量,将最小生成树组织到一个称为MST树的索引结构中.MST树索引结构可以高效地支持多种查询,例如子图查询.MSTA方法具备高效的索引性能.在索引大小和索引建立时间方面,传统方法是MSTA方法的数十倍,甚至上百倍.MSTA方法虽然不能返回完整结果,但是可以返回经图距离度量排序最好的部分结果.     

2D Vector field approximation using linear neighborhoods

We present a vector field approximation for two-dimensional vector fields that preserves their topology and significantly reduces the memory footprint. This approximation is based on a segmentation. The flow within each segmentation region is approximated by an affine linear function. The implementation is driven by four aims: (1) the approximation preserves the original topology; (2) the maximal approximation error is below a user-defined threshold in all regions; (3) the number of regions is as small as possible; and (4) each point has the minimal approximation error. The generation of an optimal solution is computationally infeasible. We discuss this problem and provide a greedy strategy to efficiently compute a sensible segmentation that considers the four aims. Finally, we use the region-wise affine linear approximation to compute a simplified grid for the vector field.     

Distributed Algorithms for Constructing Approximate Minimum Spanning Trees in Wireless Sensor Networks

While there are distributed algorithms for the MST problem, these algorithms require relatively large number of messages and time; this makes these algorithms impractical for resource-constrained networks such as ad hoc wireless sensor networks. In such networks, a sensor has very limited power, and any algorithm needs to be simple, local, and energy efficient for being practical. Motivated by these considerations, we design and analyze a class of simple and local distributed algorithms called Nearest Neighbor Tree (NNT) algorithms for energy-efficient construction of MSTs in a wireless ad hoc setting. We assume that the nodes are uniformly distributed in a unit square and show provable bounds on the performance with respect to both the quality of the spanning tree produced and the energy needed to construct them. In particular, we show that NNT produces a close approximation to the MST, and they can be maintained dynamically with polylogarithmic number of rearrangements under node insertions/deletions. We also perform extensive simulations of our algorithms. We tested our algorithms on both uniformly random distributions of nodes, and on a realistic distributions of nodes in an urban setting. Simulations validate the theoretical results and show that the bounds are much better in practice.     

Steiner Tree问题的研究进展

Steiner树问题是经典的NP难解问题,在计算机网络布局、电路设计以及生物网络等领域都有很多应用。随着参数计算理论的发展,已经证明了无向图和有向图中的Steiner树问题都是固定参数可解的(FPT)。介绍了无向图和有向图中Steiner树问题的近似算法和参数算法,分析了一些特殊Steiner树问题的研究现状,还讨论了顶点加权Steiner树问题的研究进展。最后,提出了该问题的进一步研究方向。     

基于动态数据压缩的能量采集无线传感网络数据收集优化

针对能量采集无线传感网络（WSN）中的数据收集优化问题,考虑传感器节点能量采集的时空变化特性,提出一种基于节点动态采样速率和数据压缩的策略,以实现网络中采样数据总量的最大化。首先,提出一种根据节点的邻居信息决定其最优压缩策略的本地压缩算法,基于节点在数据汇聚树中的拓扑位置考虑其数据接收和转发能耗,逐渐增加其采样速率直到其总能耗到达采集能耗阈值。接着构造网络性能的全局优化问题并提出一种启发式的算法,通过迭代求解线性规划问题计算最优的采样速率和压缩策略。实验结果表明,与现有的自适应传感和压缩率选择方案相比,所提出的两种数据收集优化算法能够维持更加稳定的传感器节点电量水平并实现更高的网络性能。     

The Freeze-Tag Problem: How to Wake Up a Swarm of Robots

An optimization problem that naturally arises in the study of swarm robotics is the Freeze-Tag Problem (FTP) of how to awaken a set of "asleep" robots, by having an awakened robot move to their locations. Once a robot is awake, it can assist in awakening other slumbering robots. The objective is to have all robots awake as early as possible. While the FTP bears some resemblance to problems from areas in combinatorial optimization such as routing, broadcasting, scheduling, and covering, its algorithmic characteristics are surprisingly different. We consider both scenarios on graphs and in geometric environments. In graphs, robots sleep at vertices and there is a length function on the edges. Awake robots travel along edges, with time depending on edge length. For most scenarios, we consider the offline version of the problem, in which each awake robot knows the position of all other robots. We prove that the problem is NP-hard, even for the special case of star graphs. We also establish hardness of approximation, showing that it is NP-hard to obtain an approximation factor better than 5/3, even for graphs of bounded degree. These lower bounds are complemented with several positive algorithmic results, including: · We show that the natural greedy strategy on star graphs has a tight worst-case performance of 7/3 and give a polynomial-time approximation scheme (PTAS) for star graphs. · We give a simple O(log δ)-competitive online algorithm for graphs with maximum degree δ and locally bounded edge weights. · We give a PTAS, running in nearly linear time, for geometrically embedded instances.     

基于轨迹受限的移动Sink低能耗数据收集协议

无线传感器网络数据收集的能耗问题一直以来都是研究的热点。本文主要研究基于移动Sink轨迹受限的数据收集协议。首先针对轨迹受限的无线传感网络提出一种通用的系统模 型,将该问题形式化为最大化降低全网总路径长度轨迹设计问题 (Maximizing total length reduction for constrained trajectory, MTRC),并证明了MTRC为NP-Hard问题;然后设计一种轨迹约束低能耗贪心算法 (Trajectory constrain of low energy consumption, TCLEC),通过 TSP近似算法设计最大化降低有效长度的Sink移动轨迹。理论分析和仿真实验结果表明,TCLEC在网络拓扑数据收集树的初始化以及优化方面是高效的,并且相对于同类基于移动Sink的无线传感网络分层数据收集方法,其能耗降低了7%左右。     

WSN中面向数据收集的网络拓扑构造算法

针对现有无线传感器网络中数据收集延迟较大的问题,提出一种优化的网络拓扑构造算法用于实现数据收集。从给定网络全连通图中找到符合条件的k个顶点的子图,使得k个顶点间的距离平方和最小化,采用Hungarian方法进行边的约简,直到得到一棵生成树,构造分布式的网络拓扑以提高适应性,从而降低控制开销。理论分析和仿真结果表明,该算法在数据收集延迟以及网络生命周期等方面均优于传统的单链、单簇2跳,以及最小生成树等数据收集算法。     

基于堆的最小连通支配集高效近似算法

提出一种解决连通网络图上连通支配集(CDS)问题的贪心近似算法。利用堆结构逐步选出支配节点,将支配节点加入由之前已确定节点组成的树中,完成网络图中支配树的构造。通过计算堆操作次数,分析算法在平均情况下的时间复杂度。在随机网络模型上的模拟实验结果表明,与已有算法相比,该算法可以得到点数更少的连通支配集。     

最大简单共享问题的快速近似算法

介绍了一种基于复制结点的消除线路交叉的模型.该模型提出了一个优化问题,就是最小化结点复制的数量.同时提出一个自定义问题——"最大简单共享问题",并证明最小化结点复制的数量与最大共享问题是等价的.证明了最大简单共享问题是NP-hard的,给出了一种简单的贪心算法,并证明该贪心算法的近似度为3.引入一个"最大互斥简单共享问题",该问题是最大简单共享问题的2-近似.将其转化为在一系列图上的完美匹配问题,使该问题可以在多项式时间内得到完美解决.最后,在最大互斥简单共享的基础上,用局部搜索的方法将近似度提高到12/7.     

An efficient path computation model for hierarchically structured topographical road maps

In this paper, we have developed a HiTi (Hierarchical MulTi) graph model for structuring large topographical road maps to speed up the minimum cost route computation. The HiTi graph model provides a novel approach to abstracting and structuring a topographical road map in a hierarchical fashion. We propose a new shortest path algorithm named SPAH, which utilizes HiTi graph model of a topographical road map for its computation. We give the proof for the optimality of SPAH. Our performance analysis of SPAH on grid graphs showed that it significantly reduces the search space over existing methods. We also present an in-depth experimental analysis of HiTi graph method by comparing it with other similar works on grid graphs. Within the HiTi graph framework, we also propose a parallel shortest path algorithm named ISPAH. Experimental results show that inter query shortest path problem provides more opportunity for scalable parallelism than the intra query shortest path problem.     

Secure Data Objects Replication in Data Grid

Secret sharing and erasure coding-based approaches have been used in distributed storage systems to ensure the confidentiality, integrity, and availability of critical information. To achieve performance goals in data accesses, these data fragmentation approaches can be combined with dynamic replication. In this paper, we consider data partitioning (both secret sharing and erasure coding) and dynamic replication in data grids, in which security and data access performance are critical issues. More specifically, we investigate the problem of optimal allocation of sensitive data objects that are partitioned by using secret sharing scheme or erasure coding scheme and/or replicated. The grid topology we consider consists of two layers. In the upper layer, multiple clusters form a network topology that can be represented by a general graph. The topology within each cluster is represented by a tree graph. We decompose the share replica allocation problem into two subproblems: the Optimal Intercluster Resident Set Problem (OIRSP) that determines which clusters need share replicas and the Optimal Intracluster Share Allocation Problem (OISAP) that determines the number of share replicas needed in a cluster and their placements. We develop two heuristic algorithms for the two subproblems. Experimental studies show that the heuristic algorithms achieve good performance in reducing communication cost and are close to optimal solutions.     

Hardness and approximation of minimum maximal matchings

In this paper, we consider the minimum maximal matching problem in some classes of graphs such as regular graphs. We show that the minimum maximal matching problem is NP-hard even in regular bipartite graphs, and a polynomial time exact algorithm is given for almost complete regular bipartite graphs. From the approximation point of view, it is well known that any maximal matching guarantees the approximation ratio of 2 but surprisingly very few improvements have been obtained. In this paper we give improved approximation ratios for several classes of graphs. For example any algorithm is shown to guarantee an approximation ratio of (2-o(1)) in graphs with high average degree. We also propose an algorithm guaranteeing for any graph of maximum degree Δ an approximation ratio of (2?1/Δ), which slightly improves the best known results. In addition, we analyse a natural linear-time greedy algorithm guaranteeing a ratio of (2?23/18k) in k-regular graphs admitting a perfect matching.     

Optimizing regenerator cost in traffic grooming

In optical networks, regenerators have to be placed on lightpaths every d consecutive nodes in order to regenerate the signal. In addition, grooming enables the use of the same regenerator by several lightpaths. Up to g (the grooming factor) lightpaths can use the same regenerator. In this work we consider the problem of minimizing the number of regenerators used in traffic grooming in optical networks. Starting from the 4-approximation algorithm of Flammini et al. (2010) [10] for d=1 and a path topology, we provide an approximation algorithm with the same approximation ratio for d=1and the ring and tree topologies. We present also a technique based on matching that leads to the same approximation ratio in tree topology and can be used to obtain approximation algorithms in other topologies. We provide an approximation algorithm for general topology that uses this technique. Finally, all the results are extended to the case of general d.