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 -algorithm for convex minimization

For convex minimization we introduce an algorithm based on -space decomposition. The method uses a bundle subroutine to generate a sequence of approximate proximal points. When a primal-dual track leading to a solution and zero subgradient pair exists, these points approximate the primal track points and give the algorithm's , or corrector, steps. The subroutine also approximates dual track points that are -gradients needed for the method's -Newton predictor steps. With the inclusion of a simple line search the resulting algorithm is proved to be globally convergent. The convergence is superlinear if the primal-dual track points and the objective's -Hessian are approximated well enough. Dedicated to Terry Rockafellar who has had a great influence on our work via strong support for proximal points and for structural definitions that involve tangential convergence. On leave from INRIA Rocquencourt Research of the first author supported by the National Science Foundation under Grant No. DMS-0071459 and by CNPq (Brazil) under Grant No. 452966/2003-5. Research of the second author supported by FAPERJ (Brazil) under Grant No.E26/150.581/00 and by CNPq (Brazil) under Grant No. 383066/2004-2.     

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     

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.     

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.     

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     

Partial regularity for stationary harmonic maps at a free boundary

Let and be smooth Riemannian manifolds, of the dimension n≥2 with nonempty boundary, and compact without boundary. We consider stationary harmonic maps u ∈ H¹(, ) with a free boundary condition of the type u(∂) ⊂ Γ, given a submanifold Γ⊂. We prove partial boundary regularity, namely (sing(u))=0, a result that was until now only known in the interior of the domain (see [B]). The key of the proof is a new lemma that allows an extension of u by a reflection construction. Once the partial regularity theorem is known, it is possible to reduce the dimension of the singular set further under additional assumptions on the target manifold and the submanifold Γ.     

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 .     

The theory of energy for sub-Laplacians with an application to quasi-continuity

In this paper, we provide a suitable theory for the energy where μ is a Radon measure and Γ is the fundamental solution of a sub-Laplacian on a stratified group As a significant application, we prove the quasi-continuity of superharmonic functions related to . The proofs are elementary and mostly rely on the use of appropriate mean-value formulas and mean-integral operators relevant to the Potential Theory for .     

The Rees algebra of a positive normal affine semigroup ring

Let R be a positive normal affine semigroup ring of dimension d and let be the maximal homogeneous ideal of R. We show that the integral closure of is equal to for all n ∈ℕ with n ≥ d − 2. From this we derive that the Rees algebra R[t] is normal in case that d ≤ 3. If emb dim(R) = d + 1, we can give a necessary and sufficient condition for R[t] to be normal.     

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.     

Tannaka duality on quotient stacks

Let = [X/G] be the quotient stack of a scheme X by an affine group scheme G over a field k. Assume that there is a line bundle on whose underlying line bundle on X is very ample. Let VB() be the category of vector bundles on .We show that is canonically isomorphic to the stack of fiber functors on VB(). This is an analogue of the Tannaka duality for affine groups. Partially supported by CNCSIS contract no. 33079/2004     

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.     

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.     

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 .     

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 .     

On two fragments with negation and without implication of the logic of residuated lattices

The logic of (commutative integral bounded) residuated lattices is known under different names in the literature: monoidal logic [26], intuitionistic logic without contraction [1], H_BCK [36] (nowadays called by Ono), etc. In this paper we study the -fragment and the -fragment of the logical systems associated with residuated lattices, both from the perspective of Gentzen systems and from that of deductive systems. We stress that our notion of fragment considers the full consequence relation admitting hypotheses. It results that this notion of fragment is axiomatized by the rules of the sequent calculus for the connectives involved. We also prove that these deductive systems are non-protoalgebraic, while the Gentzen systems are algebraizable with equivalent algebraic semantics the varieties of pseudocomplemented (commutative integral bounded) semilatticed and latticed monoids, respectively. All the logical systems considered are decidable.     

The space of complete embedded maximal surfaces with isolated singularities in the 3-dimensional Lorentz-Minkowski space

We prove that a complete embedded maximal surface in = (³, dx₁² + dx₂²-dx₃²) with a finite number of singularities is an entire maximal graph with conelike singularities over any spacelike plane, and so, it is asymptotic to a spacelike plane or a half catenoid. We show that the moduli space of entire maximal graphs over {x₃=0} in with n+12 singular points and vertical limit normal vector at infinity is a 3n+4-dimensional differentiable manifold. The convergence in means the one of conformal structures and Weierstrass data, and it is equivalent to the uniform convergence of graphs on compact subsets of {x₃=0}. Moreover, the position of the singular points in ³ and the logarithmic growth at infinity can be used as global analytical coordinates with the same underlying topology. We also introduce the moduli space of marked graphs with n+1 singular points (a mark in a graph is an ordering of its singularities), which is a (n+1)-sheeted covering of . We prove that identifying marked graphs differing by translations, rotations about a vertical axis, homotheties or symmetries about a horizontal plane, the corresponding quotient space is an analytic manifold of dimension 3n–1. This manifold can be identified with a spinorial bundle associated to the moduli space of Weierstrass data of graphs in .Mathematics Subject Classification (2000): 53C50, 58D10, 53C42First and second authors research partially supported by MEC-FEDER grant number MTM2004-00160Second and third authors research partially supported by Consejería de Educación y Ciencia de la Junta de Andalucía and the European Union.     

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 .     

Newton methods for nonsmooth convex minimization: connections among -Lagrangian, Riemannian Newton and SQP methods

This paper studies Newton-type methods for minimization of partly smooth convex functions. Sequential Newton methods are provided using local parameterizations obtained from -Lagrangian theory and from Riemannian geometry. The Hessian based on the -Lagrangian depends on the selection of a dual parameter g; by revealing the connection to Riemannian geometry, a natural choice of g emerges for which the two Newton directions coincide. This choice of g is also shown to be related to the least-squares multiplier estimate from a sequential quadratic programming (SQP) approach, and with this multiplier, SQP gives the same search direction as the Newton methods. This paper is dedicated to R.T. Rockafellar, on the occasion of his 70th birthday.