Some Generalisations of the Time Minimising Assignment Problem

The time minimising assignment problem is the problem of finding an assignment of n jobs to n facilities, one to each, which minimises the total time for completing all the jobs. The usual assumption made in these problems is that all the jobs are commenced simultaneously. In this paper two generalisations of this assumption are considered, and algorithms are presented to solve these general problems. Numerical examples are worked out illustrating the algorithms.

Neural network approach for the two-dimensional assignment problem

A neural network approach for solving the two-dimensional assignment problem is proposed. The design of the neural network is discussed and simulation results are presented. The neural network obtains 10-15% lower cost placements on the examples considered, than the adjacent pairwise exchange method.

Task assignment in a multiprocessor system

One of the key problems in the design of any incompletely connected multiprocessor system is to appropriately assign the set of tasks in a program to the Processing Elements (PEs) in the system. The task assignment problem has proven difficult both in theory and in practice. This paper presents a simple and efficient heuristic algorithm for assigning program tasks with precedence and communication constraints to the PEs in a Message-based Multiple-bus Multiprocessor System, M3, so that the total execution time for the program is minimized. The algorithm uses a cost function: “Minimum Distance and Parallel Transfer” to minimize the completion time. The effectiveness of the algorithm has been demonstrated by comparing the results with (i) the lower bound on the execution time of a program (task) graph and (ii) a random assignment.

A non-cooperative game-theoretic approach to channel assignment in multi-channel multi-radio wireless networks

Channel assignment in multi-channel multi-radio wireless networks poses a significant challenge due to scarcity of number of channels available in the wireless spectrum. Further, additional care has to be taken to consider the interference characteristics of the nodes in the network especially when nodes are in different collision domains. This work views the problem of channel assignment in multi-channel multi-radio networks with multiple collision domains as a non-cooperative game where the objective of the players is to maximize their individual utility by minimizing its interference. Necessary and sufficient conditions are derived for the channel assignment to be a Nash Equilibrium (NE) and efficiency of the NE is analyzed by deriving the lower bound of the price of anarchy of this game. A new fairness measure in multiple collision domain context is proposed and necessary and sufficient conditions for NE outcomes to be fair are derived. The equilibrium conditions are then applied to solve the channel assignment problem by proposing three algorithms, based on perfect/imperfect information, which rely on explicit communication between the players for arriving at an NE. A no-regret learning algorithm known as Freund and Schapire Informed algorithm, which has an additional advantage of low overhead in terms of information exchange, is proposed and its convergence to the stabilizing outcomes is studied. New performance metrics are proposed and extensive simulations are done using Matlab to obtain a thorough understanding of the performance of these algorithms on various topologies with respect to these metrics. It was observed that the algorithms proposed were able to achieve good convergence to NE resulting in efficient channel assignment strategies.

Redistribution Mechanisms for Assignment of Heterogeneous Objects

There are p heterogeneous objects to be assigned to n competing agents (n > p) each with unit demand. It is required to design a Groves mechanism for this assignment problem satisfying weak budget balance, individual rationality, and minimizing the budget imbalance. This calls for designing an appropriate rebate function. When the objects are identical, this problem has been solved which we refer as WCO mechanism. We measure the performance of such mechanisms by the redistribution index. We first prove an impossibility theorem which rules out linear rebate functions with non-zero redistribution index in heterogeneous object assignment. Motivated by this theorem,we explore two approaches to get around this impossibility. In the first approach, we show that linear rebate functions with non-zero redistribution index are possible when the valuations for the objects have a certain type of relationship and we design a mechanism with linear rebate function that is worst case optimal. In the second approach, we show that rebate functions with non-zero efficiency are possible if linearity is relaxed. We extend the rebate functions of the WCO mechanism to heterogeneous objects assignment and conjecture them to be worst case optimal.

Generalized eigenvalue decomposition of the field autocorrelation in correlation diffusion of photons in turbid media

We propose a novel numerical method based on a generalized eigenvalue decomposition for solving the diffusion equation governing the correlation diffusion of photons in turbid media. Medical imaging modalities such as diffuse correlation tomography and ultrasound-modulated optical tomography have the (elliptic) diffusion equation parameterized by a time variable as the forward model. Hitherto, for the computation of the correlation function, the diffusion equation is solved repeatedly over the time parameter. We show that the use of a certain time-independent generalized eigenfunction basis results in the decoupling of the spatial and time dependence of the correlation function, thus allowing greater computational efficiency in arriving at the forward solution. Besides presenting the mathematical analysis of the generalized eigenvalue problem on the basis of spectral theory, we put forth the numerical results that compare the proposed numerical method with the standard technique for solving the diffusion equation.

An algebraic theory of functional and multivalued dependencies in relational databases

Computation of the dependency basis is the fundamental step in solving the membership problem for functional dependencies (FDs) and multivalued dependencies (MVDs) in relational database theory. We examine this problem from an algebraic perspective. We introduce the notion of the inference basis of a set M of MVDs and show that it contains the maximum information about the logical consequences of M. We propose the notion of a dependency-lattice and develop an algebraic characterization of inference basis using simple notions from lattice theory. We also establish several interesting properties of dependency-lattices related to the implication problem. Founded on our characterization, we synthesize efficient algorithms for (a): computing the inference basis of a given set M of MVDs; (b): computing the dependency basis of a given attribute set w.r.t. M; and (c): solving the membership problem for MVDs. We also show that our results naturally extend to incorporate FDs also in a way that enables the solution of the membership problem for both FDs and MVDs put together. We finally show that our algorithms are more efficient than existing ones, when used to solve what we term the ‘generalized membership problem’.

Identification of dynamical systems with fractional derivative damping models using inverse sensitivity analysis

The problem of identifying parameters of time invariant linear dynamical systems with fractional derivative damping models, based on a spatially incomplete set of measured frequency response functions and experimentally determined eigensolutions, is considered. Methods based on inverse sensitivity analysis of damped eigensolutions and frequency response functions are developed. It is shown that the eigensensitivity method requires the development of derivatives of solutions of an asymmetric generalized eigenvalue problem. Both the first and second order inverse sensitivity analyses are considered. The study demonstrates the successful performance of the identification algorithms developed based on synthetic data on one, two and a 33 degrees of freedom vibrating systems with fractional dampers. Limited studies have also been conducted by combining finite element modeling with experimental data on accelerances measured in laboratory conditions on a system consisting of two steel beams rigidly joined together by a rubber hose. The method based on sensitivity of frequency response functions is shown to be more efficient than the eigensensitivity based method in identifying system parameters, especially for large scale systems.

Optimal Interconnections in the Design of Microprocessors and Digital Systems

This paper recasts the multiple data path assignment problem solved by Torng and Wilhelm by the dynamic programming method [1] into a minimal covering problem following a switching theoretic approach. The concept of bus compatibility for the data transfers is used to obtain the various ways of interconnecting the circuit modules with the minimum number of buses that allow concurrent data transfers. These have been called the feasible solutions of the problem. The minimal cost solutions are obtained by assigning weights to the bus-compatible sets present in the feasible solutions. Minimization of the cost of the solution by increasing the number of buses is also discussed.

Optimal Interconnections in the Design of Microprocessors and Digital Systems

This paper recasts the multiple data path assignment problem solved by Torng and Wilhelm by the dynamic programming method [1] into a minimal covering problem following a switching theoretic approach. The concept of bus compatibility for the data transfers is used to obtain the various ways of interconnecting the circuit modules with the minimum number of buses that allow concurrent data transfers. These have been called the feasible solutions of the problem. The minimal cost solutions are obtained by assigning weights to the bus-compatible sets present in the feasible solutions. Minimization of the cost of the solution by increasing the number of buses is also discussed.

Relationship between the controllability grammian and closed-loop eigenvalues: the single input case

The controllability grammian is important in many control applications. Given a set of closed-loop eigenvalues the corresponding controllability grammian can be obtained by computing the controller which assigns the eigenvalues and then by solving the Lyapunov equation that defines the grammian. The relationship between the controllability grammian, resulting from state feedback, and the closed-loop eigenvalues of a single input linear time invariant (LTI) system is obtained. The proposed methodology does not require the computation of the controller that assigns the specified eigenvalues. The closed-loop system matrix is obtained from the knowledge of the open-loop system matrix, control influence matrix and the specified closed-loop eigenvalues. Knowing the closed-loop system matrix, the grammian is then obtained from the solution of the Lyapunov equation that defines it. Finally the proposed idea is extended to find the state covariance matrix for a specified set of closed-loop eigenvalues (without computing the controller), due to impulsive input in the disturbance channel and to solve the eigenvalue assignment problem for the single input case.

BELIEF PROPAGATION FOR OPTIMAL EDGE COVER IN THE RANDOM COMPLETE GRAPH

We apply the objective method of Aldous to the problem of finding the minimum-cost edge cover of the complete graph with random independent and identically distributed edge costs. The limit, as the number of vertices goes to infinity, of the expected minimum cost for this problem is known via a combinatorial approach of Hessler and Wastlund. We provide a proof of this result using the machinery of the objective method and local weak convergence, which was used to prove the (2) limit of the random assignment problem. A proof via the objective method is useful because it provides us with more information on the nature of the edge's incident on a typical root in the minimum-cost edge cover. We further show that a belief propagation algorithm converges asymptotically to the optimal solution. This can be applied in a computational linguistics problem of semantic projection. The belief propagation algorithm yields a near optimal solution with lesser complexity than the known best algorithms designed for optimality in worst-case settings.

A Quasi-Newton Adaptive Algorithm for Generalized Symmetric Eigenvalue Problem

In this paper, we first recast the generalized symmetric eigenvalue problem, where the underlying matrix pencil consists of symmetric positive definite matrices, into an unconstrained minimization problem by constructing an appropriate cost function, We then extend it to the case of multiple eigenvectors using an inflation technique, Based on this asymptotic formulation, we derive a quasi-Newton-based adaptive algorithm for estimating the required generalized eigenvectors in the data case. The resulting algorithm is modular and parallel, and it is globally convergent with probability one, We also analyze the effect of inexact inflation on the convergence of this algorithm and that of inexact knowledge of one of the matrices (in the pencil) on the resulting eigenstructure. Simulation results demonstrate that the performance of this algorithm is almost identical to that of the rank-one updating algorithm of Karasalo. Further, the performance of the proposed algorithm has been found to remain stable even over 1 million updates without suffering from any error accumulation problems.

Generalized Burgers equations and Euler-Painleve transcendents. II

It was proposed earlier [P. L. Sachdev, K. R. C. Nair, and V. G. Tikekar, J. Math. Phys. 27, 1506 (1986)] that the Euler Painlevé equation yy[script `]+ay[script ']2+ f(x)yy[script ']+g(x) y2+by[script ']+c=0 represents the generalized Burgers equations (GBE's) in the same manner as Painlevé equations do the KdV type. The GBE was treated with a damping term in some detail. In this paper another GBE ut+uaux+Ju/2t =(gd/2)uxx (the nonplanar Burgers equation) is considered. It is found that its self-similar form is again governed by the Euler Painlevé equation. The ranges of the parameter alpha for which solutions of the connection problem to the self-similar equation exist are obtained numerically and confirmed via some integral relations derived from the ODE's. Special exact analytic solutions for the nonplanar Burgers equation are also obtained. These generalize the well-known single hump solutions for the Burgers equation to other geometries J=1,2; the nonlinear convection term, however, is not quadratic in these cases. This study fortifies the conjecture regarding the importance of the Euler Painlevé equation with respect to GBE's. Journal of Mathematical Physics is copyrighted by The American Institute of Physics.

Generalized Burgers equations and Euler-Painlev transcendents. I

Initial-value problems for the generalized Burgers equation (GBE) ut+u betaux+lambdaualpha =(delta/2)uxx are discussed for the single hump type of initial data both continuous and discontinuous. The numerical solution is carried to the self-similar ``intermediate asymptotic'' regime when the solution is given analytically by the self-similar form. The nonlinear (transformed) ordinary differential equations (ODE's) describing the self-similar form are generalizations of a class discussed by Euler and Painlevé and quoted by Kamke. These ODE's are new, and it is postulated that they characterize GBE's in the same manner as the Painlev equations categorize the Kortweg-de Vries (KdV) type. A connection problem for some related ODE's satisfying proper asymptotic conditions at x=±[infinity], is solved. The range of amplitude parameter is found for which the solution of the connection problem exists. The other solutions of the above GBE, which display several interesting features such as peaking, breaking, and a long shelf on the left for negative values of the damping coefficient lambda, are also discussed. The results are compared with those holding for the modified KdV equation with damping. Journal of Mathematical Physics is copyrighted by The American Institute of Physics.