Maximum stable set formulations and heuristics based on continuous optimization

 The stability number α(G) for a given graph G is the size of a maximum stable set in G. The Lovász theta number provides an upper bound on α(G) and can be computed in polynomial time as the optimal value of the Lovász semidefinite program. In this paper, we show that restricting the matrix variable in the Lovász semidefinite program to be rank-one and rank-two, respectively, yields a pair of continuous, nonlinear optimization problems each having the global optimal value α(G). We propose heuristics for obtaining large stable sets in G based on these new formulations and present computational results indicating the effectiveness of the heuristics. Received: December 13, 2000 / Accepted: September 3, 2002 Published online: December 19, 2002 RID="★" ID="★" Computational results reported in this paper were obtained on an SGI Origin2000 computer at Rice University acquired in part with support from NSF Grant DMS-9872009. Key Words. maximum stable set – maximum clique – minimum vertex cover – semidefinite program – semidefinite relaxation – continuous optimization heuristics – nonlinear programming Mathematics Subject Classification (2000): 90C06, 90C27, 90C30     

Recent advances in the solution of quadratic assignment problems

 The quadratic assignment problem (QAP) is notoriously difficult for exact solution methods. In the past few years a number of long-open QAPs, including those posed by Steinberg (1961), Nugent et al. (1968) and Krarup (1972) were solved to optimality for the first time. The solution of these problems has utilized both new algorithms and novel computing structures. We describe these developments, as well as recent work which is likely to result in the solution of even more difficult instances. Received: February 13, 2003 / Accepted: April 22, 2003 Published online: May 28, 2003 Key Words. quadratic assignment problem – discrete optimization – branch and bound Mathematics Subject Classification (1991): 90C27, 90C09, 90C20     

Local behavior of an iterative framework for generalized equations with nonisolated solutions

 An iterative framework for solving generalized equations with nonisolated solutions is presented. For generalized equations with the structure , where is a multifunction and F is single-valued, the framework covers methods that, at each step, solve subproblems of the type . The multifunction approximates F around s. Besides a condition on the quality of this approximation, two other basic assumptions are employed to show Q-superlinear or Q-quadratic convergence of the iterates to a solution. A key assumption is the upper Lipschitz-continuity of the solution set map of the perturbed generalized equation . Moreover, the solvability of the subproblems is required. Conditions that ensure these assumptions are discussed in general and by means of several applications. They include monotone mixed complementarity problems, Karush-Kuhn-Tucker systems arising from nonlinear programs, and nonlinear equations. Particular results deal with error bounds and upper Lipschitz-continuity properties for these problems. Received: November 2001 / Accepted: November 2002 Published online: December 9, 2002 Key Words. generalized equation – nonisolated solutions – Newton's method – superlinear convergence – upper Lipschitz-continuity – mixed complementarity problem – error bounds Mathematics Subject Classification (1991): 90C30, 65K05, 90C31, 90C33     

Smoothed analysis of termination of linear programming algorithms

 We perform a smoothed analysis of a termination phase for linear programming algorithms. By combining this analysis with the smoothed analysis of Renegar's condition number by Dunagan, Spielman and Teng (http://arxiv.org/abs/cs.DS/0302011) we show that the smoothed complexity of interior-point algorithms for linear programming is O(m ³ log(m/Σ)). In contrast, the best known bound on the worst-case complexity of linear programming is O(m ³ L), where L could be as large as m. We include an introduction to smoothed analysis and a tutorial on proof techniques that have been useful in smoothed analyses. Received: December 10, 2002 / Accepted: April 28, 2003 Published online: June 5, 2003 Key words. smoothed analysis – linear programming – interior-point algorithms – condition numbers Mathematics Subject Classification (1991): 90C05, 90C51, 68Q25     

An ordinal analysis of stability

This paper is the first in a series of three which culminates in an ordinal analysis of ¹₂-comprehension. On the set-theoretic side ¹₂-comprehension corresponds to Kripke-Platek set theory, KP, plus ₁-separation. The strength of the latter theory is encapsulated in the fact that it proves the existence of ordinals such that, for all >, is -stable, i.e. L is a ₁-elementary substructure of L. The objective of this paper is to give an ordinal analysis of a scenario of not too complicated stability relations as experience has shown that the understanding of the ordinal analysis of ¹₂-comprehension is greatly facilitated by explicating certain simpler cases first.This paper introduces an ordinal representation system based on -indescribable cardinals which is then employed for determining an upper bound for the proof–theoretic strength of the theory KPi+ is +-stable, where KPi is KP augmented by the axiom saying that every set is contained in an admissible set.The results in this paper were obtained in 1995 when the author was a Heisenberg Fellow of the German Science Foundation, Deutsche Forschungsgemeinschaft.     

Weak Tensor Category and Related Generalized Hopf Algebras

There are at least two kinds of generalization of Hopf algebra, i.e. pre-Hopf algebra and weak Hopf algebra. Correspondingly, we have two kinds of generalized bialgebras, almost bialgebra and weak bialgebra. Let L = （L, ×, I, a, l, r） be a tensor category. By giving up I, l, r and keeping ×, a in L, the first author got so-called pre-tensor category L = （L, ×, a） and used it to characterize almost bialgebra and pre-Hopf algebra in Comm. in Algebra, 32（2）： 397-441 （2004）. Our aim in this paper is to generalize tensor category L = （L, ×, I, a, l, r） by weakening the natural isomorphisms l, r, i.e. exchanging the natural isomorphism ll^-1 = rr^-1 = id into regular natural transformations lll= l, rrr = r with some other conditions and get so-called weak tensor category so as to characterize weak bialgebra and weak Hopf algebra. The relations between these generalized （bialgebras） Hopf algebras and two kinds generalized tensor categories will be described by using of diagrams. Moreover, some related concepts and properties about weak tensor category will be discussed.     

A graphical approach to computing Selmer groups of congruent number curves

Let E _n:y ²=x ³−n ² x denote the family of congruent number elliptic curves. Feng and Xiong (2004) equate the nontriviality of the Selmer groups associated with E _n to the presence of certain types of partitions of graphs associated with the prime factorization of n. In this paper, we extend the ideas of Feng and Xiong in order to compute the Selmer groups of E _n. 2000 Mathematics Subject Classification Primary—11G05; Secondary—14H52, 14H25, 05C90     

Avoiding numerical cancellation in the interior point method for solving semidefinite programs

 The matrix variables in a primal-dual pair of semidefinite programs are getting increasingly ill-conditioned as they approach a complementary solution. Multiplying the primal matrix variable with a vector from the eigenspace of the non-basic part will therefore result in heavy numerical cancellation. This effect is amplified by the scaling operation in interior point methods. A complete example illustrates these numerical issues. In order to avoid numerical problems in interior point methods, we propose to maintain the matrix variables in a Cholesky form. We discuss how the factors of the v-space Cholesky form can be updated after a main iteration of the interior point method with Nesterov-Todd scaling. An analogue for second order cone programming is also developed. Numerical results demonstrate the success of this approach. Received: June 16, 2001 / Accepted: April 5, 2002 Published online: October 9, 2002 Key Words. semidefinite programming – second order cone programming Mathematics Subject Classification (2000): 90C22, 90C20     

Decomposition of test sets in stochastic integer programming

 We study Graver test sets for linear two-stage stochastic integer programs and show that test sets can be decomposed into finitely many building blocks whose number is independent on the number of scenarios of the stochastic program. We present a finite algorithm to compute the building blocks directly, without prior knowledge of test set vectors. Once computed, building blocks can be employed to solve the stochastic program by a simple augmentation scheme, again without explicit knowledge of test set vectors. Finally, we report preliminary computational experience. Received: March 14, 2002 / Accepted: March 27, 2002 Published online: September 27, 2002 Key words. test sets – stochastic integer programming – decomposition methods Mathematics Subject Classification (2000): 90C15, 90C10, 13P10     

Dynamic allocation indices for restless projects and queueing admission control: a polyhedral approach

 This paper develops a polyhedral approach to the design, analysis, and computation of dynamic allocation indices for scheduling binary-action (engage/rest) Markovian stochastic projects which can change state when rested (restless bandits (RBs)), based on partial conservation laws (PCLs). This extends previous work by the author [J. Ni?o-Mora (2001): Restless bandits, partial conservation laws and indexability. Adv. Appl. Probab. 33, 76–98], where PCLs were shown to imply the optimality of index policies with a postulated structure in stochastic scheduling problems, under admissible linear objectives, and they were deployed to obtain simple sufficient conditions for the existence of Whittle's (1988) RB index (indexability), along with an adaptive-greedy index algorithm. The new contributions include: (i) we develop the polyhedral foundation of the PCL framework, based on the structural and algorithmic properties of a new polytope associated with an accessible set system -extended polymatroid}); (ii) we present new dynamic allocation indices for RBs, motivated by an admission control model, which extend Whittle's and have a significantly increased scope; (iii) we deploy PCLs to obtain both sufficient conditions for the existence of the new indices (PCL-indexability), and a new adaptive-greedy index algorithm; (iv) we interpret PCL-indexability as a form of the classic economics law of diminishing marginal returns, and characterize the index as an optimal marginal cost rate; we further solve a related optimal constrained control problem; (v) we carry out a PCL-indexability analysis of the motivating admission control model, under time-discounted and long-run average criteria; this gives, under mild conditions, a new index characterization of optimal threshold policies; and (vi) we apply the latter to present new heuristic index policies for two hard queueing control problems: admission control and routing to parallel queues; and scheduling a multiclass make-to-stock queue with lost sales, both under state-dependent holding cost rates and birth-death dynamics. Received: April 2000 / Accepted: October 2002 Published online: December 9, 2002 RID="★" ID="★" Work partly supported by the Spanish Ministry of Science and Technology (grant BEC2000-1027), NATO (Collaborative Linkage Grant PST.CLG.976568), and the Joint Spanish-US (Fulbright) Commission for Scientific and Technical Exchange (project 2000-20132) Key words. Markov decision process – restless bandits – polyhedral combinatorics – extended polymatroid – adaptive-greedy algorithm – dynamic allocation index – stochastic scheduling – threshold policy – index policy – Gittins index – Klimov index – Whittle index – control of queues – admission control – routing – make-to-stock – multiclass queue – finite buffers – conservation laws – achievable performance Mathematics Subject Classification (1991): (AMS 2000 Subject Classification): 90B36, 90B22, 90C40, 90C57, 90C08     

Estimation of Weak Lensing Parameters by Stochastic Integration

Abstract

A procedure for computing distance–redshift statistics in inhomogeneous universes is described. We interpret the generalized Dyer–Roeder equation [Dyer, C. C.; Roeder, R. C. The distance-redshift relation for universes with no intergalactic medium. Astrophys. J. 1972, 174, L115–L117; Dyer, C. C.; Roeder, R. C. Distance-redshift relations for universes with some intergalactic medium. Astrophys. J. 1972, 180, L31–L34] as a stochastic differential equation which treats the shearing forces as Brownian movement and yields a Monte-Carlo procedure. Shear distributions taken from N-body simulations produce a redshift dependent diffusion coefficient.     

Intégration Symplectique des Variétés de Poisson Régulières

Asymplectic integration of a Poisson manifold (M, Λ) is a symplectic groupoid (Γ,η) whichrealizes the given Poisson manifold, i.e. such that the space of units Γ₀ with the induced Poisson structure Λ₀ is isomorphic to (M, Λ). This notion was introduced by A. Weinstein in [28] in order to quantize Poisson manifolds by quantizing their symplectic integration. Any Poisson manifold can be integrated by alocal symplectic groupoid ([4], [13]) but already for regular Poisson manifolds there are obstructions to global integrability ([2], [6], [11], [17], [28]). The aim of this paper is to summarize all the known obstructions and present a sufficient topological condition for integrability of regular Poisson manifolds; we will indeed describe a concrete procedure for this integration. Further our criterion will provide necessary and sufficient if we require Γ to be Hausdorff, which is a suitable condition to proceed to Weinstein’s program of quantization. These integrability results may be interpreted as a generalization of the Cartan-Smith proof of Lie’s third theorem in the infinite dimensional case.

---

---

Recherche supportée par D.G.I.C.Y.T. Espagne (Proyecto PB90-0765) et Xunta de Galicia (Proxecto XUGA20704B90)     

Cohomologically trivial internal categories in categories of groups with operations

We describe cohomologically trivial internal categories in the categoryC of groups with operations satisfying certain conditions ([15], [16]). As particular cases we obtain: ifC=Gr, H⁰(C, –)=0 iff C is a connected internal category; ifC=Ab,H ¹(C, –)=0 iff C is equivalent to the discrete internal category (Cokerd, Cokerd, 1, 1, 1, 1). We also discuss related questions concerning extensions, internal categories, their cohomology and equivalence in the categoryC.     

Inequalities for <Emphasis Type="Bold">cd</Emphasis>-Indices of Joins and Products of Polytopes

The cd-index is a polynomial which encodes the flag f-vector of a convex polytope. For polytopes U and V, we determine explicit recurrences for computing the cd-index of the free join and the cd-index of the Cartesian product U x V. As an application of these recurrences, we prove the inequality involving the cd-indices of three polytopes.     

Algebraic characterization of isometries of the complex and the quaternionic hyperbolic planes

Let H²_{\mathbb F}{{\bf H}^{\bf 2}_{\mathbb F}} denote the two dimensional hyperbolic space over \mathbb F{\mathbb F} , where \mathbb F{\mathbb F} is either the complex numbers \mathbb C{\mathbb C} or the quaternions \mathbb H{\mathbb H} . It is of interest to characterize algebraically the dynamical types of isometries of H²_{\mathbb F}{{\bf H}^{\bf 2}_{\mathbb F}} . For \mathbb F=\mathbb C{\mathbb F=\mathbb C} , such a characterization is known from the work of Giraud–Goldman. In this paper, we offer an algebraic characterization of isometries of H²_{\mathbb H}{{\bf H}^{\bf 2}_{\mathbb H}} . Our result restricts to the case \mathbb F=\mathbb C{\mathbb F=\mathbb C} and provides another characterization of the isometries of H²_{\mathbb C}{{\bf H}^{\bf 2}_{\mathbb C}} , which is different from the characterization due to Giraud–Goldman. Two elements in a group G are said to be in the same z-class if their centralizers are conjugate in G. The z-classes provide a finite partition of the isometry group. In this paper, we describe the centralizers of isometries of H²_{\mathbb F}{{\bf H}^{\bf 2}_{\mathbb F}} and determine the z-classes.     

Convex approximations for complete integer recourse models

We consider convex approximations of the expected value function of a two-stage integer recourse problem. The convex approximations are obtained by perturbing the distribution of the random right-hand side vector. It is shown that the approximation is optimal for the class of problems with totally unimodular recourse matrices. For problems not in this class, the result is a convex lower bound that is strictly better than the one obtained from the LP relaxation.This research has been made possible by a fellowship of the Royal Netherlands Academy of Arts and Sciences.Key words.integer recourse – convex approximationMathematics Subject Classification (1991):90C15, 90C11     

First- and second-order methods for semidefinite programming

 In this paper, we survey the most recent methods that have been developed for the solution of semidefinite programs. We first concentrate on the methods that have been primarily motivated by the interior point (IP) algorithms for linear programming, putting special emphasis in the class of primal-dual path-following algorithms. We also survey methods that have been developed for solving large-scale SDP problems. These include first-order nonlinear programming (NLP) methods and more specialized path-following IP methods which use the (preconditioned) conjugate gradient or residual scheme to compute the Newton direction and the notion of matrix completion to exploit data sparsity. Received: December 16, 2002 / Accepted: May 5, 2003 Published online: May 28, 2003 Key words. semidefinite programming – interior-point methods – polynomial complexity – path-following methods – primal-dual methods – nonlinear programming – Newton method – first-order methods – bundle method – matrix completion The author's research presented in this survey article has been supported in part by NSF through grants INT-9600343, INT-9910084, CCR-9700448, CCR-9902010, CCR-0203113 and ONR through grants N00014-93-1-0234, N00014-94-1-0340 and N00014-03-1-0401. Mathematics Subject Classification (2000): 65K05, 90C06, 90C22, 90C25, 90C30, 90C51     

Quotients of the congruence kernels of SL2 over arithmetic dedekind domains

LetC=C(C, P, k) be the coordinate ring of the affine curve obtained by removing a closed pointP from a (suitable) projective curveC over afinite fieldk. Let SL₂ (C,q) be the principal congruence subgroup of SL₂(C) andU ₂(C,q) be the subgroup generated by the all unipotent matrices in SL₂(C,q), whereq is aC-ideal. In this paper we prove that, for all but finitely manyq, the quotient SL₂(C,q)/U ₂(C,q) is a free group of finite,unbounded rank. LetC(SL₂(A)) be the congruence kernel of SL₂(A), whereA is an arithmetic Dedekind domain with only finitely many units. (e.g.A=C or ℤ) and letG be any finitely generated group. From the above (and previous results) we deduce that the profinite completion ofG,Ĝ, is a homonorphic image ofC(SL₂(A)). This is related to previous results of Lubotzky and Mel'nikov.     

Gelfand–Kirillov Dimension for Automorphism Groups of Relatively Free Algebras

Using ideas of our recent work on automorphisms of residually nilpotent relatively free groups, we introduce a new growth function for subgroups of the automorphism groups of relatively free algebras Fⁿ(V) over a field of characteristic zero and the related notion of Gelfand-Kirillov dimension, and study their behavior. We prove that, under some natural restrictions, the Gelfand-Kirillov dimension of the group of tame automorphisms of Fⁿ(V) is equal to the Gelfand-Kirillov dimension of the algebra Fⁿ(V). We show that, in some cases, the Gelfand-Kirillov dimension of the group of tame automorphisms of Fⁿ(V) is smaller than the Gelfand-Kirillov dimension of the whole automorphism group, and calculate the Gelfand-Kirillov dimension of the automorphism group of Fⁿ(V) for some important varieties V.Partially supported by Grant MM605/96 of the Bulgarian Foundation for Scientific Research.2000 Mathematics Subject Classification: primary 16R10, 16P90; secondary 16W20, 17B01, 17B30, 17B40