New Approximation Algorithms for Minimum Cycle Bases of Graphs

We consider the problem of computing an approximate minimum cycle basis of an undirected non-negative edge-weighted graph G with m edges and n vertices; the extension to directed graphs is also discussed. In this problem, a {0,1} incidence vector is associated with each cycle and the vector space over F-2 generated by these vectors is the cycle space of G. A set of cycles is called a cycle basis of G if it forms a basis for its cycle space. A cycle basis where the sum of the weights of the cycles is minimum is called a minimum cycle basis of G. Cycle bases of low weight are useful in a number of contexts, e.g. the analysis of electrical networks, structural engineering, chemistry, and surface reconstruction. Although in most such applications any cycle basis can be used, a low weight cycle basis often translates to better performance and/or numerical stability. Despite the fact that the problem can be solved exactly in polynomial time, we design approximation algorithms since the performance of the exact algorithms may be too expensive for some practical applications. We present two new algorithms to compute an approximate minimum cycle basis. For any integer k >= 1, we give (2k - 1)-approximation algorithms with expected running time O(kmn(1+2/k) + mn((1+1/k)(omega-1))) and deterministic running time O(n(3+2/k) ), respectively. Here omega is the best exponent of matrix multiplication. It is presently known that omega < 2.376. Both algorithms are o(m(omega)) for dense graphs. This is the first time that any algorithm which computes sparse cycle bases with a guarantee drops below the Theta(m(omega) ) bound. We also present a 2-approximation algorithm with expected running time O(M-omega root n log n), a linear time 2-approximation algorithm for planar graphs and an O(n(3)) time 2.42-approximation algorithm for the complete Euclidean graph in the plane.

Load balancing algorithms for an extended hypercube

Reduction of the execution time of a job through equitable distribution of work load among the processors in a distributed system is the goal of load balancing. Performance of static and dynamic load balancing algorithms for the extended hypercube, is discussed. Threshold algorithms are very well-known algorithms for dynamic load balancing in distributed systems. An extension of the threshold algorithm, called the multilevel threshold algorithm, has been proposed. The hierarchical interconnection network of the extended hypercube is suitable for implementing the proposed algorithm. The new algorithm has been implemented on a transputer-based system and the performance of the algorithm for an extended hypercube is compared with those for mesh and binary hypercube networks

Absolutely expedient algorithms for learning Nash equilibria

This paper considers a multi-person discrete game with random payoffs. The distribution of the random payoff is unknown to the players and further none of the players know the strategies or the actual moves of other players. A class of absolutely expedient learning algorithms for the game based on a decentralised team of Learning Automata is presented. These algorithms correspond, in some sense, to rational behaviour on the part of the players. All stable stationary points of the algorithm are shown to be Nash equilibria for the game. It is also shown that under some additional constraints on the game, the team will always converge to a Nash equilibrium.

Heterogeneous nucleation of pb particles embedded in a Zn matrix

Zinc-10 and 20 wt pct Pb alloys have been rapidly solidified by melt spinning to obtain a very fine scale dispersion of nanometer-sized Pb particles embedded in Zn matrix. The microstructure and crystallography of the Pb particles have been studied using transmission electron microscopy (TEM). Each embedded Pb particle is a single crystal, with a truncated hexagonal biprism shape with the 6/mmm Zn matrix point group symmetry surrounded by and { 0001 á },\text { \text10[`\text1] \text0 },\text and { \text10[`\text1] \text1 }0001 1010 and 1011 facets. The Pb particles solidify with a well-defined orientation relationship with the Zn matrix of ( 0001 )Zn ||(111)Pb\text and\text [ \text11[`\text2] \text0 ]Zn| ||[ 1[`1] 0 ]Pb 0001Zn(111)Pb and 1120Zn110Pb . The melting and solidification behavior of the Pb particle have been studied using differential scanning calorimetry (DSC). The Pb particles solidify with an undercooling of approximately 30 K, by heterogeneous nucleation on the {0001} facets of the surrounding Zn matrix, with an apparent contact angle of 23 deg.

Heterogeneous permanganate oxidation of 1,5-dienes: a novel synthesis of 5-substituted butanolides

In the presence of a catalytic amount of water, 1,5-dienes undergo novel and unusual oxidation with potassium permanganate�copper sulfate in dichloromethane to give substituted butanolides in good yields under very mild conditions.

Stochastic Approximation Algorithms for Constrained Optimization via Simulation

We develop four algorithms for simulation-based optimization under multiple inequality constraints. Both the cost and the constraint functions are considered to be long-run averages of certain state-dependent single-stage functions. We pose the problem in the simulation optimization framework by using the Lagrange multiplier method. Two of our algorithms estimate only the gradient of the Lagrangian, while the other two estimate both the gradient and the Hessian of it. In the process, we also develop various new estimators for the gradient and Hessian. All our algorithms use two simulations each. Two of these algorithms are based on the smoothed functional (SF) technique, while the other two are based on the simultaneous perturbation stochastic approximation (SPSA) method. We prove the convergence of our algorithms and show numerical experiments on a setting involving an open Jackson network. The Newton-based SF algorithm is seen to show the best overall performance.

Heuristic algorithms for scheduling of a batch processor in automobile gear manufacturing

In this paper we address a scheduling problem for minimising total weighted tardiness. The motivation for the paper comes from the automobile gear manufacturing process. We consider the bottleneck operation of heat treatment stage of gear manufacturing. Real life scenarios like unequal release times, incompatible job families, non-identical job sizes and allowance for job splitting have been considered. A mathematical model taking into account dynamic starting conditions has been developed. Due to the NP-hard nature of the problem, a few heuristic algorithms have been proposed. The performance of the proposed heuristic algorithms is evaluated: (a) in comparison with optimal solution for small size problem instances, and (b) in comparison with `estimated optimal solution' for large size problem instances. Extensive computational analyses reveal that the proposed heuristic algorithms are capable of consistently obtaining near-optimal solutions (that is, statistically estimated one) in very reasonable computational time.

Cooperative Spectrum Sensing Algorithms For OFDM Systems with Frequency Selective Channels

This paper considers the problem of spectrum sensing in cognitive radio networks when the primary user employs Orthogonal Frequency Division Multiplexing (OFDM). We specifically consider the scenario when the channel between the primary and a secondary user is frequency selective. We develop cooperative sequential detection algorithms based on energy detectors. We modify the detectors to mitigate the effects of some common model uncertainties such as timing and frequency offset, IQ-imbalance and uncertainty in noise and transmit power. The performance of the proposed algorithms are studied via simulations. We show that the performance of the energy detector is not affected by the frequency selective channel. We also provide a theoretical analysis for some of our algorithms.

Genetic algorithms: a survey

Genetic algorithms provide an alternative to traditional optimization techniques by using directed random searches to locate optimal solutions in complex landscapes. We introduce the art and science of genetic algorithms and survey current issues in GA theory and practice. We do not present a detailed study, instead, we offer a quick guide into the labyrinth of GA research. First, we draw the analogy between genetic algorithms and the search processes in nature. Then we describe the genetic algorithm that Holland introduced in 1975 and the workings of GAs. After a survey of techniques proposed as improvements to Holland's GA and of some radically different approaches, we survey the advances in GA theory related to modeling, dynamics, and deception

Heterogeneous permanganate oxidations: Synthesis of medium ring keto-lactones via substituent directed oxidative cyclisation

Homoallyl alcohols 4a-b and 5a-b undergo smooth oxidative cyclisation to give the corresponding ring enlarged keto-lactones under heterogeneous permanganate oxidation conditions.

Managing interprocessor delays in distributed recursive algorithms

For a class of distributed recursive algorithms, it is shown that a stochastic approximation-like tapering stepsize routine suppresses the effects of interprocessor delays.

High-Throughput Study of the Cu(CH3COO)(2)center dot H2O-5-Nitroisophthalic Acid Heterocyclic Ligand System: Synthesis, Structure, Magnetic, and Heterogeneous Catalytic Studies of Three Copper Nitroisophthalates

A high-throughput screening was employed to identify new compounds in Cu(CH3COO)(2)center dot H2O-NIPA-heterocyclic ligand systems. Of the compounds identified, three compounds, Cu-3{(NO2)-C6H3-(COO)(2)}(3)(C3N6H6)] (1), Cu-2(mu(3)-OH)(H2O){(NO2)-C6H3-(COO)(2)}(CN4H)]center dot-(H2O) (II), and Cu-2(mu(3)-OH)(H2O){(NO2)-C6H3-(COO)(2}-)(CN5H2)]center dot 2(H2O) (III), have been isolated as good quality single crystals by employing conventional hydrothermal methods. Three other compounds, Cu-2{(NO2)-C6H3-(COO)(2)}-(CN4H)(H2O) (IIa), Cu-2{(NO2)-C6H3-(COO)(2)}(CN5H2) (IIIa), and Cu-2{(NO2)-C6H3-(COO)(2)}{(CN5H2)(2)}2H(2)O (IIIb), were identified by a combination of elemental analysis, thermogravimetric analysis (TGA), and IR spectroscopic studies, although their structures are yet to be determined. The single crystalline compounds were also characterized by elemental analysis, TGA, IR, UV vis, magnetic, and catalytic studies. The structures of the compounds have paddle wheel (I) and infinite Cu 0(H) Cu chains (II and HI) connected with NLPA and heterocyclic ligands forming two-(II) and three-dimensional (I and III) structures. The bound and lattice water molecules in 11 and 111 could be reversibly removed/inserted without affecting the structure. In the case of II, the removal of water gives rise to a structural transition, but the dehydrated phase reverts back to the original phase on prolonged exposure to atmospheric conditions. Magnetic studies indicate an overall antiferromagnetism in all of the compounds. Lewis acid catalytic studies indicate that compounds II and HI are active for cyanosilylation of imines.

Line clipping revisited: Two efficient algorithms based on simple geometric observations

Two new line clipping algorithms, the opposite-corner algorithm and the perpendicular-distance algorithm, that are based on simple geometric observations are presented. These algorithms do not require computation of outcodes nor do they depend on the parametric representations of the lines. It is shown that the opposite-corner algorithm perform consistently better than an algorithm due to Nicholl, Lee, and Nicholl which is claimed to be better than the classic algorithm due to Cohen-Sutherland and the more recent Liang-Barsky algorithm. The pseudo-code of the opposite-corner algorithm is provided in the Appendix.

S-nets: A Petri net based model for performance evaluation of real-time scheduling algorithms

A new class of nets, called S-nets, is introduced for the performance analysis of scheduling algorithms used in real-time systems Deterministic timed Petri nets do not adequately model the scheduling of resources encountered in real-time systems, and need to be augmented with resource places and signal places, and a scheduler block, to facilitate the modeling of scheduling algorithms. The tokens are colored, and the transition firing rules are suitably modified. Further, the concept of transition folding is used, to get intuitively simple models of multiframe real-time systems. Two generic performance measures, called �load index� and �balance index,� which characterize the resource utilization and the uniformity of workload distribution, respectively, are defined. The utility of S-nets for evaluating heuristic-based scheduling schemes is illustrated by considering three heuristics for real-time scheduling. S-nets are useful in tuning the hardware configuration and the underlying scheduling policy, so that the system utilization is maximized, and the workload distribution among the computing resources is balanced.

Some Algorithms for Eigensubspace Estimation

An important tool in signal processing is the use of eigenvalue and singular value decompositions for extracting information from time-series/sensor array data. These tools are used in the so-called subspace methods that underlie solutions to the harmonic retrieval problem in time series and the directions-of-arrival (DOA) estimation problem in array processing. The subspace methods require the knowledge of eigenvectors of the underlying covariance matrix to estimate the parameters of interest. Eigenstructure estimation in signal processing has two important classes: (i) estimating the eigenstructure of the given covariance matrix and (ii) updating the eigenstructure estimates given the current estimate and new data. In this paper, we survey some algorithms for both these classes useful for harmonic retrieval and DOA estimation problems. We begin by surveying key results in the literature and then describe, in some detail, energy function minimization approaches that underlie a class of feedback neural networks. Our approaches estimate some or all of the eigenvectors corresponding to the repeated minimum eigenvalue and also multiple orthogonal eigenvectors corresponding to the ordered eigenvalues of the covariance matrix. Our presentation includes some supporting analysis and simulation results. We may point out here that eigensubspace estimation is a vast area and all aspects of this cannot be fully covered in a single paper. (C) 1995 Academic Press, Inc.