An efficient solver for weighted Max-SAT

We present a new branch and bound algorithm for weighted Max-SAT, called Lazy which incorporates original data structures and inference rules, as well as a lower bound of better quality. We provide experimental evidence that our solver is very competitive and outperforms some of the best performing Max-SAT and weighted Max-SAT solvers on a wide range of instances.     

Semigroups of Composition Operators in BMOA and the Extension of a Theorem of Sarason

In this paper we deal with the maximal subspace in BMOA where a general semigroup of analytic functions on the unit disk generates a strongly continuous semigroup of composition operators. Particular cases of this question are related to a well-known theorem of Sarason about VMOA. Our results describe analytically that maximal subspace and provide a condition which is sufficient for the maximal subspace to be exactly VMOA. A related necessary condition is also proved in the case when the semigroup has an inner Denjoy-Wolff point. As a byproduct we provide a generalization of the theorem of Sarason. This research has been partially supported by the Ministerio de Educación y Ciencia projects n. MTM2006-14449-C02-01 and MTM2005-08350-C03-03 and by La Consejería de Educación y Ciencia de la Junta de Andalucía.     

Local embeddings of some families of subgroups of finite groups

In this paper we study the influence of the partial cover and avoidance property on the subgroups of some relevant families of subgroups in a finite group.     

Evolution families and the Loewner equation II: complex hyperbolic manifolds

We prove that evolution families on complex complete hyperbolic manifolds are in one to one correspondence with certain semicomplete non-autonomous holomorphic vector fields, providing the solution to a very general Loewner type differential equation on manifolds. M. D. Contreras and S. Díaz-Madrigal were partially supported by the Ministerio de Ciencia e Innovación and the European Union (FEDER), project MTM2006-14449-C02-01, by La Consejería de Educación y Ciencia de la Junta de Andalucía, and by the European Science Foundation Research Networking Programme HCAA.     

Maximal surface group representations in isometry groups of classical Hermitian symmetric spaces

Higgs bundles and non-abelian Hodge theory provide holomorphic methods with which to study the moduli spaces of surface group representations in a reductive Lie group G. In this paper we survey the case in which G is the isometry group of a classical Hermitian symmetric space of non-compact type. Using Morse theory on the moduli spaces of Higgs bundles, we compute the number of connected components of the moduli space of representations with maximal Toledo invariant Members of VBAC (Vector Bundles on Algebraic Curves). Second and Third authors partially supported by Ministerio de Educación y Ciencia and Conselho de Reitores das Universidades Portuguesas through Acción Integrada Hispano-Lusa HP2002-0017 (Spain)/E–30/03 (Portugal). First and Second authors partially supported by Ministerio de Educación y Ciencia (Spain) through Project MTM2004-07090-C03-01. Third author partially supported by the Centro de Matemática da Universidade do Porto and the project POCTI/MAT/58549/2004, financed by FCT (Portugal) through the programmes POCTI and POSI of the QCA III (2000–2006) with European Community (FEDER) and national funds. The second author visited the IHES with the partial support of the European Commission through its 6th Framework Programme “Structuring the European Research Area” and the Contract No. RITA-CT-2004-505493 for the provision of Transnational Access implemented as Specific Support Action     

Jacobi transplantation revisited

A transplantation theorem for Jacobi series proved by Muckenhoupt is reinvestigated by means of a suitable variant of Calderón–Zygmund operator theory. An essential novelty of our paper is weak type (1,1) estimate for the Jacobi transplantation operator, located in a fairly general weighted setting. Moreover, L ^p estimates are proved for a class of weights that contains the class admitted in Muckenhoupt’s theorem. Research of ó. Ciaurri and K. Stempak was supported by the grant MTM2006-13000-C03-03 of the DGI. Research of A. Nowak and K. Stempak was supported by MNiSW Grant N201 054 3214285.     

A Sharp Form of the Cramér–Wold Theorem

The Cramér–Wold theorem states that a Borel probability measure P on ℝ ^d is uniquely determined by its one-dimensional projections. We prove a sharp form of this result, addressing the problem of how large a subset of these projections is really needed to determine P. We also consider extensions of our results to measures on a separable Hilbert space. First author partially supported by the Spanish Ministerio de Ciencia y Tecnología, grant BFM2002-04430-C02-02. Second author partially supported by Instituto de Cooperación Iberoamericana, Programa de Cooperación Interuniversitaria AL-E 2003. Third author partially supported by grants from NSERC and the Canada research chairs program.     

Incomplete inference for graph problems

Recently, a resolution-based transformation has been introduced for the usual Max-SAT encoding of several graph problems such as the Minimum Vertex Covering, Maximum Clique and Combinatorial Auctions which consists in iteratively applying specific inference rules to transform and simplify the original formula. Such transformation was shown suitable to improve the performance of local and systematic search procedures. In this paper, we present several refinements for such transformation. In particular, we introduce a more suitable transformation for the Minimum Vertex Covering problem, specially for its weighted version, and we extend its use for the Maximum Cut problem. Empirical results indicate that systematic Max-SAT solvers improve substantially their performance.     

Numerical Properties of Shifted Tridiagonal LU Factorizations

In this paper, we consider shifted tridiagonal matrices. We prove that the standard algorithm to compute the LU factorization in this situation is mixed forward-backward stable and, therefore, componentwise forward stable. Moreover, we give a formula to compute the corresponding condition number in O(n) flops. This research has been partially supported by Dirección General de Investigación (Ministerio de Ciencia y Tecnología) of Spain through grants BFM2003-06335-C03-02 and MTM2006-06671 as well as by the Postdoctoral Fellowship EX2004-0658 provided by Ministerio de Educación y Ciencia of Spain.     

Existence and Uniqueness of Fixed Point in Partially Ordered Sets and Applications to Ordinary Differential Equations

We prove some fixed point theorems in partially ordered sets, providing an extension of the Banach contractive mapping theorem. Having studied previously the nondecreasing case, we consider in this paper nonincreasing mappings as well as non monotone mappings. We also present some applications to first–order ordinary differential equations with periodic boundary conditions, proving the existence of a unique solution admitting the existence of a lower solution. Research partially supported by Ministerio de Educación y Ciencia and FEDER, Project MTM2004-06652-C03-01, and by Xunta de Galicia and FEDER, Projects PGIDIT02PXIC20703PN and PGIDIT05PXIC20702PN     

Mild solutions for a class of fractional SPDEs and their sample paths

We introduce a notion of mild solution for a class of non-autonomous parabolic stochastic partial differential equations defined on a bounded open subset ${D\subset\mathbb{R}^{d}}We introduce a notion of mild solution for a class of non-autonomous parabolic stochastic partial differential equations defined on a bounded open subset and driven by an infinite-dimensional fractional noise. We prove the existence of such a solution, establish its relation with the variational solution introduced by Nualart and Vuillermot (J Funct Anal 232:390–454, 2006) and the H?lder continuity of its sample paths when we consider it as an L ²(D)-valued stochastic process. When h is an affine function, we also prove uniqueness. An immediate consequence of our results is the indistinguishability of mild and variational solutions in the case of uniqueness. M. Sanz-Solé was supported by the grant MTM 2006-01351 from the Dirección General de Investigación, Ministerio de Educación y Ciencia, Spain.     

The limit as <Emphasis Type="Italic">p</Emphasis> → ∞ in a nonlocal <Emphasis Type="Italic">p</Emphasis>-Laplacian evolution equation: a nonlocal approximation of a model for sandpiles

In this paper, we study the nonlocal ∞-Laplacian type diffusion equation obtained as the limit as p → ∞ to the nonlocal analogous to the p-Laplacian evolution,

On the Convexity of Precedence Sequencing Games

In this paper we study a class of cooperative sequencing games that arise from one-machine sequencing situations in which chain precedence relations are imposed on the jobs. We show that these sequencing games are convex if the initial order of the jobs is a concatenation of chains. F. Klijn's research is supported by a Ramón y Cajal contract of the Spanish Ministerio de Ciencia y Tecnología. The main part of F. Klijn's work was supported by a Marie Curie Fellowship of the European Community programme “Improving Human Research Potential and the Socio-economic Knowledge Base” under contract number HPMF-CT-2001-01232, carried out at the Departament d'Economia i d'Història Econòmica, Universitat Autònoma de Barcelona. His work is also partially supported by Research Grant BEC2002-02130 from the Spanish Ministerio de Ciencia y Tecnología and by the Barcelona Economics Program of CREA     

The value of the stochastic solution in multistage problems

We generalize the definition of the bounds for the optimal value of the objective function for various deterministic equivalent models in multistage stochastic programs. The parameters EVPI and VSS were introduced for two-stage models. The parameter EVPI, the expected value of perfect information, measures how much it is reasonable to pay to obtain perfect information about the future. The parameter VSS, the value of the stochastic solution, allows us to obtain the goodness of the expected solution value when the expected values are replaced by the random values for the input variables. We extend the definition of these parameters to the multistage stochastic model and prove a similar chain of inequalities with the lower and upper bounds depending substantially on the structure of the problem. This research has been partially supported by the grants, 1/BBVA 00038.16421/2004 from Fundación BBVA, SEJ2005-05549/ECON from Ministerio de Educación y Ciencia and the grant GRUPOS79/04 from the Generalitat Valenciana, Spain.     

Large orbits of<Emphasis Type="Italic">p</Emphasis>-groups on characters and applications to character degrees

We prove that if ap-groupA acts on a solvablep′-groupG then there is a “large” orbit on the ordinary complex irreducible characters ofG. As a consequence of this theorem we obtain results that relate ordinary and Brauer character degrees. Research supported by the FEDER, the Spanish Ministerio de Ciencia y Tecnología, grant BFM2001-0180, and Programa Ramón y Cajal.     

Width of convex bodies in spaces of constant curvature

We consider the measure of points, the measure of lines and the measure of planes intersecting a given convex body K in a space form. We obtain some integral formulas involving the width of K and the curvature of its boundary ∂K. Also we study the special case of constant width. Moreover we obtain a generalisation of the Heintze–Karcher inequality to space forms. Work partially supported by grant number ACI2003-44 Joint action Catalonia–Baden-Württemberg and by FEDER/MEC grant number MTM2006-04353. The third author was also supported by the program Ramón y Cajal, MEC.     

Rational Brauer characters

It is known that every finite group of even order has a non-trivial complex irreducible character which is rational valued. We prove the modular version of this result: If p is an odd prime and G is any finite group of even order, then G has a non-trivial irreducible p-Brauer character which is rational valued. The first author is partially supported by the Ministerio de Educación y Ciencia proyecto MTM2004-06067-C02-01, while the second gratefully acknowledges the support of the NSA (grant H98230-04-0066).     

Characterizing efficiency without linear structure: a unified approach

In this paper, we study a general optimization problem without linear structure under a reflexive and transitive relation on a nonempty set E, and characterize the existence of efficient points and the domination property for a subset of E through a generalization of the order-completeness condition introduced earlier. Afterwards, we study the abstract optimization problem by using generalized continuity concepts and establish various existence results. As an application, we extend and improve several existence results given in the literature for an optimization problem involving set-valued maps under vector and set criteria. The work of the first author was partially supported by CONICYT-Chile through FONDECYT 107-0689 and FONDAP-Matemáticas Aplicadas II; whereas that of the second and third author were supported in part by Ministerio de Educación y Ciencia (Spain), project MTM2006-02629 and by Junta de Castilla y León (Spain) Project VA027B06.     

Intelligent variable orderings and re-orderings in DAC-based solvers for WCSP

Weighted constraint satisfaction problems (WCSPs) is a well-known framework for combinatorial optimization problems with several domains of application. In the last few years, several local consistencies for WCSPs have been proposed. Their main use is to embed them into a systematic search, in order to detect and prune unfeasible values as well as to anticipate the detection of deadends. Some of these consistencies rely on an order among variables but nothing is known about which orders are best. Therefore, current implementations use the lexicographic order by default. In this paper we analyze the effect of heuristic orders at three levels of increasing overhead: i) compute the order prior to search and keep it fixed during the whole solving process (we call this a static order), ii) compute the order at every search node using current subproblem information (we call this a dynamic order) and iii) compute a sequence of different orders at every search node and sequentially enforce the local consistency for each one (we call this dynamic re-ordering). We performed experiments in three different problems: Max-SAT, Max-CSP and warehouse location problems. We did not find an alternative better than the rest for all the instances. However, we found that inverse degree (static order), sum of unary weights (dynamic order) and re-ordering with the sum of unary weights are good heuristics which are always better than a random order. This research is supported by the MEC through project TIC-2002-04470-C03.     

Sharp Conditions for the Existence of Solutions of Second-Order Autonomous Differential Equations

We prove general existence results for where f and g need not be continuous or monotone. Moreover neither f nor g need be bounded around, respectively, x ₀ and x ₁, thus allowing singularities in the equation. Several other basic topics such as uniqueness, continuation, extremality and periodicity are studied in our general framework. The research of J. á. Cid and R. L. Pouso is partially supported by Ministerio de Educación y Ciencia, Spain, project MTM2004-06652-C03-01, and by Xunta de Galicia, Spain/FEDER, project PGIDIT05PXIC20702PN.