The analysis of approximate quickselect and related problems

Approximate Quickselect, a simple modification of the well known Quickselect algorithm for selection, can be used to efficiently find an element with rank k in a given range [i..j], out of n given elements. We study basic cost measures of Approximate Quickselect by computing exact and asymptotic results for the expected number of passes, comparisons and data moves during the execution of this algorithm. The key element appearing in the analysis of Approximate Quickselect is a trivariate recurrence that we solve in full generality. The general solution of the recurrence proves to be very useful, as it allows us to tackle several related problems, besides the analysis that originally motivated us. In particular, we have been able to carry out a precise analysis of the expected number of moves of the ith element when selecting the jth smallest element with standard Quickselect, where we are able to give both exact and asymptotic results. Moreover, we can apply our general results to obtain exact and asymptotic results for several parameters in binary search trees, namely the expected number of common ancestors of the nodes with rank i and j, the expected size of the subtree rooted at the least common ancestor of the nodes with rank i and j, and the expected distance between the nodes of ranks i and j.

An approximate mathematical model for solidification of a flowing liquid in a microchannel

A mathematical model is developed to analyse the combined flow and solidification of a liquid in a small pipe or two-dimensional channel. In either case the problem reduces to solving a single equation for the position of the solidification front. Results show that for a large range of flow rates the closure time is approximately constant, and the value depends primarily on the wall temperature and channel width. However, the ice shape at closure will be very different for low and high fluxes. As the flow rate increases the closure time starts to depend on the flow rate until the closure time increases dramatically, subsequently the pipe will never close.

An approximate solution method for boundary layer flow of a power law fluid over a flat plate

The work in this paper deals with the development of momentum and thermal boundary layers when a power law fluid flows over a flat plate. At the plate we impose either constant temperature, constant flux or a Newton cooling condition. The problem is analysed using similarity solutions, integral momentum and energy equations and an approximation technique which is a form of the Heat Balance Integral Method. The fluid properties are assumed to be independent of temperature, hence the momentum equation uncouples from the thermal problem. We first derive the similarity equations for the velocity and present exact solutions for the case where the power law index n = 2. The similarity solutions are used to validate the new approximation method. This new technique is then applied to the thermal boundary layer, where a similarity solution can only be obtained for the case n = 1.

The curvature of the conical intersection seam: an approximate second-order analysis

We present a method for analyzing the curvature (second derivatives) of the conical intersection hyperline at an optimized critical point. Our method uses the projected Hessians of the degenerate states after elimination of the two branching space coordinates, and is equivalent to a frequency calculation on a single Born-Oppenheimer potential-energy surface. Based on the projected Hessians, we develop an equation for the energy as a function of a set of curvilinear coordinates where the degeneracy is preserved to second order (i.e., the conical intersection hyperline). The curvature of the potential-energy surface in these coordinates is the curvature of the conical intersection hyperline itself, and thus determines whether one has a minimum or saddle point on the hyperline. The equation used to classify optimized conical intersection points depends in a simple way on the first- and second-order degeneracy splittings calculated at these points. As an example, for fulvene, we show that the two optimized conical intersection points of C2v symmetry are saddle points on the intersection hyperline. Accordingly, there are further intersection points of lower energy, and one of C2 symmetry - presented here for the first time - is found to be the global minimum in the intersection space

Approximate knowledge of rationality and correlated equilibria

We extend Aumann's theorem [Aumann 1987], deriving correlated equilibria as a consequence of common priors and common knowledge of rationality, by explicitly allowing for non-rational behavior. Wereplace the assumption of common knowledge of rationality with a substantially weaker one, joint p-belief of rationality, where agents believe the other agents are rational with probability p or more. We show that behavior in this case constitutes a kind of correlated equilibrium satisfying certain p-belief constraints, and that it varies continuously in the parameters p and, for p sufficiently close to one,with high probability is supported on strategies that survive the iterated elimination of strictly dominated strategies. Finally, we extend the analysis to characterizing rational expectations of interimtypes, to games of incomplete information, as well as to the case of non-common priors.

Parallel scheduling of multiclass M/M/m queues: Approximate and heavy-traffic optimization of achievable performance

We address the problem of scheduling a multiclass $M/M/m$ queue with Bernoulli feedback on $m$ parallel servers to minimize time-average linear holding costs. We analyze the performance of a heuristic priority-index rule, which extends Klimov's optimal solution to the single-server case: servers select preemptively customers with larger Klimov indices. We present closed-form suboptimality bounds (approximate optimality) for Klimov's rule, which imply that its suboptimality gap is uniformly bounded above with respect to (i) external arrival rates, as long as they stay within system capacity;and (ii) the number of servers. It follows that its relativesuboptimality gap vanishes in a heavy-traffic limit, as external arrival rates approach system capacity (heavy-traffic optimality). We obtain simpler expressions for the special no-feedback case, where the heuristic reduces to the classical $c \mu$ rule. Our analysis is based on comparing the expected cost of Klimov's ruleto the value of a strong linear programming (LP) relaxation of the system's region of achievable performance of mean queue lengths. In order to obtain this relaxation, we derive and exploit a new set ofwork decomposition laws for the parallel-server system. We further report on the results of a computational study on the quality of the $c \mu$ rule for parallel scheduling.

Exact and approximate stepdown methods for multiple hypothesis testing

Consider the problem of testing k hypotheses simultaneously. In this paper,we discuss finite and large sample theory of stepdown methods that providecontrol of the familywise error rate (FWE). In order to improve upon theBonferroni method or Holm's (1979) stepdown method, Westfall and Young(1993) make eective use of resampling to construct stepdown methods thatimplicitly estimate the dependence structure of the test statistics. However,their methods depend on an assumption called subset pivotality. The goalof this paper is to construct general stepdown methods that do not requiresuch an assumption. In order to accomplish this, we take a close look atwhat makes stepdown procedures work, and a key component is a monotonicityrequirement of critical values. By imposing such monotonicity on estimatedcritical values (which is not an assumption on the model but an assumptionon the method), it is demonstrated that the problem of constructing a validmultiple test procedure which controls the FWE can be reduced to the problemof contructing a single test which controls the usual probability of a Type 1error. This reduction allows us to draw upon an enormous resamplingliterature as a general means of test contruction.

Approximate polytope ensemble for one-class classification

In this work, a new one-class classification ensemble strategy called approximate polytope ensemble is presented. The main contribution of the paper is threefold. First, the geometrical concept of convex hull is used to define the boundary of the target class defining the problem. Expansions and contractions of this geometrical structure are introduced in order to avoid over-fitting. Second, the decision whether a point belongs to the convex hull model in high dimensional spaces is approximated by means of random projections and an ensemble decision process. Finally, a tiling strategy is proposed in order to model non-convex structures. Experimental results show that the proposed strategy is significantly better than state of the art one-class classification methods on over 200 datasets.

Approximate solution to the speed of spreading viruses

Recently, it has been shown that the speed of virus infections can be explained by time-delayed reactiondiffusion [J. Fort and V. Me´ndez, Phys. Rev. Lett. 89, 178101 (2002)], but no analytical solutions were found. Here we derive formulas for the front speed, valid in appropriate limits. We also integrate numerically the evolution equations of the system. There is good agreement with both numerical and experimental speeds

Material flow accounting of Spain

Material throughput is a means of measuring the so-called social metabolism, or physical dimensions of a society’s consumption, and can be taken as an indirect and approximate indicator of sustainability. Material flow accounting can be used to test the dematerialisation hypothesis, the idea that technological progress causes a decrease in total material used (strong dematerialisation) or material used per monetary unit of output (weak dematerialisation). This paper sets out the results of a material flow analysis for Spain for the period from 1980 to 2000. The analysis reveals that neither strong nor weak dematerialisation took place during the period analysed. Although the population did not increase considerably, materials mobilised by the Spanish economy (DMI) increased by 85% in absolute terms, surpassing GDP growth. In addition, Spain became more dependent on external trade in physical terms. In fact, its imports are more than twice the amount of its exports in terms of weight.

L'energia solar fotovoltaica com una alternativa en els espais urbans

Estudi realitzat per avaluar la possibilitat i viabilitat d’instal·lació de panells solar fotovoltaics als terrats de les comunitats de veïns del Districte de l’Eixample de Barcelona. La seva finalitat és conscienciar a la població sobre la problemàtica actual del canvi climàtic fent ús de la ciutat com a element clau per a fomentar l’estalvi de consum energètic i la reducció d’emissions de diòxid de carboni (CO2). Els resultats obtinguts ens donen un valor aproximat de la superfície i potència necessària pels habitants de la ciutat de Barcelona i Catalunya, per tal de cobrir el seu consum d’electricitat d’ús domèstic amb energia solar fotovoltaica, així com una comparativa amb els resultats obtinguts en el Districte de l’Eixample en les dimensions: socio-econòmica, mediambiental i política.

The Private and fiscal returns to schooling and the effect of public policies on private incentives to invest in education: a general framework and some results for the EU

This paper develops a comprehensive framework for the quantitative analysis of the private and fiscal returns to schooling and of the effect of public policies on private incentives to invest in education. This framework is applied to 14 member states of the European Union. For each of these countries, we construct estimates of the private return to an additional year of schooling for an individual of average attainment, taking into account the effects of education on wages and employment probabilities after allowing for academic failure rates, the direct and opportunity costs of schooling, and the impact of personal taxes, social security contributions and unemployment and pension benefits on net incomes. We also construct a set of effective tax and subsidy rates that measure the effects of different public policies on the private returns to education, and measures of the fiscal returns to schooling that capture the long-term effects of a marginal increase in attainment on public finances under conditions that approximate general equilibrium.

Caracteritació de models funcionals d'àmfores romanes mitjançant Finite Element Analysis

Projecte de recerca elaborat a partir d’una estada al Laboratory of Archaeometry del National Centre of Scientific Research “Demokritos” d’Atenes, Grècia, entre juny i setembre 2006. Aquest estudi s’emmarca dins d’un context més ampli d’estudi del canvi tecnològic que es documenta en la producció d’àmfores de tipologia romana durant els segles I aC i I dC en els territoris costaners de Catalunya. Una part d’aquest estudi contempla el càlcul de les propietats mecàniques d’aquestes àmfores i la seva avaluació en funció de la tipologia amforal, a partir de l’Anàlisi d’Elements Finits (AEF). L’AEF és una aproximació numèrica que té el seu origen en les ciències d’enginyeria i que ha estat emprada per estimar el comportament mecànic d’un model en termes, per exemple, de deformació i estrès. Així, un objecte, o millor dit el seu model, es dividit en sub-dominis anomenats elements finits, als quals se’ls atribueixen les propietats mecàniques del material en estudi. Aquests elements finits estan connectats formant una xarxa amb constriccions que pot ser definida. En el cas d’aplicar una força determinada a un model, el comportament de l’objecte pot ser estimat mitjançant el conjunt d’equacions lineals que defineixen el rendiment dels elements finits, proporcionant una bona aproximació per a la descripció de la deformació estructural. Així, aquesta simulació per ordinador suposa una important eina per entendre la funcionalitat de ceràmiques arqueològiques. Aquest procediment representa un model quantitatiu per predir el trencament de l’objecte ceràmic quan aquest és sotmès a diferents condicions de pressió. Aquest model ha estat aplicat a diferents tipologies amforals. Els resultats preliminars mostren diferències significatives entre la tipologia pre-romana i les tipologies romanes, així com entre els mateixos dissenys amforals romans, d’importants implicacions arqueològiques.

L' Aprenentatge basat en problemes a través de casos clínics simulats. Una proposta metodològica de disseny i avaluació docent

RESUM Les exigències actuals de la professió de d’infermeria requereixen que la docència vagi orientada a interrelacionar els diferents rols a desenvolupar enla pràctica diària, per adquirir experiència en l’aprenentatge i així augmentar la qualitat de les cures d’infermeria. Per assolir aquest objectiu és important l’aprenentatge basat enproblemes. Aquest pretén en primer lloc que els estudiants aprenguin allò que permet desenvolupar-se enla vida professional de la manera més natural possible a partir d’una idea clara i profunda de l’evidència sobre la que s’ha d’actuar. Amb aquesta finalitat es vandissenyar casos clínics amb uns objectius que requerien la integració de coneixements, actituds i valors, en diferents fases a desenvolupar en un període de temps predeterminat. També ens vam proposar una estratègia docent que permetés a l’estudiant incorporar el coneixement científic que dóna suport a la pràctica assistencial per aproximar teoria i pràctica. Es pretén que els estudiants busquin una resposta basada en la millor evidència científica disponible, per prendre una decisió respecte a les cures del pacient. Els objectius de l’estudi són: Avaluar globalment l’aprenentatge basat en la simulació de casos Avaluar com els estudiants valoren la integració del model d’infermeria i del procés d’atenció en l’aprenentatge basat en la simulació de casos. Valorar les sensacions percebudes per l’estudiant durant la simulació del cas. Valorar l’actitud d el’estudiant en relació a la incorporació de l’evidència científica per una millora en la pràctica clínica. Avaluar el grau de dificultat manifestat per l’estudiant en relació al procés de documentació. Avaluar la idonietat de l’argumentació i la decisió de l’estudiant a la pregunta formulada en el cas clínic. Metodologia: L’assignatura d’Infermeria Medicoquirúrgica. Adult I del Departament d’Infermeria de la Universitat de Vic, va iniciar una experiència d’aprenentatge basat en la resolució de problemes, amb estudiants de 2on curs. Les professores responsables dels seminaris van realitzar una avaluació de l’experiència a través d’una enquesta. Aquesta es responia al cap d’un mes de la simulació al laboratori, quan es contrastaven els resultats obtinguts en aquesta entre professores i estudiants després de visualitzar la gravació feta durant el mateix. En el context del seminari de simulació de casos, es va introduir una pregunta/problema, a partir de la que els estudiants, en grup, havien de documentar-se amb el suport d’una guia. Per valorar l’actitud davant aquesta pregunta/problema es va dissenyar un qustionari tipus Likert. L’avaluació del grau de dificultat s’ha registrat a través d’unes escales de puntuació. Per a l’avaluació de la decisió presa, es van valorar les síntesis resum entregades en els treballs escrits pels diferents grups. Resultats: La realització de la simulació en el laboratori va ser avaluada per un alt percentatge d’estudiants (68,8%) amb puntuacions entre 6 i 8 mentre que un 26,6% la van situar en tre 9 i 10, només un 4,7 % la van puntuar amb 5. La integració del model d’infermeria va ser valorada pel 86% amb una puntuació entre 7 i 10. La valoració global de la simulació va ser qualificada pels estudiants amb una puntuació de 8 (34,4%) seguida d’un 28,1% amb una consideració de 7. Un 7,2% van puntuar entre 9 i 10. El 93,3% van assegurar que conèixer les fonts documentals els serviria per millorar l’assistència, el 86,7% esperen obtenir arguments sòlids respecte les seves desicions si la documentació consultada és de qualitat. Un 77,8% dels estudiants consideren estar més satisfets al saber incorporar la presa de decisions basada en evidències. Respecte el grau de dificultat en el procés de documentació la dificultat més gran la presenten en com buscar en les bases de dades de referències bibliogràfiques. Conclusions: L’aprenentatge dels estudiants a través de la simulació de casos és una estratègia vàlida que l’estudiant valora positivament al mateix temps que permet desenvolupar habilitats per a la pràctica professional. L’estratègia docent dissenyada per integrar les evidències en la presa de decisions es considera positiva, no obstant, després d’analitzar els resultats, s’han de modificar alguns aspectes per a la seva millora; tutoritzar per a millorar el procés de documentació i incidir més en la crítica i reflexió, de manera que les troballes de la investigació siguin canalitzades cap a la pràctica.