Disseny, implementació i avaluació d'algorismes Max-SAT multivaluats

La finalitat d'aquest projecte és definir el problema Max-SAT amb codificació multiavaluada, implementar algorismes exactes de resolució del problema i construir un generador aleatori de problemes que permeti avaluar aquests algorismes.

The generator problem for Z-stable C*-algebras

The generator problem was posed by Kadison in 1967, and it remains open until today. We provide a solution for the class of C*-algebras absorbing the Jiang-Su algebra Z tensorially. More precisely, we show that every unital, separable, Z-stable C*-algebra A is singly generated, which means that there exists an element x є A that is not contained in any proper sub-C*- algebra of A. To give applications of our result, we observe that Z can be embedded into the reduced group C*-algebra of a discrete group that contains a non-cyclic, free subgroup. It follows that certain tensor products with reduced group C*-algebras are singly generated. In particular, C*r (F ∞) ⨂ C*r (F ∞) is singly generated.

Polynomial-time complexity for instances of the endomorphism problem in free groups

We say the endomorphism problem is solvable for an element W in a free group F if it can be decided effectively whether, given U in F, there is an endomorphism Φ of F sending W to U. This work analyzes an approach due to C. Edmunds and improved by C. Sims. Here we prove that the approach provides an efficient algorithm for solving the endomorphism problem when W is a two- generator word. We show that when W is a two-generator word this algorithm solves the problem in time polynomial in the length of U. This result gives a polynomial-time algorithm for solving, in free groups, two-variable equations in which all the variables occur on one side of the equality and all the constants on the other side.

ILS-ESP An efficient, simple, and parameter-free algorithm for solving the permutation flow-shop problem

From a managerial point of view, the more effcient, simple, and parameter-free (ESP) an algorithm is, the more likely it will be used in practice for solving real-life problems. Following this principle, an ESP algorithm for solving the Permutation Flowshop Sequencing Problem (PFSP) is proposed in this article. Using an Iterated Local Search (ILS) framework, the so-called ILS-ESP algorithm is able to compete in performance with other well-known ILS-based approaches, which are considered among the most effcient algorithms for the PFSP. However, while other similar approaches still employ several parameters that can affect their performance if not properly chosen, our algorithm does not require any particular fine-tuning process since it uses basic "common sense" rules for the local search, perturbation, and acceptance criterion stages of the ILS metaheuristic. Our approach defines a new operator for the ILS perturbation process, a new acceptance criterion based on extremely simple and transparent rules, and a biased randomization process of the initial solution to randomly generate different alternative initial solutions of similar quality -which is attained by applying a biased randomization to a classical PFSP heuristic. This diversification of the initial solution aims at avoiding poorly designed starting points and, thus, allows the methodology to take advantage of current trends in parallel and distributed computing. A set of extensive tests, based on literature benchmarks, has been carried out in order to validate our algorithm and compare it against other approaches. These tests show that our parameter-free algorithm is able to compete with state-of-the-art metaheuristics for the PFSP. Also, the experiments show that, when using parallel computing, it is possible to improve the top ILS-based metaheuristic by just incorporating to it our biased randomization process with a high-quality pseudo-random number generator.

Is the observed persistence spurious? A test for fractional integration versus short memory and structural breaks

Although it is commonly accepted that most macroeconomic variables are nonstationary, it is often difficult to identify the source of the non-stationarity. In particular, it is well-known that integrated and short memory models containing trending components that may display sudden changes in their parameters share some statistical properties that make their identification a hard task. The goal of this paper is to extend the classical testing framework for I(1) versus I(0)+ breaks by considering a a more general class of models under the null hypothesis: non-stationary fractionally integrated (FI) processes. A similar identification problem holds in this broader setting which is shown to be a relevant issue from both a statistical and an economic perspective. The proposed test is developed in the time domain and is very simple to compute. The asymptotic properties of the new technique are derived and it is shown by simulation that it is very well-behaved in finite samples. To illustrate the usefulness of the proposed technique, an application using inflation data is also provided.

Biased diffusion in confined media: Test of the Fick-Jacobs approximation and validity criteria

We study biased, diffusive transport of Brownian particles through narrow, spatially periodic structures in which the motion is constrained in lateral directions. The problem is analyzed under the perspective of the Fick-Jacobs equation, which accounts for the effect of the lateral confinement by introducing an entropic barrier in a one-dimensional diffusion. The validity of this approximation, based on the assumption of an instantaneous equilibration of the particle distribution in the cross section of the structure, is analyzed by comparing the different time scales that characterize the problem. A validity criterion is established in terms of the shape of the structure and of the applied force. It is analytically corroborated and verified by numerical simulations that the critical value of the force up to which this description holds true scales as the square of the periodicity of the structure. The criterion can be visualized by means of a diagram representing the regions where the Fick-Jacobs description becomes inaccurate in terms of the scaled force versus the periodicity of the structure.

Establishment of an In Vitro Photoallergy Test Using NCTC2544 Cells and IL-18 Production

Differentiation between photoallergenic and phototoxic reactions induced by low molecular weight compounds represents a current problem. The use of eratinocytes as a potential tool for the detection of photoallergens as opposed to photoirritants is considered an interesting strategy for developing in vitro methods. We have previously demonstrated the possibility to use the human keratinocyte cell line NCTC2455 and the production of interleukin-18 (IL-18) to screen low molecular weight sensitizers. The purpose of this work was to explore the possibility to use the NCTC2544 assay to identify photoallergens and discriminate from phototoxic chemicals. First, we identified suitable condition of UV-irradiation (3.5 J/cm2) by investigating the effect of UVAirradiation on intracellular IL-18 on untreated or chloropromazine (a representative phototoxic compound)- treated NCTC2544 cells. Then, the effect of UVA-irradiation over NCTC2544 cells treated with increasing concentrations of 15 compounds including photoallergens (benzophenone, 4-ter-butyl-4-methoxydibenzoylmethane, 2-ethylexyl-p-methoxycinnamate, ketoprofen, 6-methylcumarin); photoirritant and photoallergen (4-aminobenzoic acid, chlorpromazine, promethazine); photoirritants (acridine, ibuprofen, 8-methoxypsoralen, retinoic acid); and negative compounds (lactic acid, SDS and p-phenilendiamine) was investigated. Twenty-four hours after exposure, cytotoxicity was evaluated by the MTT assay or LDH leakage, while ELISA was used to measure the production of IL-18. At the maximal concentration assayed with non-cytotoxic effects (CV80 under irradiated condition), all tested photoallergens induced a significant and a dose-dependent increase of intracellular IL-18 following UVA irratiation, whereas photoirritants failed. We suggest that this system may be useful for the in vitro evaluation of the photoallergic potential of chemicals.

The orthogonal subcategory problem in homotopy theory

It is known that, in a locally presentable category, localization exists with respect to every set of morphisms, while the statement that localization with respect to every (possibly proper) class of morphisms exists in locally presentable categories is equivalent to a large-cardinal axiom from set theory. One proves similarly, on one hand, that homotopy localization exists with respect to sets of maps in every cofibrantly generated, left proper, simplicial model category M whose underlying category is locally presentable. On the other hand, as we show in this article, the existence of localization with respect to possibly proper classes of maps in a model category M satisfying the above assumptions is implied by a large-cardinal axiom called Vopënka's principle, although we do not know if the reverse implication holds. We also show that, under the same assumptions on M, every endofunctor of M that is idempotent up to homotopy is equivalent to localization with respect to some class S of maps, and if Vopënka's principle holds then S can be chosen to be a set. There are examples showing that the latter need not be true if M is not cofibrantly generated. The above assumptions on M are satisfied by simplicial sets and symmetric spectra over simplicial sets, among many other model categories.

Periodic orbits of the planar collision restricted 3-body problem

Using the continuation method we prove that the circular and the elliptic symmetric periodic orbits of the planar rotating Kepler problem can be continued into periodic orbits of the planar collision restricted 3–body problem. Additionally, we also continue to this restricted problem the so called “comets orbits”.

A topological proof that surface relators are test words

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

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.

Bribe-proof rules in the division problem

The division problem consists of allocating an amount of a perfectly divisible good among a group of n agents with single-peaked preferences. A rule maps preference profiles into n shares of the amount to be allocated. A rule is bribe-proof if no group of agents can compensate another agent to misrepresent his preference and, after an appropriate redistribution of their shares, each obtain a strictly preferred share. We characterize all bribe-proof rules as the class of efficient, strategy-proof, and weak replacement monotonic rules. In addition, we identify the functional form of all bribe-proof and tops-only rules.

A maximal domain of preferences for tops-only rules in the division problem

The division problem consists of allocating an amount M of a perfectly divisible good among a group of n agents. Sprumont (1991) showed that if agents have single-peaked preferences over their shares, the uniform rule is the unique strategy-proof, efficient, and anonymous rule. Ching and Serizawa (1998) extended this result by showing that the set of single-plateaued preferences is the largest domain, for all possible values of M, admitting a rule (the extended uniform rule) satisfying strategy-proofness, efficiency and symmetry. We identify, for each M and n, a maximal domain of preferences under which the extended uniform rule also satisfies the properties of strategy-proofness, efficiency, continuity, and "tops-onlyness". These domains (called weakly single-plateaued) are strictly larger than the set of single-plateaued preferences. However, their intersection, when M varies from zero to infinity, coincides with the set of single-plateaued preferences.

Subjective income expectations, canonical models and income risk

Expectations are central to behaviour. Despite the existence of subjective expectations data, the standard approach is to ignore these, to hypothecate a model of behaviour and to infer expectations from realisations. In the context of income models, we reveal the informational gain obtained from using both a canonical model and subjective expectations data. We propose a test for this informational gain, and illustrate our approach with an application to the problem of measuring income risk.