Primal separation for 0/1 polytopes

 The 0/1 primal separation problem is: Given an extreme point xˉ of a 0/1 polytope P and some point x ^*, find an inequality which is tight at xˉ, violated by x ^* and valid for P or assert that no such inequality exists. It is known that this separation variant can be reduced to the standard separation problem for P. We show that 0/1 optimization and 0/1 primal separation are polynomial time equivalent. This implies that the problems 0/1 optimization, 0/1 standard separation, 0/1 augmentation, and 0/1 primal separation are polynomial time equivalent. Then we provide polynomial time primal separation procedures for matching, stable set, maximum cut, and maximum bipartite graph problems, giving evidence that these algorithms are conceptually simpler and easier to implement than their corresponding counterparts for standard separation. In particular, for perfect matching we present an algorithm for primal separation that rests only on simple max-flow computations. In contrast, the known standard separation method relies on an explicit minimum odd cut algorithm. Consequently, we obtain a very simple proof that a maximum weight perfect matching of a graph can be computed in polynomial time. Received: August 20, 2001 / Accepted: April 2002 Published online: December 9, 2002 RID="⋆" ID="⋆" This research was developed while the author was on leave at the Istituto di Analisi dei Sistemi ed Informatica, Viale Manzoni 30, 00185 Roma, supported by the project TMR-DONET nr. ERB FMRX-CT98-0202 of the European Union. Mathematics Subject Classification (2000): 90C10, 90C60, 90C57     

Separation of the elasticity theory equations with radial inhomogeneity : PMM vol. 38, n 6, 1974, pp. 1139–1144

The separation of a system of three elasticity theory equations in the static case to a system of two equations and one independent equation for a space with a radial inhomogeneity is presented in a spherical coordinate system. These equations are solved by separation of variables for specific kinds of radial inhomogeneity. In particular, solutions are found for the Lamé coefficients μ = const, λ (ifr) is an arbitrary function, μ = μ_or^β, λ = λ_or^β.While methods of solving problems associated with the equilibrium of an elastic homogeneous sphere have been studied sufficiently [1], problems with spherical symmetry of the boundary conditions have mainly been solved for an inhomogeneous sphere [2, 3],For a particular kind of inhomogeneity dependent on one Cartesian coordinate, the equations have been separated completely in [4], A system of three equations with a radial inhomogeneity in a spherical coordinate system is separated below by a method analogous to [4].     

On the separation of maximally violated mod-k cuts

Separation is of fundamental importance in cutting-plane based techniques for Integer Linear Programming (ILP). In recent decades, a considerable research effort has been devoted to the definition of effective separation procedures for families of well-structured cuts. In this paper we address the separation of Chvátal rank-1 inequalities in the context of general ILP’s of the form min{c ^T x:Ax≤b,x integer}, where A is an m×n integer matrix and b an m-dimensional integer vector. In particular, for any given integer k we study mod-k cuts of the form λ ^T Ax≤⌊λ ^T b⌋ for any λ∈{0,1/k,...,(k−1)/k} ^m such that λ ^T A is integer. Following the line of research recently proposed for mod-2 cuts by Applegate, Bixby, Chvátal and Cook [1] and Fleischer and Tardos [19], we restrict to maximally violated cuts, i.e., to inequalities which are violated by (k−1)/k by the given fractional point. We show that, for any given k, such a separation requires O(mn min{m,n}) time. Applications to both the symmetric and asymmetric TSP are discussed. In particular, for any given k, we propose an O(|V|²|E ^*|)-time exact separation algorithm for mod-k cuts which are maximally violated by a given fractional (symmetric or asymmetric) TSP solution with support graph G ^*=(V,E ^*). This implies that we can identify a maximally violated cut for the symmetric TSP whenever a maximally violated (extended) comb inequality exists. Finally, facet-defining mod-k cuts for the symmetric and asymmetric TSP are studied. Received May 29, 1997 / Revised version received May 10, 1999?Published online November 9, 1999     

Separation properties inX and 2 X . Upper semicontinuous and measurable multifunctions

This paper investigates relations among some separation (countable separation) properties of a topological space (X, τ _X ), corresponding properties of the hyperspace 2 ^X , endowed with the finite topology (the σ-algebra σ(ν ⁺)), and closedness (measurability) of graphs of semicontinuous (measurable) multifunctions.     

Separation conditions for conformal iterated function systems

We extend both the weak separation condition and the finite type condition to include finite iterated function systems (IFSs) of injective C ¹ conformal contractions on compact subsets of \mathbbR^d{{\mathbb{R}}^d} . For conformal IFSs satisfying the bounded distortion property, we prove that the finite type condition implies the weak separation condition. By assuming the weak separation condition, we prove that the Hausdorff and box dimensions of the attractor are equal and, if the dimension of the attractor is α, then its α-dimensional Hausdorff measure is positive and finite. We obtain a necessary and sufficient condition for the associated self-conformal measure μ to be singular. By using these we give a first example of a singular invariant measure μ that is associated with a non-linear IFS with overlaps.     

Upper bound on the coarsening rate for an epitaxial growth model

We study a specific example of energy‐driven coarsening in two space dimensions. The energy is ∫|??u|² + (1 ‐ | ?u|²)²; the evolution is the fourth‐order PDE representing steepest descent. This equation has been proposed as a model of epitaxial growth for systems with slope selection. Numerical simulations and heuristic arguments indicate that the standard deviation of u grows like t^1/3, and the energy per unit area decays like t^‐1/3. We prove a weak, one‐sided version of the latter statement: The time‐averaged energy per unit area decays no faster than t^‐1/3. Our argument follows a strategy introduced by Kohn and Otto in the context of phase separation, combining (i) a dissipation relation, (ii) an isoperimetric inequality, and (iii) an ODE lemma. The interpolation inequality is new and rather subtle; our proof is by contradiction, relying on recent compactness results for the Aviles‐Giga energy. © 2003 Wiley Periodicals, Inc.     

Robust a-posteriori error control of Cahn-Hilliard type equations with elasticity

Phase separation of an initially homogeneous mixture into two different phases can be modeled on a mesoscopic scale by the Cahn-Hilliard equation. The interface thickness between the pure phases enters as a small parameter γ into this mass conserving fourth order semilinear parabolic equation. Numerical analysis is well established for a fixed parameter size, but error estimates depend exponentially on γ^–1 and thus become useless if γ → 0. We consider the case, that elastic stresses due to a lattice misfit become important and the equation has to be coupled to a system of linear elasticity. Applications include e. g. the simulation of Sn-Cu alloys for the production of lead free solder or Ni-Al alloys used for rotor blade surfaces. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Random walks and an O*(n5) volume algorithm for convex bodies

Given a high dimensional convex body K⊆ℝⁿ by a separation oracle, we can approximate its volume with relative error ε, using O*(n⁵) oracle calls. Our algorithm also brings the body into isotropic position. As all previous randomized volume algorithms, we use “rounding” followed by a multiphase Monte-Carlo (product estimator) technique. Both parts rely on sampling (generating random points in K), which is done by random walk. Our algorithm introduces three new ideas: the use of the isotropic position (or at least an approximation of it) for rounding; the separation of global obstructions (diameter) and local obstructions (boundary problems) for fast mixing; and a stepwise interlacing of rounding and sampling. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 11 , 1–50, 1997     

Riesz Spherical Potentials with External Fields and Minimal Energy Points Separation

In this paper we consider the minimal energy problem on the sphere S ^d for Riesz potentials with external fields. Fundamental existence, uniqueness, and characterization results are derived about the associated equilibrium measure. The discrete problem and the corresponding weighted Fekete points are investigated. As an application we obtain the separation of the minimal s-energy points for d – 2 < s < d. The explicit form of the separation constant is new even for the classical case of s = d – 1. Research supported, in part, by a National Science Foundation Research grant DMS 0532154.     

Query complexity,or why is it difficult to separateNP A ∩coNP A fromP A by random oraclesA?

By thequery-time complexity of a relativized algorithm we mean the total length of oracle queries made; thequery-space complexity is the maximum length of the queries made. With respect to these cost measures one can define polynomially time- or space-bounded deterministic, nondeterministic, alternating, etc. Turing machines and the corresponding complexity classes. It turns out that all known relativized separation results operate essentially with this cost measure. Therefore, if certain classes do not separate in the query complexity model, this can be taken as an indication that their relativized separation in the classical cost model will require entirely new principles.A notable unresolved question in relativized complexity theory is the separation of NP^A co NP^A fromP ^A under random oraclesA. We conjecture that the analogues of these classes actually coincide in the query complexity model, thus indicating an answer to the question in the title. As a first step in the direction of establishing the conjecture, we prove the following result, where polynomial bounds refer to query complexity.If two polynomially query-time-bounded nondeterministic oracle Turing machines accept precisely complementary (oracle dependent) languages L^A and {0, 1}^*L^A under every oracle A then there exists a deterministic polynomially query-time-bounded oracle Turing machine that accept L^A. The proof involves a sort of greedy strategy to selecting deterministically, from the large set of prospective queries of the two nondeterministic machines, a small subset that suffices to perform an accepting computation in one of the nondeterministic machines. We describe additional algorithmic strategies that may resolve the same problem when the condition holds for a (1–) fraction of the oracles A, a step that would bring us to a non-uniform version of the conjecture. Thereby we reduce the question to a combinatorial problem on certain pairs of sets of partial functions on finite sets.     

Some properties of set-open topologies

The space of continuous real-valued functions with set-open topology is studied. The coincidence of the set-open topologies for various families λ is considered and conditions for a set-open topology to coincide with the uniform topology are investigated. The separation axioms in the spaces C ^λ(X) are studied. Criteria for the local compactness and σ-compactness of C ^λ(X) are given. __________ Translated from Sovremennaya Matematika i Ee Prilozheniya (Contemporary Mathematics and Its Applications), Vol. 34, General Topology, 2005.     

Antiweb-wheel inequalities and their separation problems over the stable set polytopes

A stable set in a graph G is a set of pairwise nonadjacent vertices. The problem of finding a maximum weight stable set is one of the most basic ℕℙ-hard problems. An important approach to this problem is to formulate it as the problem of optimizing a linear function over the convex hull STAB(G) of incidence vectors of stable sets. Since it is impossible (unless ℕℙ=coℕℙ) to obtain a “concise” characterization of STAB(G) as the solution set of a system of linear inequalities, it is a more realistic goal to find large classes of valid inequalities with the property that the corresponding separation problem (given a point x ^*, find, if possible, an inequality in the class that x ^* violates) is efficiently solvable.?Some known large classes of separable inequalities are the trivial, edge, cycle and wheel inequalities. In this paper, we give a polynomial time separation algorithm for the (t)-antiweb inequalities of Trotter. We then introduce an even larger class (in fact, a sequence of classes) of valid inequalities, called (t)-antiweb-s-wheel inequalities. This class is a common generalization of the (t)-antiweb inequalities and the wheel inequalities. We also give efficient separation algorithms for them. Received: June 2000 / Accepted: August 2001?Published online February 14, 2002     

Yan Theorem in L∞ with Applications to Asset Pricing

We prove an L~∞ version of the Yan theorem and deduce from it a necessary condition for theabsence of free lunches in a model of financial markets,in which asset prices are a continuous R~d valued processand only simple investment strategies are admissible.Our proof is based on a new separation theorem for convexsets of finitely additive measures.     

The scaling limit for a stochastic PDE and the separation of phases

Summary We investigate the problem of singular perturbation for a reaction-diffusion equation with additive noise (or a stochastic partial differential equation of Ginzburg-Landau type) under the situation that the reaction term is determined by a potential with double-wells of equal depth. As the parameter (the temperature of the system) tends to 0, the solution converges to one of the two stable phases and consequently the phase separation is formed in the limit. We derive a stochastic differential equation which describes the random movement of the phase separation point. The proof consists of two main steps. We show that the solution stays near a manifoldM of minimal energy configurations based on a Lyapunov type argument. Then, the limit equation is identified by introducing a nice coordinate system in a neighborhood ofM .Research partially supported by Japan Society for the Promotion of Science     

On point energies, separation radius and mesh norm for -extremal configurations on compact sets in

We investigate bounds for point energies, separation radius, and mesh norm of certain arrangements of N points on sets A from a class of d-dimensional compact sets embedded in R^d′, 1dd^′. We assume that these points interact through a Riesz potential V=|·|^-s, where s>0 and |·| is the Euclidean distance in . With and denoting, respectively, the separation radius and mesh norm of s-extremal configurations, which are defined to yield minimal discrete Riesz s-energy, we show, in particular, the following.(A) For the d-dimensional unit sphere and s<d-1, and, moreover, if sd-2. The latter result is sharp in the case s=d-2. In addition, point energies for s-extremal configurations are asymptotically equal. This observation relates to numerical experiments on observed scar defects in certain biological systems.(B) For and s>d, and the mesh ratio is uniformly bounded for a wide subclass of . We also conclude that point energies for s-extremal configurations have the same order, as N→∞.     

Herbrandizing search problems in Bounded Arithmetic

We study search problems and reducibilities between them with known or potential relevance to bounded arithmetic theories. Our primary objective is to understand the sets of low complexity consequences (esp. Σ^b₁ or Σ^b₂) of theories Sⁱ₂ and Tⁱ₂ for a small i, ideally in a rather strong sense of characterization; or, at least, in the standard sense of axiomatization. We also strive for maximum combinatorial simplicity of the characterizations and axiomatizations, eventually sufficient to prove conjectured separation results. To this end two techniques based on the Herbrand's theorem are developed. They characterize/axiomatize Σ^b₁‐consequences of Σ^b₂‐definable search problems, while the method based on the more involved concept of characterization is easier and gives more transparent results. This method yields new proofs of Buss' witnessing theorem and of the relation between PLS and Σ^b₁(T¹₂), and also an axiomatization of Σ^b₁(T²₂). (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Dynamic ordinal analysis

 Dynamic ordinal analysis is ordinal analysis for weak arithmetics like fragments of bounded arithmetic. In this paper we will define dynamic ordinals – they will be sets of number theoretic functions measuring the amount of sΠ ^b ₁(X) order induction available in a theory. We will compare order induction to successor induction over weak theories. We will compute dynamic ordinals of the bounded arithmetic theories sΣ ^b _n (X)−L ^m IND for m=n and m=n+1, n≥0. Different dynamic ordinals lead to separation. In this way we will obtain several separation results between these relativized theories. We will generalize our results to further languages extending the language of bounded arithmetic. Received: 27 April 2001 / Published online: 19 December 2002 The results for sΣ ^b _n (X)−L ^m IND are part of the authors dissertation [3]; the results for sΣ ^b _m (X)−L ^m+1 IND base on results of ARAI [1]. Mathematics Subject Classification (2000): Primary 03F30; Secondary 03F05, 03F50 Key words or phrases: Dynamic ordinal – Bounded arithmetic – Proof-theoretic ordinal – Order induction – Semi-formal system – Cut-elimination     

Exact solutions of the modified Korteweg-de Vries equation

We use the inverse scattering method to obtain a formula for certain exact solutions of the modified Korteweg-de Vries (mKdV) equation. Using matrix exponentials, we write the kernel of the relevant Marchenko integral equation as W( x + y;t ) = Ce ^{- ( x + y )A} e^{8A3 t} B\Omega \left( {x + y;t} \right) = Ce^{ - \left( {x + y} \right)A} e^{8A^3 t} BB, where the real matrix triplet (A,B,C) consists of a constant p×p matrix A with eigenvalues having positive real parts, a constant p×1 matrix B, and a constant 1× p matrix C for a positive integer p. Using separation of variables, we explicitly solve the Marchenko integral equation, yielding exact solutions of the mKdV equation. These solutions are constructed in terms of the unique solution P of the Sylvester equation AP + PA = BC or in terms of the unique solutions Q and N of the Lyapunov equations A^°Q + QA = C^°C and AN + NA^° = BB^°, where B^°denotes the conjugate transposed matrix. We consider two interesting examples.