Handelman’s hierarchy for the maximum stable set problem

The maximum stable set problem is a well-known NP-hard problem in combinatorial optimization, which can be formulated as the maximization of a quadratic square-free polynomial over the (Boolean) hypercube. We investigate a hierarchy of linear programming relaxations for this problem, based on a result of Handelman showing that a positive polynomial over a polytope with non-empty interior can be represented as conic combination of products of the linear constraints defining the polytope. We relate the rank of Handelman’s hierarchy with structural properties of graphs. In particular we show a relation to fractional clique covers which we use to upper bound the Handelman rank for perfect graphs and determine its exact value in the vertex-transitive case. Moreover we show two upper bounds on the Handelman rank in terms of the (fractional) stability number of the graph and compute the Handelman rank for several classes of graphs including odd cycles and wheels and their complements. We also point out links to several other linear and semidefinite programming hierarchies.     

Semi-Lagrangian relaxation applied to?the?uncapacitated facility location problem

We show how the performance of general purpose Mixed Integer Programming (MIP) solvers, can be enhanced by using the Semi-Lagrangian Relaxation (SLR) method. To illustrate this procedure we perform computational experiments on large-scale instances of the Uncapacitated Facility Location (UFL) problems with unknown optimal values. CPLEX solves 3 out of the 36 instances. By combining CPLEX with SLR, we manage to solve 18 out of the 36 instances and improve the best known lower bound for the other instances. The key point has been that, on average, the SLR approach, has reduced by more than 90% the total number of relevant UFL variables.     

What is the theory without power set?

We show that the theory , consisting of the usual axioms of but with the power set axiom removed—specifically axiomatized by extensionality, foundation, pairing, union, infinity, separation, replacement and the assertion that every set can be well‐ordered—is weaker than commonly supposed and is inadequate to establish several basic facts often desired in its context. For example, there are models of in which ω₁ is singular, in which every set of reals is countable, yet ω₁ exists, in which there are sets of reals of every size , but none of size , and therefore, in which the collection axiom fails; there are models of for which the ?o? theorem fails, even when the ultrapower is well‐founded and the measure exists inside the model; there are models of for which the Gaifman theorem fails, in that there is an embedding of models that is Σ₁‐elementary and cofinal, but not elementary; there are elementary embeddings of models whose cofinal restriction is not elementary. Moreover, the collection of formulas that are provably equivalent in to a Σ₁‐formula or a Π₁‐formula is not closed under bounded quantification. Nevertheless, these deficits of are completely repaired by strengthening it to the theory , obtained by using collection rather than replacement in the axiomatization above. These results extend prior work of Zarach 18 .     

How many data clusters are in the Galaxy data set?

Advances in Data Analysis and Classification - In model-based clustering, the Galaxy data set is often used as a benchmark data set to study the performance of different modeling approaches. Aitkin...     

How likely is Buffon's ring toss to intersect a planar Cantor set?

In Bateman and Volberg (2008) [1], it was shown that the n-th partial 1/4 Cantor in the plane set decays in Favard length no faster than $C\frac{\log n}{n}$. In Bond and Volberg (2008) [2], the so-called circular Favard length of the same set is studied, and the same estimate is shown to persist when the circle has radius $r?Cn$. By considering characteristic functions, the result of Bond and Volberg (2008) [2] naturally leads to a conjecture which (if true) would imply the sharpness of the $L\log \log L$ boundedness of the circular maximal operator proved by Seeger, Tao and Wright (2005) [3].     

Lelek?s problem is not a metric problem

We show that Lelek?s problem on the chainability of continua with span zero is not a metric problem: from a non-metric counterexample one can construct a metric one.     

How Close is the Sample Covariance Matrix to?the?Actual Covariance Matrix?

Given a probability distribution in ? ⁿ with general (nonwhite) covariance, a classical estimator of the covariance matrix is the sample covariance matrix obtained from a sample of N independent points. What is the optimal sample size N=N(n) that guarantees estimation with a fixed accuracy in the operator norm? Suppose that the distribution is supported in a centered Euclidean ball of radius $O(\sqrt{n})$ . We conjecture that the optimal sample size is N=O(n) for all distributions with finite fourth moment, and we prove this up to an iterated logarithmic factor. This problem is motivated by the optimal theorem of Rudelson (J. Funct. Anal. 164:60?C72, 1999), which states that N=O(nlog?n) for distributions with finite second moment, and a recent result of Adamczak et al. (J. Am. Math. Soc. 234:535?C561, 2010), which guarantees that N=O(n) for subexponential distributions.     

How strict is strictification?

The subject of this paper is the higher structure of the strictification adjunction, which relates the two fundamental bases of three-dimensional category theory: the Gray-category of 2-categories and the tricategory of bicategories. We show that – far from requiring the full weakness provided by the definitions of tricategory theory – this adjunction can be strictly enriched over the symmetric closed multicategory of bicategories defined by Verity. Moreover, we show that this adjunction underlies an adjunction of bicategory-enriched symmetric multicategories. An appendix introduces the symmetric closed multicategory of pseudo double categories, into which Verity's symmetric multicategory of bicategories embeds fully.     

How Competitive is the ADI for Tensor Structured Equations?

In [1] we presented an extension of the alternating direction implicit (ADI) method for the solution of Lyapunov equations (1) to higher dimensional problems. The vectorized form of the Lyapunov equation is We considered the generalization of this equation of the form (2) The tensor train structure is one possible generalization of the low rank factorization we find in the right hand side of (1). Therefor we assume B to be of tensor train structure. We showed that in analogy to the low rank ADI case the solution X can be generated in tensor train structure, too. Further we provided an algorithm that computes X using a generalization of the ADI method. Here we compare our new tensor ADI method with an density matrix renormalization group (DMRG) solver for tensor train matrix equations and with matrix equation solvers to investigate the competitiveness of our new solver. (© 2012 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

How Accurate is the Streamline Diffusion Finite Element Method?

We investigate the optimal accuracy of the streamline diffusion finite element method applied to convection-dominated problems. For linear/bilinear elements the theoretical order of convergence given in the literature is either for quasi-uniform meshes or for some uniform meshes. The determination of the optimal order in general was an open problem. By studying a special type of meshes, it is shown that the streamline diffusion method may actually converge with any order within this range depending on the characterization of the meshes.

     

How rich is the class of multifractional Brownian motions?

The multifractional Brownian motion (MBM) processes are locally self-similar Gaussian processes. They extend the classical fractional Brownian motion processes _BH={_BH(t)_}t∈R$B_H=\{B_H(t){\}}_{t\in \mathbb{R}}$ by allowing their self-similarity parameter H∈(0,1)$H\in (0,1)$ to depend on time.     

On the lattice structure of the set of stable matchings for a many-to-one model ∗

For the many-to-one matching model with firms having substitutable and q-separable preferences we propose two very natural binary operations that together with the unanimous partial ordering of the workers endow the set of stable matchings with a lattice structure. We also exhibit examples in which, under this restricted domain of firms' preferences, the classical binary operations may not even be matching     

The kidney exchange problem: How hard is it to find a donor?

The most effective treatment for kidney failure that is currently known is transplantation. However, the supply of kidneys from cadaveric donors does not meet the fast-growing demand and the kidney from a willing living donor (genetically or emotionally relative of the patient) is often not suitable for immunological reasons. Therefore in several countries attempts have started to organize exchanges of kidneys between incompatible patient-donor pairs. On the theoretical side, game-theoretical models have been proposed to analyze various optimality criteria for such exchanges and various search schemes have been tested. One possibility to model patients’ preferences is to take into account in the first step the suitability of the donated kidney and in the second step the length of the obtained cycle of exchanges. Although the core of such a cooperative game is always nonempty and one solution can be found by the famous Top Trading Cycles algorithm, in this paper we show that many questions concerning the structure of the core are difficult to answer.     

Properties of solutions of the Tricomi problem for the Lavrent’ev-Bitsadze equation at corner points

We consider the Tricomi problem for the Lavrent’ev-Bitsadze equation for the case in which the elliptic part of the boundary is part of a circle. For the homogeneous equation, we introduce a new class of solutions that are not continuous at the corner points of the domain and construct nontrivial solutions in this class in closed form. For the inhomogeneous equation, we introduce the notion of an n-regular solution and prove a criterion for the existence of such a solution.     

Some new monotonicity formulas and the singular set in the lower dimensional obstacle problem

We construct two new one-parameter families of monotonicity formulas to study the free boundary points in the lower dimensional obstacle problem. The first one is a family of Weiss type formulas geared for points of any given homogeneity and the second one is a family of Monneau type formulas suited for the study of singular points. We show the uniqueness and continuous dependence of the blowups at singular points of given homogeneity. This allows to prove a structural theorem for the singular set. Our approach works both for zero and smooth non-zero lower dimensional obstacles. The study in the latter case is based on a generalization of Almgren’s frequency formula, first established by Caffarelli, Salsa, and Silvestre. N. Garofalo is supported in part by NSF grant DMS-0701001. A. Petrosyan is supported in part by NSF grant DMS-0701015.