Voting Paths

We consider a variant of the popular matching problem here. The input instance is a bipartite graph $G=(\mathcal{A}\cup\mathcal{P},E)$, where vertices in $\mathcal{A}$ are called applicants and vertices in $\mathcal{P}$ are called posts. Each applicant ranks a subset of posts in an order of preference, possibly involving ties. A matching $M$ is popular if there is no other matching $M'$ such that the number of applicants who prefer their partners in $M'$ to $M$ exceeds the number of applicants who prefer their partners in $M$ to $M'$. However, the “more popular than” relation is not transitive; hence this relation is not a partial order, and thus there need not be a maximal element here. Indeed, there are simple instances that do not admit popular matchings. The questions of whether an input instance $G$ admits a popular matching and how to compute one if it exists were studied earlier by Abraham et al. Here we study reachability questions among matchings in $G$, assuming that $G=(\mathcal{A}\cup\mathcal{P},E)$ admits a popular matching. A matching $M_k$ is reachable from $M_0$ if there is a sequence of matchings $\langle M_0,M_1,\dots,M_k\rangle$ such that each matching is more popular than its predecessor. Such a sequence is called a length-$k$ voting path from $M_0$ to $M_k$. We show an interesting property of reachability among matchings in $G$: there is always a voting path of length at most 2 from any matching to some popular matching. Given a bipartite graph $G=(\mathcal{A}\cup\mathcal{P},E)$ with $n$ vertices and $m$ edges and any matching $M_0$ in $G$, we give an $O(m\sqrt{n})$ algorithm to compute a shortest-length voting path from $M_0$ to a popular matching; when preference lists are strictly ordered, we have an $O(m+n)$ algorithm. This problem has applications in dynamic matching markets, where applicants and posts can enter and leave the market, and applicants can also change their preferences arbitrarily. After any change, the current matching may no longer be popular, in which case we are required to update it. However, our model demands that we switch from one matching to another only if there is consensus among the applicants to agree to the switch. Hence we need to update via a voting path that ends in a popular matching. Thus our algorithm has applications here.

Denoising signals corrupted by chaotic noise

We consider the problem of signal estimation where the observed time series is modeled as y(i) = x(i) + s(i) with {x(i)} being an orbit of a chaotic self-map on a compact subset of R-d and {s(i)} a sequence in R-d converging to zero. This model is motivated by experimental results in the literature where the ocean ambient noise and the ocean clutter are found to be chaotic. Making use of observations up to time n, we propose an estimate of s(i) for i < n and show that it approaches s(i) as n -> infinity for typical asymptotic behaviors of orbits. (C) 2010 Elsevier B.V. All rights reserved.

An approximate algorithm for the minimal vertex nested polygon problem

Given two simple polygons, the Minimal Vertex Nested Polygon Problem is one of finding a polygon nested between the given polygons having the minimum number of vertices. In this paper, we suggest efficient approximate algorithms for interesting special cases of the above using the shortest-path finding graph algorithms.

Transient signal detection using wigner-ville distribution and wavelet denoising

The problem of detecting an unknown transient signal in noise is considered. The SNR of the observed data is first enhanced using wavelet domain filter The output of the wavelet domain filter is then transformed using a Wigner-Ville transform,which separates the spectrum of the observed signal into narrow frequency bands. Each subband signal at the output of the Wigner-ville block is subjected kto wavelet based level dependent denoising (WBLDD)to supress colored noise A weighted sum of the absolute value of outputs of WBLDD is passed through an energy detector, whose output is used as test statistic to take the final decision. By assigning weights proportional to the energy of the corresponding subband signals, the proposed detector approximates a frequency domain matched filter Simulation results are presented to show that the performance of the proposed detector is better than that of the wavelet packet transform based detector.

Component Inventory Costs in an Assembly Problem with Uncertain Supplier Lead-Times

We present a generic study of inventory costs in a factory stockroom that supplies component parts to an assembly line. Specifically, we are concerned with the increase in component inventories due to uncertainty in supplier lead-times, and the fact that several different components must be present before assembly can begin. It is assumed that the suppliers of the various components are independent, that the suppliers' operations are in statistical equilibrium, and that the same amount of each type of component is demanded by the assembly line each time a new assembly cycle is scheduled to begin. We use, as a measure of inventory cost, the expected time for which an order of components must be held in the stockroom from the time it is delivered until the time it is consumed by the assembly line. Our work reveals the effects of supplier lead-time variability, the number of different types of components, and their desired service levels, on the inventory cost. In addition, under the assumptions that inventory holding costs and the cost of delaying assembly are linear in time, we study optimal ordering policies and present an interesting characterization that is independent of the supplier lead-time distributions.

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.

High-Rate,2-Group ML-Decodable STBCs for 2(m) Transmit Antennas

A Space-Time Block Code (STBC) in K-variables is said to be g-Group ML-Decodable (GMLD) if its Maximum-Likelihood (ML) decoding metric can be written as a sum of g independent terms, with each term being a function of a subset of the K variables. In this paper, a construction method to obtain high-rate, 2-GMLD STBCs for 2(m) transmit antennas, m > 1, is presented. The rate of the STBC obtained for 2(m) transmit antennas is 2(m-2) + 1/2(m), complex symbols per channel use. The design method is illustrated for the case of 4 and 8 transmit antennas. The code obtained for 4 transmit antennas is equivalent to the rate-5/4 Quasi-Orthogonal design (QOD) proposed by Yuen, Guan and Tjung.

The Proto-Lucianic Problem in 1 Samuel

The Lucianic text of the Septuagint of the Historical Books witnessed primarily by the manuscript group L (19, 82, 93, 108, and 127) consists of at least two strata: the recensional elements, which date back to about 300 C.E., and the substratum under these recensional elements, the proto-Lucianic text. Some distinctive readings in L seem to be supported by witnesses that antedate the supposed time of the recension. These witnesses include the biblical quotations of Josephus, Hippolytus, Irenaeus, Tertullian, and Cyprian, and the Old Latin translation of the Septuagint. It has also been posited that some Lucianic readings might go back to Hebrew readings that are not found in the Masoretic text but appear in the Qumran biblical texts. This phenomenon constitutes the proto-Lucianic problem. In chapter 1 the proto-Lucianic problem and its research history are introduced. Josephus references to 1 Samuel are analyzed in chapter 2. His agreements with L are few and are mostly only apparent or, at best, coincidental. In chapters 3 6 the quotations by four early Church Fathers are analyzed. Hippolytus Septuagint text is extremely hard to establish since his quotations from 1 Samuel have only been preserved in Armenian and Georgian translations. Most of the suggested agreements between Hippolytus and L are only apparent or coincidental. Irenaeus is the most trustworthy textual witness of the four early Church Fathers. His quotations from 1 Samuel agree with L several times against codex Vaticanus (B) and all or most of the other witnesses in preserving the original text. Tertullian and Cyprian agree with L in attesting some Hebraizing approximations that do not seem to be of Hexaplaric origin. The question is more likely of early Hebraizing readings of the same tradition as the kaige recension. In chapter 7 it is noted that Origen, although a pre-Lucianic Father, does not qualify as a proto-Lucianic witness. General observations about the Old Latin witnesses as well as an analysis of the manuscript La115 are given in chapter 8. In chapter 9 the theory of the proto-Lucianic recension is discussed. In order to demonstrate the existence of the proto-Lucianic recension one should find instances of indisputable agreement between the Qumran biblical manuscripts and L in readings that are secondary in Greek. No such case can be found in the Qumran material in 1 Samuel. In the text-historical conclusions (chapter 10) it is noted that of all the suggested proto-Lucianic agreements in 1 Samuel (about 75 plus 70 in La115) more than half are only apparent or, at best, coincidental. Of the indisputable agreements, however, 26 are agreements in the original reading. In about 20 instances the agreement is in a secondary reading. These agreements are early variants; mostly minor changes that happen all the time in the course of transmission. Four of the agreements, however, are in a pre-Hexaplaric Hebraizing approximation that has found its way independently into the pre-Lucianic witnesses and the Lucianic recension. The study aims at demonstrating the value of the Lucianic text as a textual witness: under the recensional layer(s) there is an ancient text that preserves very old, even original readings which have not been preserved in B and most of the other witnesses. The study also confirms the value of the early Church Fathers as textual witnesses.

A note on the porous-wavemaker problem

A complete analytical solution is obtained, by using an integral transform method, for the porous-wavemaker problem, when the effect of surface tension is taken into account on the free surface of water of finite-depth in which surface waves are produced by small horizontal oscillations of a porous vertical plate. The final results are expressed in the form of convergent integrals as well as series and known results are reproduced when surface tension is neglected.

Steady compressible flow of granular materials through a wedge-shaped hopper: The smooth wall, radial gravity problem

A continuum model based on the critical state theory of soil mechanics is used to generate stress and density profiles, and to compute discharge velocities for the plane flow of cohesionless materials. Two types of yield loci are employed, namely, a yield locus with a corner, and a smooth yield locus. The yield locus with a corner leads to computational difficulties. For the smooth yield locus, results are found to be relatively insensitive to the shape of the yield locus, the location of the upper traction-free surface and the density specified on this surface. This insensitivity arises from the existence of asymptotic stress and density fields, to which the solution tends to converge on moving down the hopper. Numerical and approximate analytical solutions are obtained for these fields and the latter is used to derive an expression for the discharge velocity. This relation predicts discharge velocities to within 13% of the exact (numerical) values. While the assumption of incompressibility has been frequently used in the literature, it is shown here that in some cases, this leads to discharge velocities which are significantly higher than those obtained by the incorporation of density variation.

On the Fekete-Szego problem for concave univalent functions

We consider the Fekete-Szego problem with real parameter lambda for the class Co(alpha) of concave univalent functions. (C) 2010 Elsevier Inc. All rights reserved.