-measures for branching exit Markov systems and their applications to differential equations

Semilinear equations Lu=(u) where L is an elliptic differential operator and is a positive function can be investigated by using (L,)-superdiffusions. In a special case u=u² a powerful probabilistic tool – the Brownian snake – introduced by Le Gall was successfully applied by him and his school to get deep results on solutions of this equation. Some of these results (but not all of them) were extended by Dynkin and Kuznetsov to general equations by applying superprocesses. An important role in the theory of the Brownian snake and its applications is played by measures _x on the space of continuous paths. Our goal is to introduce analogous measures related to superprocesses (and to general branching exit Markov systems). They are defined on the space of measures and we call them -measures. Using -measures allows to combine some advantages of Brownian snakes and of superprocesses as tools for a study of semilinear PDEs.Partially supported by National Science Foundation Grant DMS-0204237 and DMS-9971009Mathematics Subject Classification (2000): Primary 31C15, Secondary 35J65, 60J60     

Optimal 3-terminal cuts and linear programming

Given an undirected graph G=(V,E) and three specified terminal nodes t ₁,t ₂,t ₃, a 3-cut is a subset A of E such that no two terminals are in the same component of G\A. If a non-negative edge weight c _e is specified for each e∈E, the optimal 3-cut problem is to find a 3-cut of minimum total weight. This problem is -hard, and in fact, is max- -hard. An approximation algorithm having performance guarantee has recently been given by Călinescu, Karloff, and Rabani. It is based on a certain linear-programming relaxation, for which it is shown that the optimal 3-cut has weight at most times the optimal LP value. It is proved here that can be improved to , and that this is best possible. As a consequence, we obtain an approximation algorithm for the optimal 3-cut problem having performance guarantee . In addition, we show that is best possible for this algorithm. Research of this author was supported by NSERC PGSB. Research supported by a grant from NSERC of Canada.     

A branch-and-cut algorithm for the stochastic uncapacitated lot-sizing problem

This paper addresses a multi-stage stochastic integer programming formulation of the uncapacitated lot-sizing problem under uncertainty. We show that the classical (ℓ,S) inequalities for the deterministic lot-sizing polytope are also valid for the stochastic lot-sizing polytope. We then extend the (ℓ,S) inequalities to a general class of valid inequalities, called the inequalities, and we establish necessary and sufficient conditions which guarantee that the inequalities are facet-defining. A separation heuristic for inequalities is developed and incorporated into a branch-and-cut algorithm. A computational study verifies the usefulness of the inequalities as cuts. This research has been supported in part by the National Science Foundation under Award number DMII-0121495.     

Critical extreme points of the 2-edge connected spanning subgraph polytope

In this paper we study the extreme points of the polytope P(G), the linear relaxation of the 2-edge connected spanning subgraph polytope of a graph G. We introduce a partial ordering on the extreme points of P(G) and give necessary conditions for a non-integer extreme point of P(G) to be minimal with respect to that ordering. We show that, if is a non-integer minimal extreme point of P(G), then G and can be reduced, by means of some reduction operations, to a graph G' and an extreme point of P(G') where G' and satisfy some simple properties. As a consequence we obtain a characterization of the perfectly 2-edge connected graphs, the graphs for which the polytope P(G) is integral. Received: May, 2004 Part of this work has been done while the first author was visiting the Research Institute for Discrete Mathematics, University of Bonn, Germany.     

On <Emphasis Type="Italic">L</Emphasis><Subscript>α,ω</Subscript> complete extensions of complete theories of Boolean algebras

For a complete first order theory of Boolean algebras T which has nonisomorphic countable models, we determine the first limit ordinal = (T) such that We show that for some and for all other Ts, A nonprincipal ideal I of B is almost principal, if a is a principal ideal of B} is a maximal ideal of B. We show that the theory of Boolean algebras with an almost principal ideal has complete extensions and characterize them by invariants similar to the Tarskis invariants.Mathematics Subject Classification (2000): Primary 03C15, Secondary 03C35, 06E05Revised version: 2 February 2004     

On Cross-intersecting Families of Sets

A family of -element subsets and a family of k-element subsets of an n-element set are cross-intersecting if every set from has a nonempty intersection with every set from . We compare two previously established inequalities each related to the maximization of the product , and give a new and short proof for one of them. We also determine the maximum of for arbitrary positive weights ,_k.     

What is so special with the powerset operation?

The powerset operator, , is an operator which (1) sends sets to sets,(2) is defined by a positive formula and (3) raises the cardinality of its argument, i.e., |(x)|>|x|. As a consequence of (3), has a proper class as least fixed point (the universe itself). In this paper we address the questions: (a) How does contribute to the generation of the class of all positive operators? (b) Are there other operators with the above properties, independent of ? Concerning (a) we show that every positive operator is a combination of the identity, powerset, and almost constant operators. This enables one to define what a -independent operator is. Concerning (b) we show that every -independent bounded positive operator is not -like.Mathematics Subject Classification (2000): Primary 03E05, secondary 03E20     

The volumetric barrier for convex quadratic constraints

Let where and _i is an n×n positive semidefinite matrix. We prove that the volumetric and combined volumetric-logarithmic barriers for are and self-concordant, respectively. Our analysis uses the semidefinite programming (SDP) representation for the convex quadratic constraints defining , and our earlier results on the volumetric barrier for SDP. The self-concordance results actually hold for a class of SDP problems more general than those corresponding to the SDP representation of .Mathematics Subject Classification (1991):90C25, 90C30     

Analysis of nonsmooth vector-valued functions associated with second-order cones

Let be the Lorentz/second-order cone in . For any function f from to , one can define a corresponding function f^soc(x) on by applying f to the spectral values of the spectral decomposition of x with respect to . We show that this vector-valued function inherits from f the properties of continuity, (local) Lipschitz continuity, directional differentiability, Fréchet differentiability, continuous differentiability, as well as (-order) semismoothness. These results are useful for designing and analyzing smoothing methods and nonsmooth methods for solving second-order cone programs and complementarity problems.Mathematics Subject Classification (1991): 26A27, 26B05, 26B35, 49J52, 90C33, 65K05     

Local solvability of the -equation with boundary regularity on weakly q-convex domains

We consider weakly q-convex domains with smooth boundary and show that the -equation is locally solvable with regularity up to the boundary for smooth forms of degree (p,s) for s≥q.     

Proper holomorphic embeddings of finitely and some infinitely connected subsets of into

We show that any finitely connected domain can be properly embedded into . For some sequences can also be properly embedded into .     

2-universal -lattices over real quadratic fields

Let be a real quadratic field with m a square-free positive rational integer, and be the ring of integers in F. An -lattice L on a totally positive definite quadratic space V over F is called r-universal if L represents all totally positive definite -lattices l with rank r over . We prove that there exists no 2-universal -lattice over F with rank less than 6, and there exists a 2-universal -lattice over F with rank 6 if and only if m=2, 5. Moreover there exists only one 2-universal -lattice with rank 6, up to isometry, over .     

On the gap between the quadratic integer programming problem and its semidefinite relaxation

Consider the semidefinite relaxation (SDR) of the quadratic integer program (QIP): where Q is a given symmetric matrix and D is diagonal. We consider the SDR gap We establish the uniqueness of the SDR solution and prove that if and only if γ_r:=n⁻¹max{x^TVV^Tx:x ∈ {-1, 1}ⁿ}=1 where V is an orthogonal matrix whose columns span the (r–dimensional) null space of D−Q and where D is the unique SDR solution. We also give a test for establishing whether that involves 2^r−1 function evaluations. In the case that γ_r<1 we derive an upper bound on γ which is tighter than Thus we show that `breaching' the SDR gap for the QIP problem is as difficult as the solution of a QIP with the rank of the cost function matrix equal to the dimension of the null space of D−Q. This reduced rank QIP problem has been recently shown to be solvable in polynomial time for fixed r.     

Asymptotic laws for regenerative compositions: gamma subordinators and the like

For a random closed set obtained by exponential transformation of the closed range of a subordinator, a regenerative composition of generic positive integer n is defined by recording the sizes of clusters of n uniform random points as they are separated by the points of . We focus on the number of parts K_n of the composition when is derived from a gamma subordinator. We prove logarithmic asymptotics of the moments and central limit theorems for K_n and other functionals of the composition such as the number of singletons, doubletons, etc. This study complements our previous work on asymptotics of these functionals when the tail of the Lévy measure is regularly varying at 0+. Research supported in part by N.S.F. Grant DMS-0071448     

Summing norms of identities between unitary ideals

Based on abstract interpolation, we prove asymptotic formulae for the (F,2)-summing norm of inclusions id: , where E and F are two Banach sequence spaces. Here, stands for the unitary ideal of operators on the n-dimensional Hilbert space whose singular values belong to E, and for the Hilbert-Schmidt operators. Our results are noncommutative analogues of results due to Bennett and Carl, as well as their recent generalizations to Banach sequence spaces. As an application, we give lower and upper estimates for certain s-numbers of the embeddings id: and id: . In the concluding section, we finally consider mixing norms. The second named author was supported by KBN Grant 2 P03A 042 18.     

The feasibility pump

In this paper we consider the NP-hard problem of finding a feasible solution (if any exists) for a generic MIP problem of the form min{c^Tx:Ax≥b,x_j integer ∀j ∈ }. Trivially, a feasible solution can be defined as a point x* ∈ P:={x:Ax≥b} that is equal to its rounding , where the rounded point is defined by := x*_j if j ∈ and := x*_j otherwise, and [·] represents scalar rounding to the nearest integer. Replacing “equal” with “as close as possible” relative to a suitable distance function Δ(x*, ), suggests the following Feasibility Pump (FP) heuristic for finding a feasible solution of a given MIP.We start from any x* ∈ P, and define its rounding . At each FP iteration we look for a point x* ∈ P that is as close as possible to the current by solving the problem min {Δ(x, ): x ∈ P}. Assuming Δ(x, ) is chosen appropriately, this is an easily solvable LP problem. If Δ(x*, )=0, then x* is a feasible MIP solution and we are done. Otherwise, we replace by the rounding of x*, and repeat.We report computational results on a set of 83 difficult 0-1 MIPs, using the commercial software ILOG-Cplex 8.1 as a benchmark. The outcome is that FP, in spite of its simple foundation, proves competitive with ILOG-Cplex both in terms of speed and quality of the first solution delivered. Interestingly, ILOG-Cplex could not find any feasible solution at the root node for 19 problems in our test-bed, whereas FP was unsuccessful in just 3 cases.     

Holomorphic dynamics near germs of singular curves

Let M be a two dimensional complex manifold, p ∈ M and a germ of holomorphic foliation of M at p. Let be a germ of an irreducible, possibly singular, curve at p in M which is a separatrix for . We prove that if the Camacho-Sad-Suwa index Ind then there exists another separatrix for at p. A similar result is proved for the existence of parabolic curves for germs of holomorphic diffeomorphisms near a curve of fixed points.     

Ambiguous chance constrained problems and robust optimization

In this paper we study ambiguous chance constrained problems where the distributions of the random parameters in the problem are themselves uncertain. We focus primarily on the special case where the uncertainty set of the distributions is of the form where ρ_p denotes the Prohorov metric. The ambiguous chance constrained problem is approximated by a robust sampled problem where each constraint is a robust constraint centered at a sample drawn according to the central measure The main contribution of this paper is to show that the robust sampled problem is a good approximation for the ambiguous chance constrained problem with a high probability. This result is established using the Strassen-Dudley Representation Theorem that states that when the distributions of two random variables are close in the Prohorov metric one can construct a coupling of the random variables such that the samples are close with a high probability. We also show that the robust sampled problem can be solved efficiently both in theory and in practice. Research partially supported by NSF grant CCR-00-09972. Research partially supported by NSF grants CCR-00-09972, DMS-01-04282, and ONR grant N000140310514.     

On the zero-distribution of Epstein zeta-functions

We prove that the mean value of the real parts of the nontrivial zeros of the Epstein zeta-function associated with a positive definite quadratic form in n variables is equal to . Furthermore, we show that Epstein zeta-functions in general have an asymmetric zero-distribution with respect to the critical line Re .     

Restriction of the cotangent bundle to elliptic curves and Hilbert-Kunz functions

We describe the possible restrictions of the cotangent bundle to an elliptic curve . We apply this in positive characteristic to the computation of the Hilbert-Kunz function of a homogeneous R₊-primary ideal in the graded section ring .