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.

Modeling and Forecasting Implied Volatility: Implications for Trading, Pricing, and Risk Management

Modeling and forecasting of implied volatility (IV) is important to both practitioners and academics, especially in trading, pricing, hedging, and risk management activities, all of which require an accurate volatility. However, it has become challenging since the 1987 stock market crash, as implied volatilities (IVs) recovered from stock index options present two patterns: volatility smirk(skew) and volatility term-structure, if the two are examined at the same time, presents a rich implied volatility surface (IVS). This implies that the assumptions behind the Black-Scholes (1973) model do not hold empirically, as asset prices are mostly influenced by many underlying risk factors. This thesis, consists of four essays, is modeling and forecasting implied volatility in the presence of options markets’ empirical regularities. The first essay is modeling the dynamics IVS, it extends the Dumas, Fleming and Whaley (DFW) (1998) framework; for instance, using moneyness in the implied forward price and OTM put-call options on the FTSE100 index, a nonlinear optimization is used to estimate different models and thereby produce rich, smooth IVSs. Here, the constant-volatility model fails to explain the variations in the rich IVS. Next, it is found that three factors can explain about 69-88% of the variance in the IVS. Of this, on average, 56% is explained by the level factor, 15% by the term-structure factor, and the additional 7% by the jump-fear factor. The second essay proposes a quantile regression model for modeling contemporaneous asymmetric return-volatility relationship, which is the generalization of Hibbert et al. (2008) model. The results show strong negative asymmetric return-volatility relationship at various quantiles of IV distributions, it is monotonically increasing when moving from the median quantile to the uppermost quantile (i.e., 95%); therefore, OLS underestimates this relationship at upper quantiles. Additionally, the asymmetric relationship is more pronounced with the smirk (skew) adjusted volatility index measure in comparison to the old volatility index measure. Nonetheless, the volatility indices are ranked in terms of asymmetric volatility as follows: VIX, VSTOXX, VDAX, and VXN. The third essay examines the information content of the new-VDAX volatility index to forecast daily Value-at-Risk (VaR) estimates and compares its VaR forecasts with the forecasts of the Filtered Historical Simulation and RiskMetrics. All daily VaR models are then backtested from 1992-2009 using unconditional, independence, conditional coverage, and quadratic-score tests. It is found that the VDAX subsumes almost all information required for the volatility of daily VaR forecasts for a portfolio of the DAX30 index; implied-VaR models outperform all other VaR models. The fourth essay models the risk factors driving the swaption IVs. It is found that three factors can explain 94-97% of the variation in each of the EUR, USD, and GBP swaption IVs. There are significant linkages across factors, and bi-directional causality is at work between the factors implied by EUR and USD swaption IVs. Furthermore, the factors implied by EUR and USD IVs respond to each others’ shocks; however, surprisingly, GBP does not affect them. Second, the string market model calibration results show it can efficiently reproduce (or forecast) the volatility surface for each of the swaptions markets.

Simulating and Forecasting the Demand for New Consumer Durables

A diffusion/replacement model for new consumer durables designed to be used as a long-term forecasting tool is developed. The model simulates new demand as well as replacement demand over time. The model is called DEMSIM and is built upon a counteractive adoption model specifying the basic forces affecting the adoption behaviour of individual consumers. These forces are the promoting forces and the resisting forces. The promoting forces are further divided into internal and external influences. These influences are operationalized within a multi-segmental diffusion model generating the adoption behaviour of the consumers in each segment as an expected value. This diffusion model is combined with a replacement model built upon the same segmental structure as the diffusion model. This model generates, in turn, the expected replacement behaviour in each segment. To be able to use DEMSIM as a forecasting tool in early stages of a diffusion process estimates of the model parameters are needed as soon as possible after product launch. However, traditional statistical techniques are not very helpful in estimating such parameters in early stages of a diffusion process. To enable early parameter calibration an optimization algorithm is developed by which the main parameters of the diffusion model can be estimated on the basis of very few sales observations. The optimization is carried out in iterative simulation runs. Empirical validations using the optimization algorithm reveal that the diffusion model performs well in early long-term sales forecasts, especially as it comes to the timing of future sales peaks.

Comparison of ANN models for predicting water quality in distribution systems

Deterministic models have been widely used to predict water quality in distribution systems, but their calibration requires extensive and accurate data sets for numerous parameters. In this study, alternative data-driven modeling approaches based on artificial neural networks (ANNs) were used to predict temporal variations of two important characteristics of water quality chlorine residual and biomass concentrations. The authors considered three types of ANN algorithms. Of these, the Levenberg-Marquardt algorithm provided the best results in predicting residual chlorine and biomass with error-free and ``noisy'' data. The ANN models developed here can generate water quality scenarios of piped systems in real time to help utilities determine weak points of low chlorine residual and high biomass concentration and select optimum remedial strategies.

Effect of interaction of macrocracks on the stress intensity factor in a beam

Beams with a central edge crack, as well as other noncentral vertical and inclined edge cracks distributed symmetrically, subjected to three-point as well as four-point bending, are analysed using the finite element technique. Values of stress intensity factor K1 at the central crack tip for a crack-to-beam depth ratio Image equal to 0.5, are calculated for various cracked-beam configurations, using the compliance calibration technique as well as method of strain energy release rate. These are compared with the value of K1 for the case of a beam with central edge crack alone. Results of the present parametric study are used to specify the range of values pertaining to basic parameters such as crack-to-beam depth ratios, geometry and position with respect to central edge crack, of other macrocracks for which interaction exists. Accordingly, the macrocracks are classified as either interacting or noninteracting types. Hence for noninteracting types of cracks, analytical expressions available for the determination of K1 in the case of beam with a central edge crack alone, are applicable.

Development of a low-cost portable colorimeter for the estimation of fluoride in drinking water

People in many countries are affected by fluorosis owing to the high levels of fluoride in drinking water. An inexpensive method for estimating the concentration of the fluoride ion in drinking water would be helpful in identifying safe sources of water and also in monitoring the performance of defluoridation techniques. For this purpose, a simple, inexpensive, and portable colorimeter has been developed in the present work. It is used in conjunction with the SPADNS method, which shows a color change in the visible region on addition of water containing fluoride to a reagent solution. Groundwater samples were collected from different parts of the state of Karnataka, India and analysed for fluoride. The results obtained using the colorimeter and the double beam spectrophotometer agreed fairly well. The costs of the colorimeter and of the chemicals required per test were about Rs. 250 (US$ 5) and Rs. 2.5 (US$ 0.05), respectively. In addition, the cost of the chemicals required for constructing the calibration curve was about Rs. 15 (US$ 0.3). (C) 2010 Elsevier B.V. All rights reserved.

A pulsed field gradient spin echo NMR spectrometer for diffusion coefficient measurements

A pulsed field gradient spin echo NMR spectrometer has been assembled by interfacing a programmable pulse generator and a data acquisition system designed and fabricated in our laboratory with other imported units. Calibration results of the magnetic field gradients are presented.

Change detection and controlling forest information using multi-temporal Landsat TM imagery.

A method was developed for relative radiometric calibration of single multitemporal Landsat TM image, several multitemporal images covering each others, and several multitemporal images covering different geographic locations. The radiometricly calibrated difference images were used for detecting rapid changes on forest stands. The nonparametric Kernel method was applied for change detection. The accuracy of the change detection was estimated by inspecting the image analysis results in field. The change classification was applied for controlling the quality of the continuously updated forest stand information. The aim was to ensure that all the manmade changes and any forest damages were correctly updated including the attribute and stand delineation information. The image analysis results were compared with the registered treatments and the stand information base. The stands with discrepancies between these two information sources were recommended to be field inspected.

Estimation of soil hydraulic properties and their uncertainty: comparison between laboratory and field experiment

Often the soil hydraulic parameters are obtained by the inversion of measured data (e.g. soil moisture, pressure head, and cumulative infiltration, etc.). However, the inverse problem in unsaturated zone is ill-posed due to various reasons, and hence the parameters become non-unique. The presence of multiple soil layers brings the additional complexities in the inverse modelling. The generalized likelihood uncertainty estimate (GLUE) is a useful approach to estimate the parameters and their uncertainty when dealing with soil moisture dynamics which is a highly non-linear problem. Because the estimated parameters depend on the modelling scale, inverse modelling carried out on laboratory data and field data may provide independent estimates. The objective of this paper is to compare the parameters and their uncertainty estimated through experiments in the laboratory and in the field and to assess which of the soil hydraulic parameters are independent of the experiment. The first two layers in the field site are characterized by Loamy sand and Loamy. The mean soil moisture and pressure head at three depths are measured with an interval of half hour for a period of 1 week using the evaporation method for the laboratory experiment, whereas soil moisture at three different depths (60, 110, and 200 cm) is measured with an interval of 1 h for 2 years for the field experiment. A one-dimensional soil moisture model on the basis of the finite difference method was used. The calibration and validation are approximately for 1 year each. The model performance was found to be good with root mean square error (RMSE) varying from 2 to 4 cm(3) cm(-3). It is found from the two experiments that mean and uncertainty in the saturated soil moisture (theta(s)) and shape parameter (n) of van Genuchten equations are similar for both the soil types. Copyright (C) 2010 John Wiley & Sons, Ltd.

Optimal Use of Treatment Modalities and Treatment Results of Osteosarcoma and Soft Tissue Sarcomas

Soft tissue sarcomas are malignant tumours of mesenchymal origin. Because of infiltrative growth pattern, simple enucleation of the tumour causes a high rate of local recurrence. Instead, these tumours should be resected with a rim of normal tissue around the tumour. Data on the adequate margin width are scarce. At Helsinki University Central Hospital (HUCH) a multidisciplinary treatment group started in 1987. Surgical resection with a wide margin (2.5 cm) is the primary aim. In case of narrower margin radiation therapy is necessary. The role of adjuvant chemotherapy remains unclear. Our aims were to study local control by the surgical margin and to develop a new prognostic tool to aid decision-making on which patients should receive adjuvant chemotherapy. Patients with soft tissue sarcoma of the extremity or the trunk wall referred to HUCH during 1987-2002 form material in Studies I and II. External validation material comes from the Lund university sarcoma registry. The smallest surgical margin of at least 2.5 centimetres yielded local control of 89 per cent at five years. Amputation rate was 9 per cent. The proposed prognostic model with necrosis, vascular invasion, size on a continuous scale, depth, location and grade worked well both in Helsinki material and in the validation material, and it also showed good calibration. Based on the present study, we recommend the smallest surgical margin of 2-3 centimetres in soft tissue sarcoma irrespective of grade. Improvement in local control was present but modest in margins wider than 1 centimetre. In cases where gaining a wider margin would lead to a considerable loss of function, smaller margin is to be considered combined to radiation therapy. Patients treated with inadequate margins should be offered radiation therapy irrespective of tumour grade. Our new prognostic model to estimate 10-year survival probability in patients with soft tissue sarcoma of the extremities or trunk wall showed good dicscrimination and calibration. For time being the prognostic model is available for scientific use and further validations. In the future, the model may aid in clinical decision-making. For operable osteosarcoma, neoadjuvant multidrug chemotherapy followed by delayed surgery and multidrug adjuvant chemotherapy is the treatment of choice. Overall survival rates at five years are approximately 75 per cent in modern trials with classical osteosarcoma. All patients diagnosed and reported to the Finnish Cancer Registry with osteosarcoma in Finland during 1971-2005 form the material in Studies III and IV. Limb-salvage rate increased from 23 per cent to 78 per cent during 1971-2005. The 10-year sarcoma-specific survival for the whole study population improved from 32 per cent to 62 per cent. It was 75 per cent for patients with a local high-grade osteosarcoma of the extremity diagnosed during 1991-2005. This study outlines the improved prognosis of osteosarcoma patients in Finland with modern chemotherapy. The 10-year survival rates are good also in an international scale. Nonetheless, their limb-salvage rate remains inferior to those seen for highly selected patient series. Overall, the centralisation of osteosarcoma treatment would most likely improve both survival and limb-salvage rates even further.

Una gramática descriptiva del chabacano de Ternate

This dissertation is a descriptive grammar of Ternate Chabacano, a Spanish-lexifier Creole spoken by 3.000 people in the town of Ternate, Philippines. The dissertation offers an analysis of the phonological, morphological, and syntactic system of the language. It includes an overview of the historical background, the current situation of the speech community and a collection of annotated texts. Ternate Chabacano shares many characteristics with its main adstrate language Tagalog as well as the dialectal varieties of Spanish. At present, English also exerts an influence, nevertheless mainly affecting its lexicon. The description offered is based on fieldwork conducted in Ternate. Spoken language collected through thematic interviews forms the main type of the material analysed. Information regarding the informants and text types is included in the examples. Ternate Chabacano has a five-vowel system and 17 consonant phonemes. The morphology of the language is largely isolating. Clitics are used extensively for expressing adverbial relations. The verbal system is based on the preverbal markers that express the category of tense, modality and aspect, among which aspect is the main dimension. Complex predicates and verbal chains are used in order to further distinguish aspect and modality, as well as changes of voice and valency. Intransitive verbs express motion, states, and reflexive actions, even though the majority of verbs can occur in both intransitive and transitive clauses. Ternate Chabacano is a nominative-accusative type language but the typological configuration of the Philippine languages influences the marking of its constituents. A case in point is constituted by the nominal determination system. The basic constituent order in a clause is VSO. Equative and attibutive clauses are formed by juxtaposition while the locative clauses feature a copula. Indefinite terms are expressed through existential constructions. The negation of existential clauses differs from standard negation but both are intensified in the same way. In spoken discourse, tag-questions are common. Pragmatic elements and social formulas reflect largely the corresponding Tagalog expressions. Coordination and subordination occur typically without overt markers but a variety of markers exists for expressing different relations, especially those made explicit by adverbial clauses. Verbal chains form a continuum from serial verbs to complementation and ultimately to coordination.

A simple computational model for predicting .pi.-facial selectivity in reductions of sterically unbiased ketones. Relative importance of electrostatic and orbital interactions

Various factore controlling the preferred facial selectivity in the reductions of a number of sterically unbiased ketones have been evaluated using a semiempirical MO procedure. MNDO optimized geometries do not reveal any significant ground-state distortions which can be correlated with the observed face selectivities. Electrostatic effecta due to an approaching reagent were modeled by placing a test negative charge at a fixed distance from the carbonyl carbon on each of the two faces. A second series of calculations was carried out using the hydride ion as a test nucleophile. The latter calculations effectively include orbital interactions involving the u and u* orbitals of the newly formed bond in the reaction. The computed energy differences with the charge model are generally much larger compared to those with the hydride ion. However, both models lead to predictions which are qualitatively consistent with the experimentally determined facial preferences for most of the systems. Thus, electrostatic interactions between the nucleophile and the substrate seem to effectively determine the face selectivities in these molecules. However, there are a few exceptions in which orbital interactions are found to contribute significantly and occasionally reverse the preference dictated by electrostatic effecta. The remarkable succew of the hydride model calculations, in spite of retaining the unperturbed geometries of the substrates, points to the unimportance of torsional effeds and orbital distortions associated with the pyramidalized carbonyl unit in the transition state in most of the substrates considered. Additional experimental results are reported which provide useful calibration for the present computational approach.

Boxicity and Poset Dimension

Let G be a simple, undirected, finite graph with vertex set V(G) and edge set E(C). A k-dimensional box is a Cartesian product of closed intervals a(1), b(1)] x a(2), b(2)] x ... x a(k), b(k)]. The boxicity of G, box(G) is the minimum integer k such that G can be represented as the intersection graph of k-dimensional boxes, i.e. each vertex is mapped to a k-dimensional box and two vertices are adjacent in G if and only if their corresponding boxes intersect. Let P = (S, P) be a poset where S is the ground set and P is a reflexive, anti-symmetric and transitive binary relation on S. The dimension of P, dim(P) is the minimum integer l such that P can be expressed as the intersection of t total orders. Let G(P) be the underlying comparability graph of P. It is a well-known fact that posets with the same underlying comparability graph have the same dimension. The first result of this paper links the dimension of a poset to the boxicity of its underlying comparability graph. In particular, we show that for any poset P, box(G(P))/(chi(G(P)) - 1) <= dim(P) <= 2box(G(P)), where chi(G(P)) is the chromatic number of G(P) and chi(G(P)) not equal 1. The second result of the paper relates the boxicity of a graph G with a natural partial order associated with its extended double cover, denoted as G(c). Let P-c be the natural height-2 poset associated with G(c) by making A the set of minimal elements and B the set of maximal elements. We show that box(G)/2 <= dim(P-c) <= 2box(G) + 4. These results have some immediate and significant consequences. The upper bound dim(P) <= 2box(G(P)) allows us to derive hitherto unknown upper bounds for poset dimension. In the other direction, using the already known bounds for partial order dimension we get the following: (I) The boxicity of any graph with maximum degree Delta is O(Delta log(2) Delta) which is an improvement over the best known upper bound of Delta(2) + 2. (2) There exist graphs with boxicity Omega(Delta log Delta). This disproves a conjecture that the boxicity of a graph is O(Delta). (3) There exists no polynomial-time algorithm to approximate the boxicity of a bipartite graph on n vertices with a factor of O(n(0.5-epsilon)) for any epsilon > 0, unless NP=ZPP.

Sputtered thin-film strain gauges for differential pressure measurement

A differential pressure transducer with sputtered gold films as strain gauges has been designed and fabricated. The construction details of the sensing element assembly are given. The details of the strain gauge film configuration employed and the thin-film deposition process are also presented. Information on the output characteristics of the differential pressure transducer such as effect of pressure cycles on output, thermal stability, bidirectional calibration results obtained and individual gauge stability is reported.

Enhanced sensitivity for the differential pulse polarographic determination of molybdenum(VI) based on adsorption catalytic current

A differential pulse polarographic (DPP) method based on the adsorption catalytic current in a medium containing chlorate and 8-hydroxyquinoline (oxine) is suggested for the determination of molybdenum(VI). Experimental conditions such as pH and the composition of supporting electrolyte have been optimized to get a linear calibration graph at trace levels of Mo(VI). The sensitivity for molybdenum can be considerably enhanced by this method. The influence of possible interferences on the catalytic current has been investigated. The sensitivity of the method is compared with those obtained for other DPP methods for molybdenum. A detection limit of 1.0 x 10(-8) mol/L has been found.