An iterated-tabu-search heuristic for a variant of the partial set covering problem

In this paper, we propose a heuristic algorithm to solve a new variant of the partial set covering problem. In this variant, each element $e_i$ has a gain $g_i$ (i.e., a positive profit), each set $s_j$ has a cost $c_j$ (i.e., a negative profit), and each set $s_j$ is part of a unique group $G_k$ that has a fixed cost $f_k$ (i.e., a negative profit). The objective is to maximize profit and it is not necessary to cover all of the elements. We present an industrial application of the model and propose a hybrid heuristic algorithm to solve it; the proposed algorithm is an iterated-local-search algorithm that uses two levels of perturbations and a tabu-search heuristic. Whereas the first level of perturbation diversifies the search around the current local optimum, the second level of perturbation performs long jumps in the search space to help escape from local optima with large basins of attraction. The proposed algorithm is evaluated on thirty real-world problems and compared to a memetic algorithm. Computational results show that most of the solutions found by ITS are either optimal or very close to optimality.     

On the complexity of the herding attack and some related attacks on hash functions

In this article, we analyze the complexity of the construction of the 2 ^k -diamond structure proposed by Kelsey and Kohno (LNCS, Vol 4004, pp 183–200, 2006). We point out a flaw in their analysis and show that their construction may not produce the desired diamond structure. We then give a more rigorous and detailed complexity analysis of the construction of a diamond structure. For this, we appeal to random graph theory (in particular, to the theory of random intersection graphs), which allows us to determine sharp necessary and sufficient conditions for the message complexity (i.e., the number of hash computations required to build the required structure). We also analyze the computational complexity for constructing a diamond structure, which has not been previously studied in the literature. Finally, we study the impact of our analysis on herding and other attacks that use the diamond structure as a subroutine. Precisely, our results shows the following:

1. The message complexity for the construction of a diamond structure is ${\sqrt{k}}$ times more than the amount previously stated in literature.

1. The time complexity is n times the message complexity, where n is the size of hash value.

Due to the above two results, the herding attack (Kelsey and Kohno, LNCS, Vol 4004, pp 183–200, 2006) and the second preimage attack (Andreeva et?al., LNCS, Vol 4965, pp 270–288, 2008) on iterated hash functions have increased complexity. We also show that the message complexity of herding and second preimage attacks on “hash twice” is n times the complexity claimed by Andreeva et?al. (LNCS, Vol 5867, pp 393–414, 2009), by giving a more detailed analysis of the attack.     

Propagation des singularités des courants positifs fermés

Given a closed positive currentT on a bounded Runge open subset Ω ofC ⁿ , we study sufficient conditions for the existence of a global extension ofT toC ⁿ . WhenT has a sufficiently low density, we show that the extension is possible and that there is no propagation of singularities, i.e.T may be extended by a closed positiveC ^∞-form outside \(\bar \Omega \) . Conversely, using recent results ofH. Skoda andH. El Mir, we give examples of non extendable currents showing that the above sufficient conditions are optimal in bidegree (1, 1).     

Positive definite superfunctions and unitary representations of lie supergroups

For a broad class of Fréchet-Lie supergroups $ \mathcal{G} $ , we prove that there exists a correspondence between positive definite smooth (resp., analytic) superfunctions on $ \mathcal{G} $ and matrix coefficients of smooth (resp., analytic) unitary representations of the Harish-Chandra pair (G, $ \mathfrak{g} $ ) associated to $ \mathcal{G} $ . As an application, we prove that a smooth positive definite superfunction on $ \mathcal{G} $ is analytic if and only if it restricts to an analytic function on the underlying manifold of $ \mathcal{G} $ . When the underlying manifold of $ \mathcal{G} $ is 1-connected we obtain a necessary and sufficient condition for a linear functional on the universal enveloping algebra U( $ {{\mathfrak{g}}_{\mathbb{C}}} $ ) to correspond to a matrix coefficient of a unitary representation of (G, $ \mathfrak{g} $ ). The class of Lie supergroups for which the aforementioned results hold is characterised by a condition on the convergence of the Trotter product formula. This condition is strictly weaker than assuming that the underlying Lie group of $ \mathcal{G} $ is a locally exponential Fréchet-Lie group. In particular, our results apply to examples of interest in representation theory such as mapping supergroups and diffeomorphism supergroups.     

Multiple criteria problems over Minkowski balls

Under study are some vector optimization problems over the space of Minkowski balls, i.e., symmetric convex compact subsets in Euclidean space. A typical problem requires to achieve the best result in the presence of conflicting goals; e.g., given the surface area of a symmetric convex body $\mathfrak{x}$ , we try to maximize the volume of $\mathfrak{x}$ and minimize the width of $\mathfrak{x}$ simultaneously.     

Weighted norm inequalities for the vectorvalued Hardy-Littlewood maximal functions of one parameter rectangles

Let N denote the Hardy-Littlewood maximal operator for the familyR of one parameter rectangles. In this paper, we obtain that for 1 _w ^p (l^r) to L _W ^P (l^r) if and only if w ∈ A_P(R); for 1≤p<∞, N is bounded from L _W ^P (l^r) to weak L _W ^P (l^r) if and only if W ∈ A_P(R). Here we say W∈A_p (1), if $$\begin{gathered} \mathop {sup}\limits_{R \in R} \left( {\tfrac{1}{{|R|}}\smallint _r wdx} \right)\left( {\tfrac{1}{{|R|}}\smallint _R w^{ - 1/(p - 1)} dx} \right)^{p - 1}< \infty ,1< p< \infty , \hfill \\ (Nw)(x) \leqslant Cw(x)a.e.,p = 1 \hfill \\ \end{gathered} $$ ,     

Classification theory for non-elementary classes I: The number of uncountable models ofψ ∈L ω_1, ω. Part A

Assuming that 2^Nn < 2^Nn+1 forn < ω, we prove that everyψ ∈L _{ω_1, ω} has many non-isomorphic models of powerN _n for somen>0or has models in all cardinalities. We can conclude that every such Ψ has at least 2 _N 1 non-isomorphic uncountable models. As for the more vague problem of classification, restricting ourselves to the atomic models of some countableT (we can reduce general cases to this) we find a cutting line named “excellent”. Excellent classes are well understood and are parallel to totally transcendental theories, have models in all cardinals, have the amalgamation property, and satisfy the Los conjecture. For non-excellent classes we have a non-structure theorem, e.g., if they have an uncountable model then they have many non-isomorphic ones in someN _n (provided {ie212-7}).     

On Rational Pairings of Functors

In the theory of coalgebras C over a ring R, the rational functor relates the category $_{C^*}{\mathbb{M}}$ of modules over the algebra C ^* (with convolution product) with the category $^C{\mathbb{M}}$ of comodules over C. This is based on the pairing of the algebra C ^* with the coalgebra C provided by the evaluation map ${\rm ev}:C^*\otimes_R C\to R$ . The (rationality) condition under consideration ensures that $^C{\mathbb{M}}$ becomes a coreflective full subcategory of $_{C^*}{\mathbb{M}}$ . We generalise this situation by defining a pairing between endofunctors T and G on any category ${\mathbb{A}}$ as a map, natural in $a,b\in {\mathbb{A}}$ , $$ \beta_{a,b}:{\mathbb{A}}(a, G(b)) \to {\mathbb{A}}(T(a),b), $$ and we call it rational if these all are injective. In case T?=?(T, m _T , e _T ) is a monad and G?=?(G, δ _G , ε _G ) is a comonad on ${\mathbb{A}}$ , additional compatibility conditions are imposed on a pairing between T and G. If such a pairing is given and is rational, and T has a right adjoint monad T ^???, we construct a rational functor as the functor-part of an idempotent comonad on the T-modules ${\mathbb{A}}_{T}$ which generalises the crucial properties of the rational functor for coalgebras. As a special case we consider pairings on monoidal categories.     

Rank-into-rank hypotheses and the failure of GCH

In this paper we are concerned about the ways GCH can fail in relation to rank-into-rank hypotheses, i.e., very large cardinals usually denoted by I3, I2, I1 and I0. The main results are a satisfactory analysis of the way the power function can vary on regular cardinals in the presence of rank-into-rank hypotheses and the consistency under I0 of the existence of ${j : V_{\lambda+1} {\prec} V_{\lambda+1}}$ with the failure of GCH at ${\lambda}$ .     

ParNes: a rapidly convergent algorithm for accurate recovery of sparse and approximately sparse signals

In this article, we propose an algorithm, nesta-lasso, for the lasso problem, i.e., an underdetermined linear least-squares problem with a 1-norm constraint on the solution. We prove under the assumption of the restricted isometry property (rip) and a sparsity condition on the solution, that nesta-lasso is guaranteed to be almost always locally linearly convergent. As in the case of the algorithm nesta, proposed by Becker, Bobin, and Candès, we rely on Nesterov’s accelerated proximal gradient method, which takes $O(\sqrt {1/\varepsilon })$ iterations to come within $\varepsilon > 0$ of the optimal value. We introduce a modification to Nesterov’s method that regularly updates the prox-center in a provably optimal manner. The aforementioned linear convergence is in part due to this modification. In the second part of this article, we attempt to solve the basis pursuit denoising (bpdn) problem (i.e., approximating the minimum 1-norm solution to an underdetermined least squares problem) by using nesta-lasso in conjunction with the Pareto root-finding method employed by van den Berg and Friedlander in their spgl1 solver. The resulting algorithm is called parnes. We provide numerical evidence to show that it is comparable to currently available solvers.     

On Estimating the Asymptotic Variance of Stationary Point Processes

We investigate a class of kernel estimators $\widehat{\sigma}^2_n$ of the asymptotic variance σ ² of a d-dimensional stationary point process $\Psi = \sum_{i\ge 1}\delta_{X_i}$ which can be observed in a cubic sampling window $W_n = [-n,n]^d\,$ . σ ² is defined by the asymptotic relation $Var(\Psi(W_n)) \sim \sigma^2 \,(2n)^d$ (as n →? ∞) and its existence is guaranteed whenever the corresponding reduced covariance measure $\gamma^{(2)}_{red}(\cdot)$ has finite total variation. Depending on the rate of decay (polynomially or exponentially) of the total variation of $\gamma^{(2)}_{red}(\cdot)$ outside of an expanding ball centered at the origin, we determine optimal bandwidths b _n (up to a constant) minimizing the mean squared error of $\widehat{\sigma}^2_n$ . The case when $\gamma^{(2)}_{red}(\cdot)$ has bounded support is of particular interest. Further we suggest an isotropised estimator $\widetilde{\sigma}^2_n$ suitable for motion-invariant point processes and compare its properties with $\widehat{\sigma}^2_n$ . Our theoretical results are illustrated and supported by a simulation study which compares the (relative) mean squared errors of $\widehat{\sigma}^2_n$ for planar Poisson, Poisson cluster, and hard-core point processes and for various values of n b _n .     

Some stability estimates for the symmetrized first eigenfunction of certain elliptic operators

We prove two stability-type estimates involving the Schwarz rearrangement of the normalized first eigenfunction u ₁?>?0 of certain linear elliptic operators whose first eigenvalue λ₁ is close to the lowest possible one (i.e., ${\lambda_1^\star}$ , the first eigenvalue of the Dirichlet Laplacian in a suitable ball). In particular, we prove that if ${\lambda_1\approx \lambda_1^\star}$ then the L ^∞-distance between the rearrangement ${u_1^\star}$ and the normalized first eigenfunction of the Dirichlet Laplacian corresponding to ${\lambda_1^\star}$ is less than a suitable power of the difference ${\lambda_1-\lambda_1^\star}$ times a universal constant. We also show that the L ^∞-distance between the first eigenfunction of the Dirichlet Laplacian in a ball whose first eigenvalue equals λ₁ and the rearrangement ${u_1^\star}$ can be controlled with a power of the value assumed by ${u_1^\star}$ on the boundary of that ball.     

On a variant of Rado’s selection lemma and its equivalence with the Boolean prime ideal theorem

We establish that, in ZF (i.e., Zermelo–Fraenkel set theory minus the Axiom of Choice AC), the statement RLT: Given a set I and a non-empty set \({\mathcal{F}}\) of non-empty elementary closed subsets of 2 ^I satisfying the fip, if \({\mathcal{F}}\) has a choice function, then \({\bigcap\mathcal{F} \ne \emptyset}\) , which was introduced in Morillon (Arch Math Logic 51(7–8):739–749, 2012), is equivalent to the Boolean Prime Ideal Theorem (see Sect. 1 for terminology). The result provides, on one hand, an affirmative answer to Morillon’s corresponding question in Morillon (2012) and, on the other hand, a negative answer—in the setting of ZFA (i.e., ZF with the axiom of extensionality weakened to permit the existence of atoms)—to the question in Morillon (2012) of whether RLT is equivalent to Rado’s selection lemma.     

Monadic MV-algebras I: a study of subvarieties

In this paper, we study and classify some important subvarieties of the variety of monadic MV-algebras. We introduce the notion of width of a monadic MV-algebra and we prove that the equational class of monadic MV-algebras of finite width k is generated by the monadic MV-algebra [0, 1] ^k . We describe completely the lattice of subvarieties of the subvariety ${\mathcal{V}([{\bf 0}, {\bf 1}]^k)}$ generated by [0, 1] ^k . We prove that the subvariety generated by a subdirectly irreducible monadic MV-algebra of finite width depends on the order and rank of ?A, the partition associated to A of the set of coatoms of the boolean subalgebra B(A) of its complemented elements, and the width of the algebra. We also give an equational basis for each proper subvariety in ${\mathcal{V}([{\bf 0}, {\bf 1}]^k)}$ . Finally, we give some results about subvarieties of infinite width.     

Bergman and Calderón Projectors for Dirac Operators

For a Dirac operator $D_{\bar{g}}$ over a spin compact Riemannian manifold with boundary $(\bar{X},\bar{g})$ , we give a new construction of the Calderón projector on $\partial\bar{X}$ and of the associated Bergman projector on the space of L ² harmonic spinors on $\bar{X}$ , and we analyze their Schwartz kernels. Our approach is based on the conformal covariance of $D_{\bar{g}}$ and the scattering theory for the Dirac operator associated with the complete conformal metric $g=\bar{g}/\rho^{2}$ where ρ is a smooth function on $\bar{X}$ which equals the distance to the boundary near $\partial\bar{X}$ . We show that $\frac{1}{2}(\operatorname{Id}+\tilde{S}(0))$ is the orthogonal Calderón projector, where $\tilde{S}(\lambda)$ is the holomorphic family in {?(λ)≥0} of normalized scattering operators constructed in Guillarmou et al. (Adv. Math., 225(5):2464–2516, 2010), which are classical pseudo-differential of order 2λ. Finally, we construct natural conformally covariant odd powers of the Dirac operator on any compact spin manifold.     

A Triangulation of ?P 3 as Symmetric Cube of S 2

The symmetric group $\operatorname{Sym}(d)$ acts on the Cartesian product (S ²) ^d by coordinate permutation, and the quotient space $(S^{2})^{d}/\operatorname{Sym}(d)$ is homeomorphic to the complex projective space ?P ^d . We used the case d=2 of this fact to construct a 10-vertex triangulation of ?P ² earlier. In this paper, we have constructed a 124-vertex simplicial subdivision $(S^{2})^{3}_{124}$ of the 64-vertex standard cellulation $(S^{2}_{4})^{3}$ of (S ²)³, such that the $\operatorname{Sym}(3)$ -action on this cellulation naturally extends to an action on $(S^{2})^{3}_{124}$ . Further, the $\operatorname{Sym}(3)$ -action on $(S^{2})^{3}_{124}$ is ??good??, so that the quotient simplicial complex $(S^{2})^{3}_{124}/\operatorname{Sym}(3)$ is a 30-vertex triangulation $\mathbb{C}P^{3}_{30}$ of ?P ³. In other words, we have constructed a simplicial realization $(S^{2})^{3}_{124} \to\mathbb{C} P^{3}_{30}$ of the branched covering (S ²)³???P ³.     

Two results for monocompact measures

For every finite measure space (Ω,A, P) whereA is K₁-generated we prove the equivalence of compactness and monocompactness for P . Moreover, we prove the existence of a perfect, not monocompaot probability, thus answering an open question in [6]. Let P be a charge on the algebraA andK ?A be a monocompact class. We show that P is o-additive ifK ^S P-approximatesK ^S, the family of finite unions inK , needs not to be monocompact.     

On the functional codes defined by quadrics and Hermitian varieties

In recent years, functional codes have received much attention. In his PhD thesis, F.A.B. Edoukou investigated various functional codes linked to quadrics and Hermitian varieties defined in finite projective spaces (Edoukou, PhD Thesis, 2007). This work was continued in (Edoukou et al., Des Codes Cryptogr 56:219–233, 2010; Edoukou et al., J Pure Appl Algebr 214:1729–1739, 2010; Hallez and Storme, Finite Fields Appl 16:27–35, 2010), where the results of the thesis were improved and extended. In particular, Hallez and Storme investigated the functional codes ${C_2(\mathcal{H})}$ , with ${\mathcal{H}}$ a non-singular Hermitian variety in PG(N, q ²). The codewords of this code are defined by evaluating the points of ${\mathcal{H}}$ in the quadratic polynomials defined over ${\mathbb{F}_{q^2}}$ . We now present the similar results for the functional code ${C_{Herm}(\mathcal{Q})}$ . The codewords of this code are defined by evaluating the points of a non-singular quadric ${\mathcal{Q}}$ in PG(N, q ²) in the polynomials defining the Hermitian varieties of PG(N, q ²).     

The Mean Curvature of a Transversely Orientable Foliation

In this work we study a codimension-one C^∞-foliation ${cal F}$ of a complete Riemannian manifold M. We assume that ${cal F}$ is transversely orientable. Under this hypothesis, we show that the mean curvature function of ${cal F}$ has a superior limit. Using this result, we find a necessary and sufficient condition for the foliation ${cal F}$ to be totally geodesic.