Primal separation algorithms

Given an integer polyhedron , an integer point , and a point , the primal separation problem is the problem of finding a linear inequality which is valid for P _I , violated by x ^*, and satisfied at equality by . The primal separation problem plays a key role in the primal approach to integer programming. In this paper we examine the complexity of primal separation for several well-known classes of inequalities for various important combinatorial optimization problems, including the knapsack, stable set and travelling salesman problems.Received: November 2002, Revised: March 2003,     

On Weighted Poincaré Inequalities

We are concerned with the problem of finding sharp summability conditions on the weights which render certain weighted inequalities of Poincaré - type true. The conditions we find consist of proper integral balances between the growths of the rearrangements of the weights.     

Is breaking of ensemble equivalence monotone in the number of constraints?

Breaking of ensemble equivalence between the microcanonical ensemble and the canonical ensemble may occur for random graphs whose size tends to infinity, and is signaled by a non-zero specific relative entropy between the two ensembles. In Garlaschelli et al. (2017) and Garlaschelli et al. (0000) it was shown that breaking occurs when the constraint is put on the degree sequence (configuration model). It is not known what is the effect on the relative entropy when the number of constraints is reduced, i.e., when only part of the nodes are constrained in their degree (and the remaining nodes are left unconstrained). Intuitively, the relative entropy is expected to decrease. However, this is not a trivial issue because when constraints are removed both the microcanonical ensemble and the canonical ensemble change. In this paper a formula for the relative entropy valid for generic discrete random structures, recently formulated by Squartini and Garlaschelli, is used to prove that the relative entropy is monotone in the number of constraints when the constraint is on the degrees of the nodes. It is further shown that the expression for the relative entropy corresponds, in the dense regime, to the degrees in the microcanonical ensemble being asymptotically multivariate Dirac and in the canonical ensemble being asymptotically Gaussian.     

Nonlinear Double-well Schrödinger Equations in the Semiclassical Limit

We consider time-dependent Schrödinger equations with a double well potential and an external nonlinear, both local and non-local, perturbation. In the semiclassical limit, the finite dimensional eigenspace associated to the lowest eigenvalues of the linear operator is almost invariant for times of the order of the beating period and the dominant term of the wavefunction is given by means of the solutions of a finite dimensional dynamical system. In the case of local nonlinear perturbation, we assume the spatial dimension d=1 or d=2.     

Power-law time distribution of large earthquakes

We study the statistical properties of time distribution of seismicity in California by means of a new method of analysis, the diffusion entropy. We find that the distribution of time intervals between a large earthquake (the main shock of a given seismic sequence) and the next one does not obey Poisson statistics, as assumed by the current models. We prove that this distribution is an inverse power law with an exponent mu=2.06+/-0.01. We propose the long-range model, reproducing the main properties of the diffusion entropy and describing the seismic triggering mechanisms induced by large earthquakes.     

On the structure of 3‐acetylamino‐5‐methyl‐1,2,4‐oxadiazole and on the fully degenerate rearrangements (FDR) of its anion: a stimulating comparison between the results of ‘in‐silicon chemistry’ and ‘laboratory chemistry’

An accurate crystal structure determination has provided evidence for a planar conformation for 3‐acetylamino‐5‐methyl‐1,2,4‐oxadiazole ( 5 ), in agreement with quantum‐mechanical calculations in the gas phase. In the crystal, a series of strong intermolecular N7H7^….O9 hydrogen bonds link the amido groups of different molecules, causing the formation of infinite parallel ordered chains. The effect of the DMSO solvent on the energy and charge distribution of compound 5 and on its relevant 5 ^? anion, involved in a fully degenerate rearrangement (FDR), has been deepened by quantum‐mechanical DFT calculations. The calculated energy barrier for the FDR increases in going from in vacuo to DMSO, in agreement with previsions based on the Hughes and Ingold rules concerning the nucleophilic substitution of an anionic reagent (the deprotonated amido group in the side chain) on a neutral substrate (the 1,2,4‐oxadiazole ring). Copyright © 2009 John Wiley & Sons, Ltd.     

On the complexity of some subgraph problems

We study the complexity of the problem of deciding the existence of a spanning subgraph of a given graph, and of that of finding a maximum (weight) such subgraph. We establish some general relations between these problems, and we use these relations to obtain new NP-completeness results for maximum (weight) spanning subgraph problems from analogous results for existence problems and from results in extremal graph theory. On the positive side, we provide a decomposition method for the maximum (weight) spanning chordal subgraph problem that can be used, e.g., to obtain a linear (or O(nlogn)) time algorithm for such problems in graphs with vertex degree bounded by 3.     

The Behavior of Solutions of Multidimensional Aggregation Equations with Mildly Singular Interaction Kernels

The authors consider the multidimensional aggregation equation tp-div（p K＊ ρ） = 0 in which the radially symmetric attractive interaction kernel has a mild singularity at the origin （Lipschitz or better）, and review recent results on this problem concerning well-posedness of nonnegative solutions and finite time blowup in multiple space dimensions depending on the behavior of the kernel at the origin. The problem with bounded initial data, data in L^p ∩ L^1, and measure solutions are also considered.     

Closed trail decompositions of complete equipartite graphs

The complete equipartite graph $K_m * {\overline{K_n}}$ has mn vertices partitioned into m parts of size n, with two vertices adjacent if and only if they are in different parts. In this paper, we determine necessary and sufficient conditions for the existence of a decomposition of $K_m * {\overline{K_n}}$ into closed trails of length k. © 2009 Wiley Periodicals, Inc. J Combin Designs 17: 374–403, 2009