A polynomial algorithm for special case of the one-machine scheduling problem with time-lags

The standard one-machine scheduling problem consists in schedulinga set of jobs in one machine which can handle only one job at atime, minimizing the maximum lateness. Each job is available forprocessing at its release date, requires a known processing timeand after finishing the processing, it is delivery after a certaintime. There also can exists precedence constraints between pairsof jobs, requiring that the first jobs must be completed beforethe second job can start. An extension of this problem consistsin assigning a time interval between the processing of the jobsassociated with the precedence constrains, known by finish-starttime-lags. In presence of this constraints, the problem is NP-hardeven if preemption is allowed. In this work, we consider a specialcase of the one-machine preemption scheduling problem with time-lags, where the time-lags have a chain form, and propose apolynomial algorithm to solve it. The algorithm consist in apolynomial number of calls of the preemption version of the LongestTail Heuristic. One of the applicability of the method is to obtainlower bounds for NP-hard one-machine and job-shop schedulingproblems. We present some computational results of thisapplication, followed by some conclusions.

Growth of positive words and lower bounds of the growth rate for Thompson's group (F)p

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

Bounding right-arm rotation distances

Rotation distance quantifies the difference in shape between two rooted binary trees of the same size by counting the minimum number of elementary changes needed to transform one tree to the other. We describe several types of rotation distance, and provide upper bounds on distances between trees with a fixed number of nodes with respect to each type. These bounds are obtained by relating each restricted rotation distance to the word length of elements of Thompson's group F with respect to different generating sets, including both finite and infinite generating sets.

Periodic orbits near a heteroclinic loop formed by one dimensional orbit and a 2-dimensional manifold: application to the charged collinear 3-body problem

The paper is devoted to the study of a type of differential systems which appear usually in the study of some Hamiltonian systems with 2 degrees of freedom. We prove the existence of infinitely many periodic orbits on each negative energy level. All these periodic orbits pass near the total collision. Finally we apply these results to study the existence of periodic orbits in the charged collinear 3–body problem.

How tight should one's hands be tied? Fear of floating and credibility of exchange rate regimes

This paper analyzes the linkages between the credibility of a target zone regime, the volatility of the exchange rate, and the width of the band where the exchange rate is allowed to fluctuate. These three concepts should be related since the band width induces a trade-off between credibility and volatility. Narrower bands should give less scope for the exchange rate to fluctuate but may make agents perceive a larger probability of realignment which by itself should increase the volatility of the exchange rate. We build a model where this trade-off is made explicit. The model is used to understand the reduction in volatility experienced by most EMS countries after their target zones were widened on August 1993. As a natural extension, the model also rationalizes the existence of non-official, implicit target zones (or fear of floating), suggested by some authors.

Current Account imbalances, thriftiness and the real exchange rate in a growing economy

This paper analyses the theoretical relevance of the dynamical aspects of growth on the discussion about the observed positive correlation between per capita real income and real exchange rates. With this purpose, we develop a simple exogenous growth model where the internal, external and intertemporal equilibrium conditions of a typical macroeconomic model are imposed; this last one through the inclusion of a balanced growth path for the foreign assets accumulation. The main result under this consideration is that the relationship defended by the Balassa-Samuelson hypothesis is no more so straightforward. In our particular approach, the mentioned bilateral relationship depends on a parameter measuring thriftiness in the economy. Therefore, the probability of ending up with a positive relationship between growth and real exchange rates -as the classical economic theory predicts- will be higher when the economy is able to maintain a minimum saving ratio. Moreover, given that our model considers a simple Keynesian consumption function, some explosive paths can also be possible.

Are one factor logarithmic volatility models useful to fit the features of financial data? An application to microsoft data.

This paper provides empirical evidence that continuous time models with one factor of volatility, in some conditions, are able to fit the main characteristics of financial data. It also reports the importance of the feedback factor in capturing the strong volatility clustering of data, caused by a possible change in the pattern of volatility in the last part of the sample. We use the Efficient Method of Moments (EMM) by Gallant and Tauchen (1996) to estimate logarithmic models with one and two stochastic volatility factors (with and without feedback) and to select among them.

On group strategy-proof mechanisms for a many-to-one matching model

For the many-to-one matching model in which firms have substitutable and quota q-separable preferences over subsets of workers we show that the workers-optimal stable mechanism is group strategy-proof for the workers. In order to prove this result, we also show that under this domain of preferences (which contains the domain of responsive preferences of the college admissions problem) the workers-optimal stable matching is weakly Pareto optimal for the workers and the Blocking Lemma holds as well. We exhibit an example showing that none of these three results remain true if the preferences of firms are substitutable but not quota q-separable.

In whose backyard? A generalized bidding approach

We analyze situations in which a group of agents (and possibly a designer) have to reach a decision that will affect all the agents. Examples of such scenarios are the location of a nuclear reactor or the siting of a major sport event. To address the problem of reaching a decision, we propose a one-stage multi-bidding mechanism where agents compete for the project by submitting bids. All Nash equilibria of this mechanism are efficient. Moreover, the payoffs attained in equilibrium by the agents satisfy intuitively appealing lower bounds..

The relevance of post-match LTC: why has the Spanish labor market become as volatile as the US one?

We present a Search and Matching model with heterogeneous workers (entrants and incumbents) that replicates the stylized facts characterizing the US and the Spanish labor markets. Under this benchmark, we find the Post-Match Labor Turnover Costs (PMLTC) to be the centerpiece to explain why the Spanish labor market is as volatile as the US one. The two driving forces governing this volatility are the gaps between entrants and incumbents in terms of separation costs and productivity. We use the model to analyze the cyclical implications of changes in labor market institutions affecting these two gaps. The scenario with a low degree of workers’ heterogeneity illustrates its suitability to understand why the Spanish labor market has become as volatile as the US one.

Lower bounds for the number of limit cycles of trigonometric Abel equations

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

Codificación a nivel de paquete para comunicaciones móviles por satélite

Una de les opcions que es contemplen per transmetre continguts multimèdia i proporcionar accés a Internet a grups de usuaris mòbils és fer servir satèl·lits. Les condiciones de propagació del canal mòbil impliquen que d'una manera o altra haurem de garantir la qualitat de servei. Això té fins i tot més importància si tenim en compte que, en el cas d'accés a Internet, no es té la capacitat d'assumir cert percentatge de pèrdua de dades que tenim, per exemple, en la transmissió de so o vídeo (rebaixant la qualitat). Entre les principals alternatives per a aquesta classe d’entorns es troba la inclusió de codificacions a nivell de paquet. El funcionament d'aquesta tècnica es basa en incloure a la transmissió paquets redundants, obtinguts mitjançant un determinat algoritme. El receptor podrà recuperar la informació original que es volia enviar, sempre que hagi rebut una certa quantitat de paquets, similar a la quantitat de paquets originals. A aquest mecanisme se'l coneix com Forward Error Correction (FEC) a nivell de paquet. En aquesta memòria es valoren breument les alternatives existents i s'expliquen algunes de les codificacions per a FEC més importants. A continuació es realitza un estudi compartiu d’algunes d'elles: les variants de LDPC (Low Density Parity Check) conegudes com LDGM (Low Density Generator Matrix), i la codificació Raptor

A classification, up to hyperbolicity, of groups given by 2 generators and one relator of length 8

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

Sistema d'autenticació one-time password (OTP) per a mòbils

Aquest projecte consisteix en fer l’anàlisi, disseny i implementació d'un sistema d'autenticació a través de contrasenyes d’un sol ús (One Time Password ‐OTP‐) per a dispositius mòbils. Per evitar l’ús de contrasenyes estàtiques farem una aplicació per a telèfons mòbils capaç de generar contrasenyes aleatòries gràcies a uns paràmetres previs, així com de poder tenir un registre dels serveis on poden ser utilitzades. Partirem d’un protocol repte/resposta on l’usuari interactuarà amb el seu telèfon mòbil i un ordinador personal amb una connexió a Internet. Podrà registrar‐se i, introduint certes dades al mòbil que li proporciona el servidor, podrà fer el procés d’autenticar‐se per poder accedir a zones restringides del servei.

Bargaining one-dimensional policies and the efficiency of super majority rules

We consider negotiations selecting one-dimensional policies. Individuals have single-peaked preferences, and they are impatient. Decisions arise from a bargaining game with random proposers and (super) majority approval, ranging from the simple majority up to unanimity. The existence and uniqueness of stationary subgame perfect equilibrium is established, and its explicit characterization provided. We supply an explicit formula to determine the unique alternative that prevails, as impatience vanishes, for each majority. As an application, we examine the efficiency of majority rules. For symmetric distributions of peaks unanimity is the unanimously preferred majority rule. For asymmetric populations rules maximizing social surplus are characterized.