Convergence and morphological constraint in frogs : variation in postcranial morphology ; a contribution in celebration of the distinguished scholarship of Robert F. Inger on the occasion of his sixty-fifth birthday / Sharon B. Emerson.

n.s. no.43(1988)

A note on parallelizing the parameterized expectations algorithm

The parameterized expectations algorithm (PEA) involves a long simulation and a nonlinear least squares (NLS) fit, both embedded in a loop. Both steps are natural candidates for parallelization. This note shows that parallelization can lead to important speedups for the PEA. I provide example code for a simple model that can serve as a template for parallelization of more interesting models, as well as a download link for an image of a bootable CD that allows creation of a cluster and execution of the example code in minutes, with no need to install any software.

Double implementation in a market for indivisible goods with a price constraint

I consider the problem of assigning agents to objects where each agent must pay the price of the object he gets and prices must sum to a given number. The objective is to select an assignment-price pair that is envy-free with respect to the true preferences. I prove that the proposed mechanism will implement both in Nash and strong Nash the set of envy-free allocations. The distinguishing feature of the mechanism is that it treats the announced preferences as the true ones and selects an envy-free allocation with respect to the announced preferences.

Preliminary study of cooperation in hybrid ad-hoc networks

In this paper, we present a first approach to evolve a cooperative behavior in ad hoc networks. Since wireless nodes are energy constrained, it may not be in the best interest of a node to always accept relay requests. On the other hand, if all nodes decide not to expend energy in relaying, then network throughput will drop dramatically. Both these extreme scenarios are unfavorable to the interests of a user. In this paper we deal with the issue of user cooperation in ad hoc networks by developing the algorithm called Generous Tit-For-Tat. We assume that nodes are rational, i.e., their actions are strictly determined by self-interest, and that each node is associated with a minimum lifetime constraint. Given these lifetime constraints and the assumption of rational behavior, we study the added behavior of the network.

Picking the Right Budget Constraint for Scotland

This position paper considers the devolution of further fiscal powers to the Scottish Parliament in the context of the objectives and remit of the Smith Commission. The argument builds on our discussion of fiscal decentralization made in our previous published work on this topic. We ask what sort of budget constraint the Scottish Parliament should operate with. A soft budget constraint (SBC) allows the Scottish Parliament to spend without having to consider all of the tax and, therefore, political consequences, of that spending, which is effectively the position at the moment. The incentives to promote economic growth through fiscal policy – on both the tax and spending sides are weak to non-existent. This is what the Scotland Act, 1998, and the continuing use of the Barnett block grant, gave Scotland. Now other budget constraints are being discussed – those of the Calman Commission (2009) and the Scotland Act (2012), as well as the ones offered in 2014 by the various political parties – Scottish Conservatives, Scottish Greens, Scottish Labour, the Scottish Liberal Democrats and the Scottish Government. There is also the budget constraint designed by the Holtham Commission (2010) for Wales that could just as well be used in Scotland. We examine to what extent these offer the hard budget constraint (HBC) that would bring tax policy firmly into the realm of Scottish politics, asking the Scottish electorate and Parliament to consider the costs to them of increasing spending in terms of higher taxes; or the benefits to them of using public spending to grow the tax base and own-sourced taxes? The hardest budget constraint of all is offered by independence but, as is now known, a clear majority of those who voted in the referendum did not vote for this form of budget constraint. Rather they voted for a significant further devolution of fiscal powers while remaining within a political and monetary union with the rest of the UK, with the risk pooling and revenue sharing that this implies. It is not surprising therefore that none of the budget constraints on offer, apart from the SNP’s, come close to the HBC of independence. However, the almost 25% fall in the price of oil since the referendum, a resource stream so central to the SNP’s economic policy making, underscores why there is a need for a trade off between a HBC and risk pooling and revenue sharing. Ranked according to the desirable characteristic of offering something approaching a HBC the least desirable are those of the Calman Commission, the Scotland Act, 2012, and Scottish Labour. In all of these the ‘elasticity’ of the block grant in the face of failure to grow the Scottish tax base is either not defined or is very elastic – meaning that the risk of failure is shuffled off to taxpayers outside of Scotland. The degree of HBC in the Scottish Conservative, Scottish Greens and Scottish Liberal Democrats proposals are much more desirable from an economic growth point of view, the latter even embracing the HBC proposed by the Holtham Commission that combines serious tax policy with welfare support in the long-run. We judge that the budget constraint in the SNP’s proposals is too hard as it does not allow for continuation of the ‘welfare union’ in the UK. We also consider that in the case of a generalized UK economic slow requiring a fiscal stimulus that the Scottish Parliament be allowed increased borrowing to be repaid in the next economic upturn.

Multilayer perceptron with local constraint as an emerging method in spatial data analysis

The use of Geographic Information Systems has revolutionalized the handling and the visualization of geo-referenced data and has underlined the critic role of spatial analysis. The usual tools for such a purpose are geostatistics which are widely used in Earth science. Geostatistics are based upon several hypothesis which are not always verified in practice. On the other hand, Artificial Neural Network (ANN) a priori can be used without special assumptions and are known to be flexible. This paper proposes to discuss the application of ANN in the case of the interpolation of a geo-referenced variable.

An objective anisotropic elastic plastic model and Algorithm applicable to bone mechanics

The implicit projection algorithm of isotropic plasticity is extended to an objective anisotropic elastic perfectly plastic model. The recursion formula developed to project the trial stress on the yield surface, is applicable to any non linear elastic law and any plastic yield function.A curvilinear transverse isotropic model based on a quadratic elastic potential and on Hill's quadratic yield criterion is then developed and implemented in a computer program for bone mechanics perspectives. The paper concludes with a numerical study of a schematic bone-prosthesis system to illustrate the potential of the model.

A numerical algorithm for finding solutions of a generalized Nash equilibrium problem

A family of nonempty closed convex sets is built by using the data of the Generalized Nash equilibrium problem (GNEP). The sets are selected iteratively such that the intersection of the selected sets contains solutions of the GNEP. The algorithm introduced by Iusem-Sosa (2003) is adapted to obtain solutions of the GNEP. Finally some numerical experiments are given to illustrate the numerical behavior of the algorithm.

Propagation connectivity of random hypergraphs

We study the concept of propagation connectivity on random 3-uniform hypergraphs. This concept is inspired by a simple linear time algorithm for solving instances of certain constraint satisfaction problems. We derive upper and lower bounds for the propagation connectivity threshold, and point out some algorithmic implications.

An algorithm for semi-infinite polynomial optimization

"Vegeu el resum a l'inici del document del fitxer adjunt."

An approximation algorithm for #k-SAT

"Vegeu el resum a l'inici del document del fitxer adjunt"

Computing hypergraph width measures exactly

Hypergraph width measures are a class of hypergraph invariants important in studying the complexity of constraint satisfaction problems (CSPs). We present a general exact exponential algorithm for a large variety of these measures. A connection between these and tree decompositions is established. This enables us to almost seamlessly adapt the combinatorial and algorithmic results known for tree decompositions of graphs to the case of hypergraphs and obtain fast exact algorithms. As a consequence, we provide algorithms which, given a hypergraph H on n vertices and m hyperedges, compute the generalized hypertree-width of H in time O*(2n) and compute the fractional hypertree-width of H in time O(1.734601n.m).1

An iterative Multiscale Finite-Volume algorithm converging to the exact solution

The multiscale finite volume (MsFV) method has been developed to efficiently solve large heterogeneous problems (elliptic or parabolic); it is usually employed for pressure equations and delivers conservative flux fields to be used in transport problems. The method essentially relies on the hypothesis that the (fine-scale) problem can be reasonably described by a set of local solutions coupled by a conservative global (coarse-scale) problem. In most cases, the boundary conditions assigned for the local problems are satisfactory and the approximate conservative fluxes provided by the method are accurate. In numerically challenging cases, however, a more accurate localization is required to obtain a good approximation of the fine-scale solution. In this paper we develop a procedure to iteratively improve the boundary conditions of the local problems. The algorithm relies on the data structure of the MsFV method and employs a Krylov-subspace projection method to obtain an unconditionally stable scheme and accelerate convergence. Two variants are considered: in the first, only the MsFV operator is used; in the second, the MsFV operator is combined in a two-step method with an operator derived from the problem solved to construct the conservative flux field. The resulting iterative MsFV algorithms allow arbitrary reduction of the solution error without compromising the construction of a conservative flux field, which is guaranteed at any iteration. Since it converges to the exact solution, the method can be regarded as a linear solver. In this context, the schemes proposed here can be viewed as preconditioned versions of the Generalized Minimal Residual method (GMRES), with a very peculiar characteristic that the residual on the coarse grid is zero at any iteration (thus conservative fluxes can be obtained).