Competitive Deadline Scheduling via Additional or Faster Processors

This paper studies on-line scheduling in a single-processor system that allows preemption. The aim is to maximize the total value of jobs completed by their deadlines. It is known that if the on-line scheduler is given a processor faster (say, two times faster) than the off-line scheduler, then there exists an on-line algorithm called that can achieve an O(1) competitive ratio. In this paper, we show that using additional unit-speed processors instead of a faster processor is a possible but not cost effective way to achieve an O(1) competitive ratio. Specifically, we find that-(logk) unit-speed processors are required, where k is the importance ratio. Another contribution of this paper is an improved analysis of the competitiveness of ; this new analysis enables us to show that , when extended to multi-processor systems, can still guarantee an O(1) competitive ratio.     

A Representation of the Interval Hull of a Tolerance Polyhedron Describing Inclusions of Function Values and Slopes

Given a nonempty set of functions

On Projection Matrices $$\mathcal{P}^k \to \mathcal{P}^2 ,k = 3,...,6, $$ and their Applications in Computer Vision

Projection matrices from projective spaces have long been used in multiple-view geometry to model the perspective projection created by the pin-hole camera. In this work we introduce higher-dimensional mappings for the representation of various applications in which the world we view is no longer rigid. We also describe the multi-view constraints from these new projection matrices (where k > 3) and methods for extracting the (non-rigid) structure and motion for each application.     

A result on k-valent graphs and its application to a graph embedding problem

Summary It is proved that any n-vertex, k-valent undirected simple graph, G, contains a spanning tree with at least leaves. As a result of this it is shown that any such graph contains an independent set, of size at least n/5k, with the property that deleting the vertices in this set and their incident edges does not disconnect G. This latter result is applied by giving an improved upper bound on the area required to embed arbitrary graphs into grid graphs.     

Ramsey numbers and an approximation algorithm for the vertex cover problem

Summary We show two results. First we derive an upper bound for the special Ramsey numbers r _k(q) where r _k(q) is the largest number of nodes a graph without odd cycles of length bounded by 2k+1 and without an independent set of size q+1 can have. We prove The proof is constructive and yields an algorithm for computing an independent set of that size. Using this algorithm we secondly describe an O(¦V¦·¦E¦) time bounded approximation algorithm for the vertex cover problem, whose worst case ratio is , for all graphs with at most (2k+3) ^k (2k+2) nodes (e.g. 1.8, if ¦V¦146000).     

Definability of Polyadic Lifts of Generalized Quantifiers

We study generalized quantifiers on finite structures.With every function : we associate a quantifier Q by letting Q x say there are at least (n) elementsx satisfying , where n is the sizeof the universe. This is the general form ofwhat is known as a monotone quantifier of type < 1 >.We study so called polyadic liftsof such quantifiers. The particular lifts we considerare Ramseyfication, branching and resumption.In each case we get exact criteria fordefinability of the lift in terms of simpler quantifiers.     

Stability of Linear Difference and Differential Inclusions

Any given n×n matrix A is shown to be a restriction, to the A-invariant subspace, of a nonnegative N×N matrix B of spectral radius (B) arbitrarily close to (A). A difference inclusion , where is a compact set of matrices, is asymptotically stable if and only if can be extended to a set of nonnegative matrices B with or . Similar results are derived for differential inclusions.     

Object-oriented cam design through the internet

We have developed a Web-based interactive cam design package under the programming paradigm of the language environment. This package was initially developed as a teaching and learning tool for educational use in an undergraduate Computer-Aided Mechanism Design course. Because the system is Web-based and implemented through a client/server model with the user interface through the Web browser, it is easy to use and maintain. The system can also be used to solve practical engineering cam design problems with flat or roller followers and with translating or oscillating motion types. The system can be used to generate the cam profile, transmission angle, position, velocity, and acceleration of the follower. Once a cam/follower system is designed, animation of the cam/follower system can be performed. At the end of the design, the CNC code for manufacturing the designed cam can also be produced through our Web-based cam design system. The package consists of a number of modules including various Web pages, common gateway interface (CGI) programs, a program called cam.ch, and the CCam class which performs the necessary computation for cam design. Two different versions of the cam design package have been designed and implemented. One runs the cam design program on the client machine as a applet, and the other runs the cam design program on the Web server through CGI. In this paper, details of design and implementation of Web-based cam design package will be described. Two application examples with different motion types for the follower will be used to illustrate features of the applet-based and CGI-based implementation schemes. The ideas of the Web-based software design presented in this paper can be applied to other application areas.     

Stability of the Logistic Population Model with Delayed Environmental Response

The population dynamics model , was considered. For this model with uniform distribution of delays and a _n = 0, nonnegativeness and convexity of the sequence a _k (0 k n) was shown to be the sufficient stability condition. Therefore, there is no need to constrain the reproduction rate and the mean delay .     

Combining the Perceptron Algorithm with Logarithmic Simulated Annealing

We present results of computational experiments with an extension of the Perceptron algorithm by a special type of simulated annealing. The simulated annealing procedure employs a logarithmic cooling schedule , where is a parameter that depends on the underlying configuration space. For sample sets S of n-dimensional vectors generated by randomly chosen polynomials , we try to approximate the positive and negative examples by linear threshold functions. The approximations are computed by both the classical Perceptron algorithm and our extension with logarithmic cooling schedules. For and , the extension outperforms the classical Perceptron algorithm by about 15% when the sample size is sufficiently large. The parameter was chosen according to estimations of the maximum escape depth from local minima of the associated energy landscape.      

Two-Parameter Discrete Systems over a Residue Ring and Their Properties

A class of two-parameter discrete systems defined on the ring of class of residues of integers modulo m is studied. All solutions are shown to be periodic, stability conditions (equality of solutions to zero, beginning from a certain instant) and a controllability condition are formulated. Controllability is shown to guarantee stabilizability.     

On the complexity of graph self-assembly in accretive systems

We study the complexity of the Accretive Graph Assembly Problem (). An instance of consists of an edge-weighted graph G, a seed vertex in G, and a temperature τ. The goal is to determine if the graph G can be assembled by a sequence of vertex additions starting from the seed vertex. The edge weights model the forces of attraction and repulsion, and determine which vertices can be added to a partially assembled graph at the given temperature. A vertex can be added when the total weight to its already built neighbors in the graph is at least τ. The assembly process is sequential meaning that only one vertex can be added at a time. Our first result is that is NP-complete even on planar graphs with maximum degree 3 when edges have only two different types of weights. This resolves the complexity of in the sense that the problem is poly-time solvable when either the maximum degree is at most 2 or the number of distinct edge weights is one, and is NP-complete otherwise. Our second result is a dichotomy theorem that completely characterizes the complexity of on graphs with maximum degree 3 and two distinct weights: w _p and w _n . We give a simple system of linear constraints on w _p , w _n , and τ that determines whether the problem is NP-complete or is poly-time solvable. In the process of establishing this dichotomy, we give a poly-time algorithm to solve a non-trivial class of Finally, we consider the optimization version of where the goal is to assemble a largest-possible induced subgraph of the given input graph. We show that even on graphs that can be assembled and have maximum degree 3, it is NP-hard to assemble a (1/n ^1-ε)-fraction of the input graph for any here n denotes the number of vertices in G.     

Solving Underdetermined Systems with Interval Methods

In this paper, we use the concepts of {1} - and {2} -inverse of a matrix to construct such a Krawczyk-like operator as

Computation of Battle–Lemarie Wavelets Using an FFT-Based Algorithm

Battle and Lemarie derived independently wavelets by orthonormalizing B-splines. The scaling function _m (t) corresponding to Battle–Lemarie's wavelet _m (t) is given by , where B _m(t) is the mth-order central B-spline and the coefficients _{m, k} satisfy . In this paper, we propose an FFT-based algorithm for computing the expansion coefficients _{m, k} and the two-scale relations of the scaling functions and wavelets. The algorithm is very simple and it can be easily implemented. Moreover, the expansion coefficients can be efficiently and accurately obtained via multiple sets of FFT computations. The computational approach presented in this paper here is noniterative and is more efficient than the matrix approach recently proposed in the literature.     

Adaptive Anomaly Detection in Transaction-Oriented Networks

Adaptive algorithms for real-time and proactive detection of network/service anomalies, i.e., soft performance degradations, in transaction-oriented wide area networks (WANs) have been developed. These algorithms (i) adaptively sample and aggregate raw transaction records to compute service-class based traffic intensities, in which potential network anomalies are highlighted; (ii) construct dynamic and service-class based performance thresholds for detecting network and service anomalies; and (iii) perform service-class based and real-time network anomaly detection. These anomaly detection algorithms are implemented as a real-time software system called TRISTAN ( ansaction n antaneous nomaly otification), which is deployed in the AT&T Transaction Access Services (TAS) network. The TAS network is a commercially important, high volume (millions of transactions per day), multiple service classes (tens), hybrid telecom and data WAN that services transaction traffic such as credit card transactions in the US and neighboring countries. TRISTAN is demonstrated to be capable of automatically and adaptively detecting network/service anomalies and correctly identifying the corresponding "guilty" service classes in TAS. TRISTAN can detect network/service faults that elude detection by the traditional alarm-based network monitoring systems.     

Spigot Algorithm and Reliable Computation of Natural Logarithm

The spigot approach used in the previous paper (Reliable Computing 7 (3) (2001), pp. 247–273) for root computation is now applied to natural logarithms. The logarithm ln Q with Q , Q > 1 is decomposed into a sum of two addends k ₁× ln Q ₁+k ₂× ln Q ₂ with k ₁, k ₂ , then each of them is computed by the spigot algorithm and summation is carried out using integer arithmetic. The whole procedure is not literally a spigot algorithm, but advantages are the same: only integer arithmetic is needed whereas arbitrary accuracy is achieved and absolute reliability is guaranteed. The concrete procedure based on the decomposition with p, q ( – {0}), p < q is simple and ready for implementation. In addition to the mentioned paper, means for determining an upper bound for the biggest integer occurring in the process of spigot computing are now provided, which is essential for the reliability of machine computation.     

Computational Divided Differencing and Divided-Difference Arithmetics

Tools for computational differentiation transform a program that computes a numerical function F(x) into a related program that computes F(x) (the derivative of F). This paper describes how techniques similar to those used in computational-differentiation tools can be used to implement other program transformations—in particular, a variety of transformations for computational divided differencing. The specific technical contributions of the paper are as follows:– It presents a program transformation that, given a numerical function F(x) defined by a program, creates a program that computes F[x ₀, x ₁], the first divided difference of F(x), where – It shows how computational first divided differencing generalizes computational differentiation.– It presents a second program transformation that permits the creation of higher-order divided differences of a numerical function defined by a program.– It shows how to extend these techniques to handle functions of several variables.The paper also discusses how computational divided-differencing techniques could lead to faster and/or more robust programs in scientific and graphics applications.Finally, the paper describes how computational divided differencing relates to the numerical-finite-differencing techniques that motivated Robert Paige's work on finite differencing of set-valued expressions in SETL programs.     

Static verification of component composition in contextual composition frameworks

Contextual component frameworks, such as Enterprise JavaBeans (EJB), allow for components to specify boundary conditions for the runtime context. These conditions are satisfied at runtime by services of the underlying platform, thus ensuring that the context in which components run exhibits properties that allow them to operate correctly. Depending on how components call each other, it is possible that satisfying such conditions lead to problems such as reduced performance due to redundant service execution, or permanent errors (composition mismatches), due to incompatible boundary conditions. Currently, the semantics of these boundary conditions are expressed in natural language only, making it impossible to incorporate them into an automatic analysis tool. Furthermore, early understanding of how components call each other would be necessary, but it is currently difficult to achieve by means of a tool, as the method dispatch rules in a component system differ from the dispatch rules of the programming language(s) in which they were developed. We have developed a metamodel, , for describing boundary conditions, an analysis method, , and a static component-level call graph extraction method for EJB applications, CHA _EJB . uses models to analyze inter-component call graphs, and thus detect problems such as composition mismatches or redundancies, thus allowing for remedial action to take place. We present and CHA _EJB in this article, show that produces correct results, and describe a prototype analysis tool implementing the three, which we used to validate our approach on two popular EJB applications. The support of the Informatics Commercialisation initiative of Enterprise Ireland is gratefully acknowledged.