Max-Coloring Paths: Tight Bounds and Extensions

The max-coloring problem is to compute a legal coloring of the vertices of a graph G = (V, E) with a non-negative weight function w on V such that Sigma(k)(i=1) max(v epsilon Ci) w(v(i)) is minimized, where C-1, ... , C-k are the various color classes. Max-coloring general graphs is as hard as the classical vertex coloring problem, a special case where vertices have unit weight. In fact, in some cases it can even be harder: for example, no polynomial time algorithm is known for max-coloring trees. In this paper we consider the problem of max-coloring paths and its generalization, max-coloring abroad class of trees and show it can be solved in time O(vertical bar V vertical bar+time for sorting the vertex weights). When vertex weights belong to R, we show a matching lower bound of Omega(vertical bar V vertical bar log vertical bar V vertical bar) in the algebraic computation tree model.

Popular Matchings with Variable Job Capacities

We consider the problem of matching people to jobs, where each person ranks a subset of jobs in an order of preference, possibly involving ties. There are several notions of optimality about how to best match each person to a job; in particular, popularity is a natural and appealing notion of optimality. However, popular matchings do not always provide an answer to the problem of determining an optimal matching since there are simple instances that do not adroit popular matchings. This motivates the following extension of the popular rnatchings problem:Given a graph G; = (A boolean OR J, E) where A is the set of people and J is the set of jobs, and a list < c(1), c(vertical bar J vertical bar)) denoting upper bounds on the capacities of each job, does there exist (x(1), ... , x(vertical bar J vertical bar)) such that setting the capacity of i-th, job to x(i) where 1 <= x(i) <= c(i), for each i, enables the resulting graph to admit a popular matching. In this paper we show that the above problem is NP-hard. We show that the problem is NP-hard even when each c is 1 or 2.

Al/SiC carriers for microwave integrated circuits by a new technique of pressureless infiltration

Materials with high thermal conductivity and thermal expansion coefficient matching with that of Si or GaAs are being used for packaging high density microcircuits due to their ability of faster heat dissipation. Al/SiC is gaining wide acceptance as electronic packaging material due to the fact that its thermal expansion coefficient can be tailored to match with that of Si or GaAs by varying the Al:SiC ratio while maintaining the thermal conductivity more or less the same. In the present work, Al/SiC microwave integrated circuit (MIC) carriers have been fabricated by pressureless infiltration of Al-alloy into porous SiC preforms in air. This new technique provides a cheaper alternative to pressure infiltration or pressureless infiltration in nitrogen in producing Al/SiC composites for electronic packaging applications. Al-alloy/65vol% SiC composite exhibited a coefficient of thermal expansion of 7 x 10(-6) K-1 (25 degrees C-100 degrees C) and a thermal conductivity of 147 Wm(-1) K-1 at 30 degrees C. The hysteresis observed in thermal expansion coefficient of the composite in the temperature range 100 degrees C-400 degrees C has been attributed to the presence of thermal residual stresses in the composite. Thermal diffusivity of the composite measured over the temperature range from 30 degrees C to 400 degrees C showed a 55% decrease in thermal diffusivity with temperature. Such a large decrease in thermal diffusivity with temperature could be due to the presence of micropores, microcracks, and decohesion of the Al/SiC interfaces in the microstructure (all formed during cooling from the processing temperature). The carrier showed satisfactory performance after integrating it into a MIC.

An Accurate Model For Interference From Spatially Distributed Shadowed Users in CDMA Uplinks

A detailed characterization of interference power statistics in CDMA systems is of considerable practical and theoretical interest. Such a characterization for uplink inter-cell interference has been difficult because of transmit power control, randomness in the number of interfering mobile stations, and randomness in their locations. We develop a new method to model the uplink inter-cell interference power as a lognormal distribution, and show that it is an order of magnitude more accurate than the conventional Gaussian approximation even when the average number of mobile stations per cell is relatively large and even outperforms the moment-matched lognormal approximation considered in the literature. The proposed method determines the lognormal parameters by matching its moment generating function with a new approximation of the moment generating function for the inter-cell interference. The method is tractable and exploits the elegant spatial Poisson process theory. Using several numerical examples, the accuracy of the proposed method in modeling the probability distribution of inter-cell interference is verified for both small and large values of interference.

Investigation of the effect of nonlocal scale on ultrasonic wave dispersion characteristics of a monolayer graphene

In this article, an ultrasonic wave propagation in graphene sheet is studied using nonlocal elasticity theory incorporating small scale effects. The graphene sheet is modeled as an isotropic plate of one-atom thick. For this model, the nonlocal governing differential equations of motion are derived from the minimization of the total potential energy of the entire system. An ultrasonic type of wave propagation model is also derived for the graphene sheet. The nonlocal scale parameter introduces certain band gap region in in-plane and flexural wave modes where no wave propagation occurs. This is manifested in the wavenumber plots as the region where the wavenumber tends to infinite or wave speed tends to zero. The frequency at which this phenomenon occurs is called the escape frequency. The explicit expressions for cutoff frequencies and escape frequencies are derived. The escape frequencies are mainly introduced because of the nonlocal elasticity. Obviously these frequencies are function of nonlocal scaling parameter. It has also been obtained that these frequencies are independent of y-directional wavenumber. It means that for any type of nanostructure, the escape frequencies are purely a function of nonlocal scaling parameter only. It is also independent of the geometry of the structure. It has been found that the cutoff frequencies are function of nonlocal scaling parameter (e(0)a) and the y-directional wavenumber (k(y)). For a given nanostructure, nonlocal small scale coefficient can be obtained by matching the results from molecular dynamics (MD) simulations and the nonlocal elasticity calculations. At that value of the nonlocal scale coefficient, the waves will propagate in the nanostructure at that cut-off frequency. In the present paper, different values of e(o)a are used. One can get the exact e(0)a for a given graphene sheet by matching the MD simulation results of graphene with the results presented in this paper. (C) 2010 Elsevier B.V. All rights reserved.

Performance Optimization of Induction Motor-Pump System Using Photovoltaic Energy Source

The optimization of a photovoltaic pumping system based on an induction motor driven pump that is powered by a solar array is presented in this paper. The motor-pump subsystem is analyzed from the point of view of optimizing the power requirement of the induction motor, which has led to an optimum u-f relationship useful in controlling the motor. The complete pumping system is implemented using a dc-dc converter, a three-phase inverter, and an induction motor-pump set. The dc-dc converter is used as a power conditioner and its duty cycle is controlled so as to match the load to the array. A microprocessor-based controller is used to carry out the load-matching.

Optimization of two-dimensional NMR by matched accumulation

It is well known that in the time-domain acquisition of NMR data, signal-to-noise (S/N) improves as the square root of the number of transients accumulated. However, the amplitude of the measured signal varies during the time of detection, having a functional form dependent on the coherence detected. Matching the time spent signal averaging to the expected amplitude of the signal observed should also improve the detected signal-to-noise. Following this reasoning, Barna et al. (J Magn. Reson.75, 384, 1987) demonstrated the utility of exponential sampling in one- and two-dimensional NMR, using maximum-entropy methods to analyze the data. It is proposed here that for two-dimensional experiments the exponential sampling be replaced by exponential averaging. The data thus collected can be analyzed by standard fast-Fourier-transform routines. We demonstrate the utility of exponential averaging in 2D NOESY spectra of the protein ubiquitin, in which an enhanced SIN is observed. It is also shown that the method acquires delayed double-quantum-filtered COSY without phase distortion.

Radiative interactions in boundary layers

A detailed description of radiative interactions in laminar compressible boundary layers for moderate Mach numbers is presented by way of asymptotic analysis and supporting solutions. The radiation field is described by the differential approximation. While the asymptotic analysis is valid for large N (the ratio of photon mean free path to molecular mean free path) and arbitrary Boltzmann number, Bo (the ratio of convective heat flux to radiation heat flux), the solutions are obtained for Bo [double less-than sign] 1, the case of strong radiative interactions. The asymptotic analysis shows the existence of an optically thin boundary layer for large N and all Bo. For Bo [double less-than sign] 1, two outer regions are observed — one optically thin (at short distances from the leading edge) and the other optically thick (at large distances from the leading edge). An interesting feature not pointed out in the previous literature is the existence of a wall layer at large distances from the leading edge where convective heat flux can be ignored to the leading order of approximation. The radiation field in all cases can be very well approximated by a one-dimensional description. The solutions have been constructed using the ideas of matched asymptotic expansions by approximate analytical procedures and numerical methods. It is shown that, to the leading order of approximation, the radiation slip method yields exactly the same result as the more complicated matching procedure. Both the cases of linear and nonlinear radiation have been considered, the former being of interest in developing approximate methods which are subsequently generalized to handle the nonlinear problem. Detailed results are presented for both cases.

Segmenting point-sampled surfaces

Extracting features from point-based representations of geometric surface models is becoming increasingly important for purposes such as model classification, matching, and exploration. In an earlier paper, we proposed a multiphase segmentation process to identify elongated features in point-sampled surface models without the explicit construction of a mesh or other surface representation. The preliminary results demonstrated the strength and potential of the segmentation process, but the resulting segmentations were still of low quality, and the segmentation process could be slow. In this paper, we describe several algorithmic improvements to overcome the shortcomings of the segmentation process. To demonstrate the improved quality of the segmentation and the superior time efficiency of the new segmentation process, we present segmentation results obtained for various point-sampled surface models. We also discuss an application of our segmentation process to extract ridge-separated features in point-sampled surfaces of CAD models.

Five-fold quasiperiodic tilings generated by inflated rhombuses with identical boundaries: possible application to the growth of quasicrystals

In order to generate normal Penrose tilings by inflation/deflation, decisions have to be made regarding the matching of the rhombuses/tilings with their neighbours. We show here that this decision-making problem can be avoided by adopting a deflation/inflation procedure which uses the decorated rhombuses with identical boundaries. The procedure enables both kinds of inflated rhombuses to match in any orientation along their edges. The tilings so generated are quasiperiodic. These structures appear to have a close relationship with the growth mechanism of quasicrystals.

Lenient Execution and Concurrent Execution of Re-entrant Routines: Efficient Implementation in Data Flow Systems

Implementation details of efficient schemes for lenient execution and concurrent execution of re-entrant routines in a data flow model have been discussed in this paper. The proposed schemes require no extra hardware support and utilise the existing hardware resources such as the Matching Unit and Memory Network Interface, effectively to achieve the above mentioned goals.

Analysis of reflection characteristics of a normal incidence plane wave on resonant sound absorbers: A finite element approach

Resonant sound absorbers are used widely as anechoic coatings in underwater applications. In this paper a finite element scheme based on the Galerkin technique is used to analyze the reflection characteristics of the resonant absorber when insonified by a normal incidence plane wave. A waveguide theory coupled with an impedance matching condition in the fluid is used to model the problem. It is shown in this paper that the fluid medium encompassing the absorber can be modeled as an elastic medium with equivalent Lamé constants. Quarter symmetry conditions within the periodic unit cell are exploited. The finite element results are compared with analytical results, and with results published elsewhere in the literature. It is shown in the process that meshing of the fluid domain can be obviated if the transmission coefficients or reflection coefficients only are desired as is often the case. Finally, some design curves for thin resonant absorbers with water closure are presented in this paper.

Popular matchings with variable item copies

We consider the problem of matching people to items, where each person ranks a subset of items in an order of preference, possibly involving ties. There are several notions of optimality about how to best match a person to an item; in particular, popularity is a natural and appealing notion of optimality. A matching M* is popular if there is no matching M such that the number of people who prefer M to M* exceeds the number who prefer M* to M. However, popular matchings do not always provide an answer to the problem of determining an optimal matching since there are simple instances that do not admit popular matchings. This motivates the following extension of the popular matchings problem: Given a graph G = (A U 3, E) where A is the set of people and 2 is the set of items, and a list < c(1),...., c(vertical bar B vertical bar)> denoting upper bounds on the number of copies of each item, does there exist < x(1),...., x(vertical bar B vertical bar)> such that for each i, having x(i) copies of the i-th item, where 1 <= xi <= c(i), enables the resulting graph to admit a popular matching? In this paper we show that the above problem is NP-hard. We show that the problem is NP-hard even when each c(i) is 1 or 2. We show a polynomial time algorithm for a variant of the above problem where the total increase in copies is bounded by an integer k. (C) 2011 Elsevier B.V. All rights reserved.

Perturbative corrections for staggered four-fermion operators

We present results for one-loop matching coefficients between continuum four-fermion operators, defined in the Naive Dimensional Regularization scheme, and staggered fermion operators of various types. We calculate diagrams involving gluon exchange between quark fines, and ''penguin'' diagrams containing quark loops. For the former we use Landau-gauge operators, with and without O(a) improvement, and including the tadpole improvement suggested by Lepage and Mackenzie. For the latter we use gauge-invariant operators. Combined with existing results for two-loop anomalous dimension matrices and one-loop matching coefficients, our results allow a lattice calculation of the amplitudes for KKBAR mixing and K --> pipi decays with all corrections of O(g2) included. We also discuss the mixing of DELTAS = 1 operators with lower dimension operators, and show that, with staggered fermions, only a single lower dimension operator need be removed by non-perturbative subtraction.

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.