27008432
Traveling Salesman Problem of Segments
In this paper, we present a polynomial time approximation scheme (PTAS) for a variant of the traveling salesman problem (called segment TSP) in which a traveling salesman tour is sought to traverse a set of n Ɛ-separated segments in two dimensional space. Our results are based on a number of geometric observations and an interesting generalization of Arora's technique [5] for Euclidean TSP (of a set of points). The randomized version of our algorithm takes O(n2(log n)O(1/Ɛ4)) time to compute a (1 + Ɛ)-approximation with probability ≥ 1/2, and can be derandomized with an additional factor of O(n2). Our technique is likely applicable to TSP problems of certain Jordan arcs and related problems.
5727433
An Experimental Study and Comparison of Topological Peeling and Topological Walk
In this paper, we present an experimental study comparing two algorithms, topological peeling and topological walk, for traversing arrangements of planar lines. Given a set H of n lines and a convex region R on a plane, both topological peeling and topological walk sweep the portion AR of the arrangement of H inside R in O(K + n log(n + r)) time and O(n + r) space, where K is the number of cells of AR and r is the number of boundary vertices of R. In our study, we robustly implemented these two algorithms using the LEDA library. Based on the implementation, we carried out experiments to conduct several comparisons, such as the arrangement traversal fashions, memory consumption, and execution time. In general, topological peeling exhibits a better control on the propagation of its sweeping curve (called the wavefront). For memory consumption, two types of measures, logical and physical memory, were examined. Our experiments showed that although both algorithms use nearly the same amount of logical memory, topological peeling could use twice as much physical memory as topological walk. For execution time, experiments revealed an interesting phenomenon that topological peeling has a 10% to 25% faster execution time than topological walk in most cases. Our analysis of this phenomenon indicates that the execution times of topological peeling and topological walk are both sensitive to the ratio of the lower input lines to all input lines. When the ratio of the lower lines to all input lines is around 85%, the two algorithms have roughly the same amount of execution time. Under this ratio, topological peeling considerably outperforms topological walk; above this ratio, topological walk slightly outperforms topological peeling.
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.
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.
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.
42016450
Geometric permutations of higher dimensional spheres
In this paper, we prove that the maximum number of geometric permutations (induced by line transversals) of a set of n pairwise disjoint spheres with a bounded radius ratio in Rd for d ≥ 3 is at most 2⌊√2M⌋+1, where M is the ratio of the largest radius and the smallest radius of the spheres. Setting M to 1, this gives an upper bound of 4 on the maximum number of geometric permutations for congruent spheres in Rd, matching a recently independently discovered result [Y. Zhou, S. Suri, in: Proc. of 12th Annual ACM-SIAM Symp. on Discrete Algorithms, 2001, pp. 234-243] on this case. Our result settles a conjecture in combinatorial geometry.
240982
Data streaming algorithms for estimating entropy of network traffic
Using entropy of traffic distributions has been shown to aid a wide variety of network monitoring applications such as anomaly detection, clustering to reveal interesting patterns, and traffic classification. However, realizing this potential benefit in practice requires accurate algorithms that can operate on high-speed links, with low CPU and memory requirements. In this paper, we investigate the problem of estimating the entropy in a streaming computation model. We give lower bounds for this problem, showing that neither approximation nor randomization alone will let us compute the entropy efficiently. We present two algorithms for randomly approximating the entropy in a time and space efficient manner, applicable for use on very high speed (greater than OC-48) links. The first algorithm for entropy estimation is inspired by the structural similarity with the seminal work of Alon et al. for estimating frequency moments, and we provide strong theoretical guarantees on the error and resource usage. Our second algorithm utilizes the observation that the performance of the streaming algorithm can be enhanced by separating the high-frequency items (or elephants) from the low-frequency items (or mice). We evaluate our algorithms on traffic traces from different deployment scenarios.
16814075
On algebraic construction of Gallager and circulant low-density parity-check codes
This correspondence presents three algebraic methods for constructing low-density parity-check (LDPC) codes. These methods are based on the structural properties of finite geometries. The first method gives a class of Gallager codes and a class of complementary Gallager codes. The second method results in two classes of circulant-LDPC codes, one in cyclic form and the other in quasi-cyclic form. The third method is a two-step hybrid method. Codes in these classes have a wide range of rates and minimum distances, and they perform well with iterative decoding.
11532584
Sequentially t-Diagnosable Systems: A Characterization and Its Applications
In the system level fault diagnosis area, the fundamental problem of characterizing sequentially t-diagnosable systems in the PMC model has remained open for more than two decades. We resolve this problem by providing a complete characterization of such systems. Our solution to the characterization problem leads to the correct identification of optimal sequentially t-diagnosable D/sub /spl delta/,k/ systems. Given a set of n units where n=2t+1, an optimal D/sub /spl delta/,k/ system can be constructed with just n([(t+2)/3]) tests, rather than n([t/2]+1) tests-a previously misjudged bound. An efficient algorithm for identifying the set of faulty units in a sequentially t-diagnosable D/sub /spl delta/,k/ system is given along the line of the proposed characterization, which is linear with respect to the number of tests in the system. >
9432716
Coordinated exception handling in distributed object systems: from model to system implementation
Exception handling in concurrent and distributed programs is a difficult task though it is often necessary. In many cases traditional exception mechanisms for sequential programs are no longer appropriate. One major difficulty is that the process of handling an exception may need to involve multiple concurrent components that are cooperating in pursuit of some global goal. Another complication is that several exceptions may be raised concurrently in different nodes of a distributed environment. Existing proposals and actual concurrent languages either ignore these difficulties or only cope with a limited form of them. The paper attempts a general solution, developed especially for distributed object systems, starting from a conceptual model, together with algorithms for coordinating concurrent components and resolving multiple exceptions, through to an actual system implementation. An industrial production cell is chosen as a case study to demonstrate the usefulness of the proposed model and algorithms. A system that supports coordinated atomic actions and exception resolution is implemented in distributed Ada 95 and examined through several performance-related experiments.
13126291
Towards Portable Metrics-based Models for Software Maintenance Problems
The usage of software metrics for various purposes has become a hot research topic in academia and industry (e.g. detecting design patterns and bad smells, studying change-proneness, quality and maintainability, predicting faults). Most of these topics have one thing in common: they are all using some kind of metrics-based models to achieve their goal. Unfortunately, only few researchers have tested these models on unknown software systems so far. This paper tackles the question, which metrics are suitable for preparing portable models (which can be efficiently applied to unknown software systems). We have assessed several metrics on four large software systems and we found that the well-known RFC and WMC metrics differentiate the analyzed systems fairly well. Consequently, these metrics cannot be used to build portable models, while the CBO, LCOM and LOC metrics behave similarly on all systems, so they seem to be suitable for this purpose