Popular mixed matchings

We study the problem of matching applicants to jobs under one-sided preferences; that is, each applicant ranks a non-empty subset of jobs under an order of preference, possibly involving ties. A matching M is said to be more popular than T if the applicants that prefer M to T outnumber those that prefer T to M. A matching is said to be popular if there is no matching more popular than it. Equivalently, a matching M is popular if phi(M, T) >= phi(T, M) for all matchings T, where phi(X, Y) is the number of applicants that prefer X to Y. Previously studied solution concepts based on the popularity criterion are either not guaranteed to exist for every instance (e.g., popular matchings) or are NP-hard to compute (e.g., least unpopular matchings). This paper addresses this issue by considering mixed matchings. A mixed matching is simply a probability distribution over matchings in the input graph. The function phi that compares two matchings generalizes in a natural manner to mixed matchings by taking expectation. A mixed matching P is popular if phi(P, Q) >= phi(Q, P) for all mixed matchings Q. We show that popular mixed matchings always exist and we design polynomial time algorithms for finding them. Then we study their efficiency and give tight bounds on the price of anarchy and price of stability of the popular matching problem. (C) 2010 Elsevier B.V. All rights reserved.

Reverse flotation of silica from Kudremukh iron ore .2. Optimization of flotation process

An experimental programme based on statistical analysis was used for optimizing the reverse Rotation of silica from non-magnetic spiral preconcentrate of Kudremukh iron ore. Flotation of silica with amine and starch as the Rotation reagents was studied to estimate the optimum reagent levels at various mesh of grind. The experiments were first carried out using a two level three factor design. Analysis of the results showed that two parameters namely, the concentration level of the amine collector and the mesh of grind, were significant. Experiments based on an orthogonal design of the hexagonal type were then carried out to determine the effects of these two variables, on recovery and grade of the concentrate. Regression equations have been developed as models. Response contours have been plotted using the 'path of steepest ascent', maximum response has been optimized at 0.27 kg/ton of amine collector, 0.5 kg/ton of starch and mesh of grind of 48.7% passing 300 mesh to give a recovery of 83.43% of Fe in the concentrate containing 66.6% Fe and 2.17% SiO2.

Singularity structure of third-order dynamical systems .2

The singularity structure of the solutions of a general third-order system, with polynomial right-hand sides of degree less than or equal to two, is studied about a movable singular point, An algorithm for transforming the given third-order system to a third-order Briot-Bouquet system is presented, The dominant behavior of a solution of the given system near a movable singularity is used to construct a transformation that changes the given system directly to a third-order Briot-Bouquet system. The results of Horn for the third-order Briot-Bouquet system are exploited to give the complete form of the series solutions of the given third-order system; convergence of these series in a deleted neighborhood of the singularity is ensured, This algorithm is used to study the singularity structure of the solutions of the Lorenz system, the Rikitake system, the three-wave interaction problem, the Rabinovich system, the Lotka-Volterra system, and the May-Leonard system for different sets of parameter values. The proposed approach goes far beyond the ARS algorithm.

The existence of homeomorphic subgraphs in chordal graphs

We establish conditions for the existence, in a chordal graph, of subgraphs homeomorphic to K-n (n greater than or equal to 3), K-m,K-n (m,n greater than or equal to 2), and wheels W-r (r greater than or equal to 3). Using these results, we develop a simple linear time algorithm for testing planarity of chordal graphs. We also show how these results lead to simple polynomial time algorithms for the Fixed Subgraph Homeomorphism problem on chordal graphs for some special classes of pattern graphs.

Distributed intrusion detection in the presence of correlated sensor readings: Signal-space and communication-complexity view-point

The problem of sensor-network-based distributed intrusion detection in the presence of clutter is considered. It is argued that sensing is best regarded as a local phenomenon in that only sensors in the immediate vicinity of an intruder are triggered. In such a setting, lack of knowledge of intruder location gives rise to correlated sensor readings. A signal-space view-point is introduced in which the noise-free sensor readings associated to intruder and clutter appear as surfaces f(s) and f(g) and the problem reduces to one of determining in distributed fashion, whether the current noisy sensor reading is best classified as intruder or clutter. Two approaches to distributed detection are pursued. In the first, a decision surface separating f(s) and f(g) is identified using Neyman-Pearson criteria. Thereafter, the individual sensor nodes interactively exchange bits to determine whether the sensor readings are on one side or the other of the decision surface. Bounds on the number of bits needed to be exchanged are derived, based on communication-complexity (CC) theory. A lower bound derived for the two-party average case CC of general functions is compared against the performance of a greedy algorithm. Extensions to the multi-party case is straightforward and is briefly discussed. The average case CC of the relevant greaterthan (CT) function is characterized within two bits. Under the second approach, each sensor node broadcasts a single bit arising from appropriate two-level quantization of its own sensor reading, keeping in mind the fusion rule to be subsequently applied at a local fusion center. The optimality of a threshold test as a quantization rule is proved under simplifying assumptions. Finally, results from a QualNet simulation of the algorithms are presented that include intruder tracking using a naive polynomial-regression algorithm. 2010 Elsevier B.V. All rights reserved.

The Herzog-Vasconcelos conjecture for affine semigroup rings

Let S be a simplicial affine semigroup such that its semigroup ring A = k[S] is Buchsbaum. We prove for such A the Herzog-Vasconcelos conjecture: If the A-module Der(k)A of k-linear derivations of A has finite projective dimension then it is free and hence A is a polynomial ring by the well known graded case of the Zariski-Lipman conjecture.

Delay constrained optimal relay placement for planned wireless sensor networks

In this paper, we study the problem of wireless sensor network design by deploying a minimum number of additional relay nodes (to minimize network design cost) at a subset of given potential relay locationsin order to convey the data from already existing sensor nodes (hereafter called source nodes) to a Base Station within a certain specified mean delay bound. We formulate this problem in two different ways, and show that the problem is NP-Hard. For a problem in which the number of existing sensor nodes and potential relay locations is n, we propose an O(n) approximation algorithm of polynomial time complexity. Results show that the algorithm performs efficiently (in over 90% of the tested scenarios, it gave solutions that were either optimal or exceeding optimal just by one relay) in various randomly generated network scenarios.

Cyclic Prefix Based Cooperative Sequential Spectrum Sensing Algorithms for OFDM

This paper considers the problem of spectrum sensing in cognitive radio networks when the primary user is using Orthogonal Frequency Division Multiplexing (OFDM). For this we develop cooperative sequential detection algorithms that use the autocorrelation property of cyclic prefix (CP) used in OFDM systems. We study the effect of timing and frequency offset, IQ-imbalance and uncertainty in noise and transmit power. We also modify the detector to mitigate the effects of these impairments. The performance of the proposed algorithms is studied via simulations. We show that sequential detection can significantly improve the performance over a fixed sample size detector.

Training-Embedded, Single-Symbol ML-Decodable, Distributed STBCs for Relay Networks

Recently, a special class of complex designs called Training-Embedded Complex Orthogonal Designs (TE-CODs) has been introduced to construct single-symbol Maximum Likelihood decodable (SSD) distributed space-time block codes (DSTBCs) for two-hop wireless relay networks using the amplify and forward protocol. However, to implement DSTBCs from square TE-CODs, the overhead due to the transmission of training symbols becomes prohibitively large as the number of relays increase. In this paper, we propose TE-Coordinate Interleaved Orthogonal Designs (TE-CIODs) to construct SSD DSTBCs. Exploiting the block diagonal structure of TE-CIODs, we show that the overhead due to the transmission of training symbols to implement DSTBCs from TE-CIODs is smaller than that for TE-CODs. We also show that DSTBCs from TE-CIODs offer higher rate than those from TE-CODs for identical number of relays while maintaining the SSD and full-diversity properties.

BER Analysis of Uplink OFDMA in the Presence of Carrier Frequency and Timing Offsets on Rician Fading Channels

In uplink orthogonal frequency division multiple access (OFDMA), carrier frequency offsets (CFO) and/or timing offsets (TO) of other users with respect to a desired user can cause significant multiuser interference (MUI). In this paper, we derive an analytical bit error rate (BER) expression that quantify the degradation in BER due to the combined effect of both CFOs and TOs in uplink OFDMA on Rician fading channels. Such an analytical BER derivation for uplink OFDMA with CFOs and TOs on Rician fading channels has not been reported so far. For the case of non-zero CFOs/TOs, we obtain an approximate BER expression involving a single integral. Analytical and simulation BER results are shown to match very well.

Single real-symbol decodable, high-rate, distributed space-time block codes

A scheme to apply the rate-1 real orthogonal designs (RODs) in relay networks with single real-symbol decodability of the symbols at the destination for any arbitrary number of relays is proposed. In the case where the relays do not have any information about the channel gains from the source to themselves, the best known distributed space time block codes (DSTBCs) for k relays with single real-symbol decodability offer an overall rate of complex symbols per channel use. The scheme proposed in this paper offers an overall rate of 2/2+k complex symbol per channel use, which is independent of the number of relays. Furthermore, in the scenario where the relays have partial channel information in the form of channel phase knowledge, the best known DSTBCs with single real-symbol decodability offer an overall rate of 1/3 complex symbols per channel use. In this paper, making use of RODs, a scheme which achieves the same overall rate of 1/3 complex symbols per channel use but with a decoding delay that is 50 percent of that of the best known DSTBCs, is presented. Simulation results of the symbol error rate performance for 10 relays, which show the superiority of the proposed scheme over the best known DSTBC for 10 relays with single real-symbol decodability, are provided.

Improved large-MIMO detection based on damped belief propagation

In this paper, we consider the application of belief propagation (BP) to achieve near-optimal signal detection in large multiple-input multiple-output (MIMO) systems at low complexities. Large-MIMO architectures based on spatial multiplexing (V-BLAST) as well as non-orthogonal space-time block codes(STBC) from cyclic division algebra (CDA) are considered. We adopt graphical models based on Markov random fields (MRF) and factor graphs (FG). In the MRF based approach, we use pairwise compatibility functions although the graphical models of MIMO systems are fully/densely connected. In the FG approach, we employ a Gaussian approximation (GA) of the multi-antenna interference, which significantly reduces the complexity while achieving very good performance for large dimensions. We show that i) both MRF and FG based BP approaches exhibit large-system behavior, where increasingly closer to optimal performance is achieved with increasing number of dimensions, and ii) damping of messages/beliefs significantly improves the bit error performance.

Improved preprocessing methods for modulo scheduling algorithms

Instruction scheduling with an automaton-based resource conflict model is well-established for normal scheduling. Such models have been generalized to software pipelining in the modulo-scheduling framework. One weakness with existing methods is that a distinct automaton must be constructed for each combination of a reservation table and initiation interval. In this work, we present a different approach to model conflicts. We construct one automaton for each reservation table which acts as a compact encoding of all the conflict automata for this table, which can be recovered for use in modulo-scheduling. The basic premise of the construction is to move away from the Proebsting-Fraser model of conflict automaton to the Muller model of automaton modelling issue sequences. The latter turns out to be useful and efficient in this situation. Having constructed this automaton, we show how to improve the estimate of resource constrained initiation interval. Such a bound is always better than the average-use estimate. We show that our bound is safe: it is always lower than the true initiation interval. This use of the automaton is orthogonal to its use in modulo-scheduling. Once we generate the required information during pre-processing, we can compute the lower bound for a program without any further reference to the automaton.

Optimum design of a helicopter rotor for low vibration using aeroelastic analysis and response surface methods

An aeroelastic analysis based on finite elements in space and time is used to model the helicopter rotor in forward flight. The rotor blade is represented as an elastic cantilever beam undergoing flap and lag bending, elastic torsion and axial deformations. The objective of the improved design is to reduce vibratory loads at the rotor hub that are the main source of helicopter vibration. Constraints are imposed on aeroelastic stability, and move limits are imposed on the blade elastic stiffness design variables. Using the aeroelastic analysis, response surface approximations are constructed for the objective function (vibratory hub loads). It is found that second order polynomial response surfaces constructed using the central composite design of the theory of design of experiments adequately represents the aeroelastic model in the vicinity of the baseline design. Optimization results show a reduction in the objective function of about 30 per cent. A key accomplishment of this paper is the decoupling of the analysis problem and the optimization problems using response surface methods, which should encourage the use of optimization methods by the helicopter industry. (C) 2002 Elsevier Science Ltd. All rights reserved.

System Dy-Fe-O: thermodynamic properties of ternary oxides using Calvet calorimetry and solid-state electrochemical cell

The enthalpy increments and the standard molar Gibbs energies of formation-of DyFeO3(s) and Dy3Fe5O12(s) have been measured using a Calvet micro-calorimeter and a solid oxide galvanic cell, respectively. A co-operative phase transition, related to anti-ferromagnetic to paramagnetic transformation, is apparent. from the heat capacity data for DyFeO3 at similar to 648 K. A similar type of phase transition has been observed for Dy3Fe5O12 at similar to 560 K which is related to ferrimagnetic to paramagnetic transformation. Enthalpy increment data for DyFeO3(s) and Dy3Fe5O12(s), except in the vicinity of the second-order transition, can be represented by the following polynomial expressions:{H(0)m(T) - H(0)m(298.15 K)) (Jmol(-1)) (+/-1.1%) = -52754 + 142.9 x (T (K)) + 2.48 x 10(-3) x (T (K))(2) + 2.951 x 10(6) x (T (K))(-1); (298.15 less than or equal to T (K) less than or equal to 1000) for DyFeO3(s), and {H(0)m(T) - H(0)m(298.15 K)} (Jmol(-1)) (+/-1.2%) = -191048 + 545.0 x (T - (K)) + 2.0 x 10(-5) x (T (K))(2) + 8.513 x 10(6) x (T (K))(-1); (208.15 less than or equal to T (K) less than or equal to 1000)for Dy3Fe5O12(s). The reversible emfs of the solid-state electrochemical cells: (-)Pt/{DyFeO3(s) + Dy2O3(s) + Fe(s)}/YDT/CSZ//{Fe(s) + Fe0.95O(s)}/Pt(+) and (-)Pt/{Fe(s) + Fe0.95O(s)}//CSZ//{DyFeO3(s) + Dy3Fe5O12(s) + Fe3O4(s)}/Pt(+), were measured in the temperature range from 1021 to 1250 K and 1035 to 1250 K, respectively. The standard Gibbs energies of formation of solid DyFeO3 and Dy3Fe5O12 calculated by the least squares regression analysis of the data obtained in the present study, and data for Fe0.95O and Dy2O3 from the literature, are given by Delta(f)G(0)m(DyFeO3,s)(kJmol(-1))(+/-3.2)= -1339.9 + 0.2473 x (T(K)); (1021 less than or equal to T (K) less than or equal to 1548)and D(f)G(0)m(Dy3Fe5O12,s) (kJmol(-1)) (+/-3.5) = -4850.4 + 0.9846 x (T (K)); (1035 less than or equal to T (K) less than or equal to 1250) The uncertainty estimates for Delta(f)G(0)m include the standard deviation in the emf and uncertainty in the data taken from the literature. Based on the thermodynamic information, oxygen potential diagram and chemical potential diagrams for the system Dy-Fe-O were developed at 1250 K. (C) 2002 Editions scientifiques et medicales Elsevier SAS. All rights reserved.