9132194
Semi-normal Schedulings: Improvement on Goemans' Algorithm
Theoretical study of the multiprocessor job scheduling problem has made significant progress recently, which, however, seems not yet to imply practical algorithms. This paper offers new observations and introduces new techniques for the multiprocessor job scheduling problem P3|fix|C max. The concept of semi-normal schedulings is introduced and a very simple linear time algorithm for constructing semi-normal schedulings is developed. Thorough analysis is provided in the study of semi-normal schedulings, which enables us to conclude that the proposed algorithm is an approximation algorithm of ratio 9/8 for the P3|fix|C max problem. This improves the previous best (practical) ratio 7/6 by Goemans. Our techniques are also useful for multiprocessor job scheduling problems on systems with more than three processors.
31382426
Strong Fault-Tolerance: Parallel Routing in Networks with Faults
A d-regular network G is strongly fault-tolerant if for any copy Gf of G with at most d - 2 faulty nodes, every pair of nonfaulty nodes u and v in Gf admits min{df(u), df (v)} node-disjoint paths in Gf from u to v, where df(u) and df(v) are the degrees of the nodes u and v in Gf. We show that popular network structures, such as hypercube and star networks, are strongly fault-tolerant. We develop efficient algorithms that construct the maximum number of node-disjoint paths of optimal or nearly optimal length in these networks with faulty nodes. Our algorithms are optimal in terms of their running time.
1021255
A minimal and complete set of operators for the development of robust manifold mesh modelers
In this paper, we identify a minimal and complete set of fundamental operators, which is necessary and sufficient for performing all homeomorphic and topological operations on 2- manifold mesh structures. Efficient algorithms are developed for the implementation of these operators. We also developed a set of powerful, user-friendly, and effective operators at the level of user-interface. Using these operators, we have developed a prototype system for robust, interactive, and user-friendly modeling of orientable 2-manifold meshes. Users of our system can perform a large set of homeomorphic and topological changes with these user-interface level operators. Our system is topologically robust in the sense that users will never create invalid 2-manifold mesh structure with these operators. In our system, the homeomorphic and topological surgery operations can be applied alternatively on 2-manifold meshes. With our system, users can blend surfaces, construct rinds, and open holes on these rind shapes. With our system, the shapes that look like solid, non-manifold, or 2-manifold with boundary can be manipulated. The system also provides automatic texture mapping during topology changes.
2261180
Graph Ear Decompositions and Graph Embeddings
Ear decomposition of a graph has been extensively studied in relation to graph connectivity. In this paper, a connection of ear decomposition to graph embeddings is exhibited. It is shown that constructing a maximum-paired ear decomposition of a graph and constructing a maximum-genus embedding of the graph are polynomial-time equivalent. Applications of this connection are discussed.
5242879
Interactive rind modeling
In this paper, we describe a technique, with roots in topological graph theory, that we call rind modeling. It provides for the easy creation of surfaces resembling peeled and punctured rinds. We show how the method's two main steps of: 1) creation of a shell or crust like the rind of an orange, and 2) opening holes in the crust by punching or peeling can be encapsulated into a real time semi-automatic interactive algorithm. We include a number of worked examples, some by students in a first modeling course, that demonstrate the ease with which a large variety of intricate rind shapes can be created.
16331940
Optimal Parallel Routing in Star Networks
Star networks have recently been proposed as attractive alternatives to the popular hypercube for interconnecting processors on a parallel computer. In this paper, we present an efficient algorithm that constructs an optimal parallel routing in star networks. Our result improves previous results for the problem.
39815337
Making Timed Automata Communicate
A computation model is introduced in which real-time constraints as well as data communications can be explicitely expressed. The model is presented in a graphical form. Its semantics is studied and algorithms to compute bisimulation equivalences for such graphs are proposed.
10227949
Analysis of nonsmooth vector-valued functions associated with second-order cones
Abstract.Let be the Lorentz/second-order cone in . For any function f from to , one can define a corresponding function fsoc(x) on by applying f to the spectral values of the spectral decomposition of x∈ with respect to . We show that this vector-valued function inherits from f the properties of continuity, (local) Lipschitz continuity, directional differentiability, Fréchet differentiability, continuous differentiability, as well as (ρ-order) semismoothness. These results are useful for designing and analyzing smoothing methods and nonsmooth methods for solving second-order cone programs and complementarity problems.
6192242
Computing Maximum-Scoring Segments in Almost Linear Time
Given a sequence, the problem studied in this paper is to find a set of k disjoint continuous subsequences such that the total sum of all elements in the set is maximized. This problem arises naturally in the analysis of DNA sequences. The previous best known algorithm requires Θ(n log n) time in the worst case. For a given sequence of length n, we present an almost linear-time algorithm for this problem. Our algorithm uses a disjoint-set data structure and requires O(nα(n, n)) time in the worst case, where α(n, n) is the inverse Ackermann function.
987186
Implementing Minimized Multivariate PKC on Low-Resource Embedded Systems
Multivariate (or $\mathcal{MQ}$) public-key cryptosystems (PKC) are alternatives to traditional PKCs based on large algebraic structures (e.g., RSA and ECC); they usually execute much faster than traditional PKCs on the same hardware. However, one major challenge in implementing multivariates in embedded systems is that the key size can be prohibitively large for applications with stringent resource constraints such as low-cost smart cards, sensor networks (e.g., Berkeley motes), and radio-frequency identification (RFID). In this paper, we investigate strategies for shortening the key of a multivariate PKC. We apply these strategies to the Tame Transformation Signatures (TTS) as an example and quantify the improvement in key size and running speed, both theoretically and via implementation. We also investigate ways to save die space and energy consumption in hardware, reporting on our ASIC implementation of TTS on a TSMC 0.25μm process. Even without any key shortening, the current consumption of TTS is only 21 μA for computing a signature, using 22,000 gate equivalents and 16,000 100-kHz cycles (160 ms). With circulant-matrix key shortening, the numbers go down to 17,000 gates and 4,400 cycles (44 ms). We therefore conclude: besides representing a future-proofing investment against the emerging quantum computers, multivariates can be immediately useful in niches.
17449226
Approximation algorithms for scheduling multiple feasible interval jobs
Time-critical jobs in many real-time applications have multiple feasible intervals. Such a job is constrained to execute from start to completion in one of its feasible intervals. A job fails if the job remains incomplete at the end of the last feasible interval. This paper is concerned with how to find a schedule in which the number of jobs completed in one of their feasible intervals is maximized. We show that the maximization problem is NP-hard for both nonpreemptible and preemptible jobs. This paper develops two approximation algorithms for nonpreemptible and preemptible jobs. When jobs are nonpreemptible, algorithm LECF is with a 2-approximation factor; when jobs are preemptible, algorithm LEF is proved being a 3-approximation algorithm. We also show that our analysis on the two algorithms is tight by providing a set of input instances. Simulation results demonstrate that algorithms LECF and LEF not only guarantee the approximation factors but also outperform other multiple feasible interval scheduling algorithms.