41027997
Graph bandwidth of weighted caterpillars
Graph bandwidth minimization (GBM) is a classical and challenging problem in graph algorithms and combinatorial optimization. Most of existing researches on this problem have focused on unweighted graphs. In this paper, we study the bandwidth minimization problem of weighted caterpillars, and propose several algorithms for solving various types of caterpillars and general graphs. More specifically, we show that the GBM problem on caterpillars with hair-length at most 2 and the GBM problem on star-shape caterpillars are NP-complete, and give a lower bound of the graph bandwidth for general weighted graphs. For caterpillars with hair-length at most 1, we present an O(n log n log(nwmax))-time algorithm to compute an optimal bandwidth layout, where n is the total number of vertices in the graph and wmax is the maximum wedge weight. For caterpillars with hair-length at most k, we give a k-approximation algorithm. For arbitrary caterpillars and general graphs, we give a heuristic algorithm and some experimental results. Experiments show that the solutions obtained by our heuristic algorithm are roughly within a factor of clog(n) of the lower bound for a small number c, which is consistent with the inapproximability results of this problem (i.e., no constant approximation for the GBM problem unless P = NP).
14297439
Geometric permutations of high dimensional spheres
We prove the maximum number of geometric permutations, induced by line transversals to a set of <i>n</i> pairwise disjoint congruent spheres in <i>R<sup>d</sup></i> with <i>d</i> ⪈ 3, is no more than 4 when <i>n</i> is sufficiently large, achieving the best known upper bound for this problem. We also prove the maximum number of geometric permutations of a set of <i>n</i> noncongruent spheres of bounded radius ratio in R<sup>d</sup>, <i>d</i> ⪈ 3, is at most 2<sup>[√2<i>M</i>]+1</sup>, where <i>M</i> is the ratio or the largest radius and the smallest radius. Our result settles a conjecture in combinatorial geometry.
29728094
Graph Bandwidth of Weighted Caterpillars
Graph bandwidth minimization (GBM) is a classical and challenging problem in graph algorithms and combinatorial optimization. Most of existing researches on this problem have focused on unweighted graphs. In this paper, we study the bandwidth minimization problem of weighted caterpillars, and propose several algorithms for solving various types of caterpillars and general graphs. More specifically, we show that the GBM problem on caterpillars with hair-length at most 2 and the GBM problem on star-shape caterpillars are NP-complete, and give a lower bound of the graph bandwidth for general weighted graphs. For caterpillars with hair-length at most 1, we present an O(n log n log(nwmax))-time algorithm to compute an optimal bandwidth layout, where n is the total number of vertices in the graph and wmax is the maximum wedge weight. For caterpillars with hair-length at most k, we give a k-approximation algorithm. For arbitrary caterpillars and general graphs, we give a heuristic algorithm and some experimental results. Experiments show that the solutions obtained by our heuristic algorithm are roughly within a factor of c log(n) of the lower bound for a small number c, which is consistent with the inapproximability results of this problem (i.e., no constant approximation for the GBM problem unless P = NP). © 2006 Published by Elsevier B.V.
21098955
Topological Peeling and Implementation
We present a new approach, called topological peeling, and its implementation for traversing a portion AR of the arrangement formed by n lines within a convex region R on the plane. Topological peeling visits the cells of AR in a fashion of propagating a "wave" of a special shape (called a double-wriggle curve) starting at a single source point. This special traversal fashion enables us to solve several problems (e.g., computing shortest paths) on planar arrangements to which previously best known arrangement traversal techniques such as topological sweep and topological walkm ay not be directly applicable. Our topological peeling algorithm takes O(K + n log(n + r)) time and O(n + r) space, where K is the number of cells in AR and r is the number of boundary vertices of R. Comparing with topological walk, topological peeling uses a simpler and more efficient way to sweep different types of lines, and relies heavily on exploring small local structures, rather than a much larger global structure. Experiments show that, on average, topological peeling outperforms topological walkb y 10 - 15% in execution time.
28240465
Motion Tracking and Intensity Surface Recovery in Microscopic Nuclear Images
Current techniques for microscopic imaging do not provide necessary spatial and temporal resolutions for real time visualization of the nucleus. Images can only be acquired in time lapse mode, leading to significant loss of information between image frames. Such data, if available, can be extremely helpful in the study of nuclear organization and function. In this paper, we present a gamut of geometric-technique-based approaches for solving the problem. Our techniques, working together, can effectively recover complicated motion and deformation as well as the change of intensity surfaces from pairs of images in a microscopic image sequence, and has low time complexity, particularly desirable by many biological applications where large amount of DNA need to be processed. These techniques are also readily applicable to other types of images for reconstructing motion and intensity surfaces of deformable objects.
6260724
Finding an optimal path without growing the tree
For problems on computing an optimal path as well as its length in a certain setting, the "standard" approach for finding an actual optimal path is by building (or "growing") a single-source optimal path tree. In this paper, we study a class of optimal path problems with the following phenomenon: The space complexity of the algorithms for reporting the lengths of single-source optimal paths for these problems is asymptotically smaller than the space complexity of the "standard" tree-growing algorithms for finding actual optimal paths. We present a general and efficient algorithmic paradigm for finding an actual optimal path for such problems without having to grow a single-source optimal path tree. Our paradigm is based on the "marriage-before-conquer" strategy, the prune-and-search technique, and a new data structure called clipped trees. The paradigm enables us to compute an actual path for a number of optimal path problems and dynamic programming problems in computational geometry, graph theory, and combinatorial optimization. Our algorithmic solutions improve the space bounds (in certain cases, the time bounds as well) of the previously best known algorithms, and settle some open problems. Our techniques are likely to be applicable to other problems.
17405074
Extracting Meaningful Entities from Police Narrative Reports
Valuable criminal-justice data in free texts such as police narrative reports are currently difficult to be accessed and used by intelligence investigators in crime analyses. It would be desirable to automatically identify from text reports meaningful entities, such as person names, addresses, narcotic drugs, or vehicle names to facilitate crime investigation. In this paper, we report our work on a neural network-based entity extractor, which applies named-entity extraction techniques to identify useful entities from police narrative reports. Preliminary evaluation results demonstrated that our approach is feasible and has some potential values for real-life applications. Our system achieved encouraging precision and recall rates for person names and narcotic drugs, but did not perform well for addresses and personal properties. Our future work includes conducting larger-scale evaluation studies and enhancing the system to capture human knowledge interactively.
12832200
A unified proof of minimum time complexity for reaching consensus and uniform consensus - an oracle-based approach
In this paper, we offer new proofs to two lower bound results in distributed computing: a minimum of f+1 and f+2 rounds for reaching consensus and uniform consensus respectively when at most f fail-stop faults can happen. Here the computation model is synchronous message passing. Both proofs are based on a novel oracle argument. These two induction proofs are unified in the following sense: the induction steps are the same and only the initial step (f=0) needs to be proved separately. The techniques used in the proof offer new insights into the lower bound results in distributed computing.
19232033
Protein Threading by Linear Programming: Theoretical Analysis and Computational Results
In a previous paper (Xu, Li, Kim, and Xu, Journal of Bioinformatics and Computational Biology, vol. 1, no. 1, pp. 95–117, 2003), we have used an integer programming approach to implement a protein threading program RAPTOR for protein 3D structure prediction, based on the threading model treating pairwise contacts rigorously and allowing variable gaps. We have solved the integer program by the canonical branch-and-bound method. In this paper we present a branch-and-cut method, a careful theoretical analysis of our formulation and why our approach is so effective. The result of cutting plane analysis is that two types of well-known cuts for this problem are already implied in the constraint set, which provides us some intuition that our formulation would be very effective. Experimental results show that for about 99 percent of real threading instances, the linear relaxations of their integer programs solve to integral optimal solutions directly. For the rest one percent of real instances, the integral solutions can be obtained with only several branch nodes. Experimental results also show that no special template or sequence features result in more possibilities of fractional solutions. This indicates that extra effort to seek for cutting planes to strengthen the existing formulation is unnecessary.
11266138
Proxy cache management for fine-grained scalable video streaming
Caching video objects at proxies close to clients has attracted a lot of attention in recent years. To meet diverse client bandwidth conditions, there have been research efforts to combine proxy caching with video layering or transcoding. Nevertheless, these adaptive systems suffer from either coarse adaptation granularity due to the inflexible structures of existing layered coders or high computation overhead due to the transcoding operations. In this paper, we propose a novel adaptive video caching framework that enables low-cost and fine-grained adaptation. The innovative approach employs the MPEG-4 fine-grained scalable (FGS) video with postencoding rate control. We demonstrate that the proposed framework is both network aware and media adaptive: clients can be of heterogeneous streaming rates, and the backbone bandwidth consumption can be adaptively controlled. We also examine the design and management issues in the framework, in particular, the optimal stream portions to cache and the optimal streaming rate to each client. Simulation results demonstrate that, compared to nonadaptive caching, the proposed framework with optimal cache management not only achieves significant reduction on transmission costs but also enables flexible utility assignment for the heterogeneous clients. Meanwhile, its computational overhead is kept at a low level, implying that it is practically deployable
7186877
On replica placement for QoS-aware content distribution
The rapid growth of time-critical information services and business-oriented applications is making quality of service (QoS) support increasingly important in content distribution. This paper investigates the problem of placing object replicas (e.g., web pages and images) to meet the QoS requirements of clients with the objective of minimizing the replication cost. We consider two classes of service models: replica-aware service and replica-blind service. In the replica-aware model, the servers are aware of the locations of replicas and can therefore direct requests to the nearest replica. We show that the QoS-aware placement problem for replica-aware services is NP-complete. Several heuristic algorithms for efficient computation of suboptimal solutions are proposed and experimentally evaluated. In the replica-blind model, the servers are not aware of the locations of replicas or even their existence. As a result, each replica only serves the requests flowing through it under some given routing strategy. We show that there exist polynomial optimal solutions to the QoS-aware placement problem for replica-blind services. Efficient algorithms are proposed to compute the optimal locations of replicas under different cost models.