Distributed algorithms for edge dominating sets

An edge dominating set for a graph G is a set D of edges such that each edge of G is in D or adjacent to at least one edge in D. This work studies deterministic distributed approximation algorithms for finding minimum-size edge dominating sets. The focus is on anonymous port-numbered networks: there are no unique identifiers, but a node of degree d can refer to its neighbours by integers 1, 2, ..., d. The present work shows that in the port-numbering model, edge dominating sets can be approximated as follows: in d-regular graphs, to within 4 − 6/(d + 1) for an odd d and to within 4 − 2/d for an even d; and in graphs with maximum degree Δ, to within 4 − 2/(Δ − 1) for an odd Δ and to within 4 − 2/Δ for an even Δ. These approximation ratios are tight for all values of d and Δ: there are matching lower bounds.

An optimal local approximation algorithm for max-min linear programs

In a max-min LP, the objective is to maximise ω subject to Ax ≤ 1, Cx ≥ ω1, and x ≥ 0 for nonnegative matrices A and C. We present a local algorithm (constant-time distributed algorithm) for approximating max-min LPs. The approximation ratio of our algorithm is the best possible for any local algorithm; there is a matching unconditional lower bound.

Analysing local algorithms in location-aware quasi-unit-disk graphs

A local algorithm with local horizon r is a distributed algorithm that runs in r synchronous communication rounds; here r is a constant that does not depend on the size of the network. As a consequence, the output of a node in a local algorithm only depends on the input within r hops from the node. We give tight bounds on the local horizon for a class of local algorithms for combinatorial problems on unit-disk graphs (UDGs). Most of our bounds are due to a refined analysis of existing approaches, while others are obtained by suggesting new algorithms. The algorithms we consider are based on network decompositions guided by a rectangular tiling of the plane. The algorithms are applied to matching, independent set, graph colouring, vertex cover, and dominating set. We also study local algorithms on quasi-UDGs, which are a popular generalisation of UDGs, aimed at more realistic modelling of communication between the network nodes. Analysing the local algorithms on quasi-UDGs allows one to assume that the nodes know their coordinates only approximately, up to an additive error. Despite the localisation error, the quality of the solution to problems on quasi-UDGs remains the same as for the case of UDGs with perfect location awareness. We analyse the increase in the local horizon that comes along with moving from UDGs to quasi-UDGs.

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.

High-precision diode-laser-based temperature measurement for air refractive index compensation

We present a laser-based system to measure the refractive index of air over a long path length. In optical distance measurements it is essential to know the refractive index of air with high accuracy. Commonly, the refractive index of air is calculated from the properties of the ambient air using either Ciddor or Edlén equations, where the dominant uncertainty component is in most cases the air temperature. The method developed in this work utilises direct absorption spectroscopy of oxygen to measure the average temperature of air and of water vapor to measure relative humidity. The method allows measurement of temperature and humidity over the same beam path as in optical distance measurement, providing spatially well matching data. Indoor and outdoor measurements demonstrate the effectiveness of the method. In particular, we demonstrate an effective compensation of the refractive index of air in an interferometric length measurement at a time-variant and spatially non-homogenous temperature over a long time period. Further, we were able to demonstrate 7 mK RMS noise over a 67 m path length using 120 s sample time. To our knowledge, this is the best temperature precision reported for a spectroscopic temperature measurement.

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.

Carotid Surgery : A posse ad esse non valet consequentia

According to a large body of evidence, carotid endarterectomy (CEA) can prevent strokes, provided that appropriate inclusion criteria and high-quality perioperative treatment methods are utilised with low complication rates. From the patient s perspective, it is of paramount importance that the operation is as safe and effective as possible. From the community s point of view, it is important that CEA provision prevents as many strokes as possible. In order to define the stroke preventing potential of CEA in different communities, a comparison between eight European countries and Australia was performed including 53 077 carotid interventions. A more detailed evaluation was performed in Finland, the United Kingdom and Egypt. It could be estimated that many potentially preventable strokes occur due to insufficient diagnostics and CEA provision. The number of CEAs should be at least doubled in the Helsinki region. The theoretical power of CEA provision in stroke prevention varied significantly between the countries. Delay from symptom to surgery has been identified as one of the most important factors influencing the effectiveness of CEA. In 2008 only 11% of CEAs in Helsinki university central hospital (HUCH) were performed within the recommended14 days. Registered data of 673 CEAs in HUCH during 2000-2005 was analyzed. There was no systematic error that would have changed the outcome analysis. However it is important that registers are audited regularly and cross matching of different registries is possible. A previously unpublished method of combining medial mandibulotomy, neck incision and carotid artery interposition was carried out as a collaboration of maxillofacial, ear, nose and throat and vascular surgeons. Five patients were operated on with a technique that was feasible and possible to perform with little morbidity, but due to the significant risks involved, this technique should be reserved for carefully selected cases. In stroke prevention, organisational decisions seem far more important than details in interventional procedures when CEA is performed with low complication rates, as was the case in the present study. A TIA clinic approach with close co-operation between the on-call vascular surgeons, neurologists and radiologists should be available at all centres treating these patients. Patients should have a direct and fast admission to the hospital performing CEA.

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.

Turbulent near-wake development behind a flat plate

An asymptotic analysis of the two-dimensional turbulent near-wake flow behind a Rat plate with sharp trailing edge has been formulated, The feature that the near-wake, which is dominated by the mixing of the oncoming turbulent boundary layers retains, to a large extent, the memory of the turbulent structure of the upstream boundary layer has been exploited to develop the analysis. This analysis leads to two regions of the near-wake flow (the inner near-wake and the outer near-wake) for which the governing equations are derived. The matching conditions among these regions lead to a logarithmic variation in the normal direction in the overlapping region surrounding the inner near-wake. These features are validated by the available experimental data. Similarity solutions for the velocity distribution (which satisfy the required matching conditions) in the inner near-wake and outer near-wake regions have been obtained by making the appropriate eddy-viscosity assumptions, Uniformly valid solutions for velocity distribution have been constructed for the near-wake. The solutions show good agreement with available experimental data. (C) Elsevier, Paris.

Context based service discovery for ubiquitous applications

Service discovery is vital in ubiquitous applications, where a large number of devices and software components collaborate unobtrusively and provide numerous services without user intervention. Existing service discovery schemes use a service matching process in order to offer services of interest to the users. Potentially, the context information of the users and surrounding environment can be used to improve the quality of service matching. To make use of context information in service matching, a service discovery technique needs to address certain challenges. Firstly, it is required that the context information shall have unambiguous representation. Secondly, the devices in the environment shall be able to disseminate high level and low level context information seamlessly in the different networks. And thirdly, dynamic nature of the context information be taken into account. We propose a C-IOB(Context-Information, Observation and Belief) based service discovery model which deals with the above challenges by processing the context information and by formulating the beliefs based on the observations. With these formulated beliefs the required services will be provided to the users. The method has been tested with a typical ubiquitous museum guide application over different cases. The simulation results are time efficient and quite encouraging.

Incremental-angle and angular velocity estimation using a star sensor

A method is described for estimating the incremental angle and angular velocity of a spacecraft using integrated rate parameters with the help of a star sensor alone. The chief advantage of this method is that the measured stars need not be identified, whereas the identification of the stars is necessary in earlier methods. This proposed estimation can be carried out with all of the available measurements by a simple linear Kalman filter, albeit with a time-varying sensitivity matrix. The residuals of estimated angular velocity by the proposed spacecraft incremental-angle and angular velocity estimation method are as accurate as the earlier methods. This method also enables the spacecraft attitude to be reconstructed for mapping the stars into an imaginary unit sphere in the body reference frame, which will preserve the true angular separation of the stars. This will pave the way for identification of the stars using any angular separation or triangle matching techniques applied to even a narrow field of view sensor that is made to sweep the sky. A numerical simulation for inertial as well as Earth pointing spacecraft is carried out to establish the results.