9706723
Efficient Job Scheduling Algorithms with Multi-Type Contentions
In this paper, we consider an interesting generalization of the classic job scheduling problem in which each job needs to compete not only for machines but also for other types of resources. The contentions among jobs for machines and for resources could interfere with each other, which complicates the problem dramatically. We present a family of approximation algorithms for solving several variants of the problem by using a generic algorithmic framework. Our algorithms achieve a constant approximation ratio (i.e., 3) when there is only one type of resources or certain dependency relation exists among multiple types of resources. When the r resources are unrelated, the approximation ratio of our algorithm becomes k+2, where k≤ r is a constant depending on the problem instance. As an application, we also show that our techniques can be easily applied to optical burst switching (OBS) networks to design more efficient wavelength scheduling algorithms.
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.
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.
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.
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.
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.
47532017
On fundamental tradeoffs between delay bounds and computational complexity in packet scheduling algorithms
We clarify, extend, and solve a long-standing open problem concerning the computational complexity for packet scheduling algorithms to achieve tight end-to-end delay bounds. We first focus on the difference between the time a packet finishes service in a scheduling algorithm and its virtual finish time under a GPS (General Processor Sharing) scheduler, called GPS-relative delay. We prove that, under a slightly restrictive but reasonable computational model, the lower bound computational complexity of any scheduling algorithm that guarantees O(1) GPS-relative delay bound is /spl Omega/(logn). We also discover that, surprisingly, the complexity lower bound remains the same even if the delay bound is relaxed to O(n/sup a/) for 0<a<1. This implies that the delay-complexity tradeoff curve is flat in the "interval" [O(1),O(n)). We later conditionally extend both complexity results (for O(1) or O(n/sup a/) delay) to a much stronger computational model, the linear decision tree. Finally, we show that the same complexity lower bounds are conditionally applicable to guaranteeing tight end-to-end delay bounds, if the delay bounds are provided through the Latency Rate (LR) framework.
5323377
Visualizing the expertise space
Expertise management systems are being widely adopted in organizations to manage tacit knowledge embedded in employees' heads. These systems have successfully applied many information technologies developed in fields such as information retrieval and document management to support expertise information collection, processing, and distribution. In this paper, we investigate the potentials of applying visualization techniques to support exploration of an expertise space. We implemented two widely applied dimensionality reduction visualization techniques, the self-organizing map and multidimensional scaling; to generate expert map and expertise field map visualizations based on an expertise data set. Our proposed approach is generic for automatic mapping of expertise space of an organization, research field, scientific domain, etc. Our initial analysis on the visualization results indicated that the expert map and expertise field map captured useful underlying structures of the expertise space and had the potential to support more efficient and effective expertise information searching and browsing.
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.
14424091
Sustaining Availability of Web Services under Distributed Denial of Service Attacks
The recent tide of Distributed Denial of Service (DDoS) attacks against high-profile web sites demonstrate how devastating DDoS attacks are and how defenseless the Internet is under such attacks. We design a practical DDoS defense system that can protect the availability of web services during severe DDoS attacks. The basic idea behind our system is to isolate and protect legitimate traffic from a huge volume of DDoS traffic when an attack occurs. Traffic that needs to be protected can be recognized and protected using efficient cryptographic techniques. Therefore, by provisioning adequate resource (e.g., bandwidth) to legitimate traffic separated by this process, we are able to provide adequate service to a large percentage of clients during DDoS attacks. The worst-case performance (effectiveness) of the system is evaluated based on a novel game theoretical framework, which characterizes the natural adversarial relationship between a DDoS adversary and the proposed system. We also conduct a simulation study to verify a key assumption used in the game-theoretical analysis and to demonstrate the system dynamics during an attack.
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.