E -Theoretic Duality for Higher Rank Graph Algebras

We prove that there is a Poincaré type duality in E-theory between higher rank graph algebras associated with a higher rank graph and its opposite correspondent. We obtain an r-duality, that is the fundamental classes are in E^r. The basic tools are a higher rank Fock space and higher rank Toeplitz algebra which has a more interesting ideal structure than in the rank 1 case. The K-homology fundamental class is given by an r-fold exact sequence whereas the K-theory fundamental class is given by a homomorphism. The E-theoretic products are essentially pull-backs so that the computation is done at the level of exact sequences. Mathematics Subject Classification (2000): 46L80.     

一类多目标分式规划的二阶对称对偶问题

研究一类多目标分式规划的二阶对称对偶问题.在二阶F-凸性假设下给出了对偶问题的弱对偶、强对偶和逆对偶定理.并在对称和反对称假设下研究了该问题的自身对偶性.     

Comparison of bundle and classical column generation

When a column generation approach is applied to decomposable mixed integer programming problems, it is standard to formulate and solve the master problem as a linear program. Seen in the dual space, this results in the algorithm known in the nonlinear programming community as the cutting-plane algorithm of Kelley and Cheney-Goldstein. However, more stable methods with better theoretical convergence rates are known and have been used as alternatives to this standard. One of them is the bundle method; our aim is to illustrate its differences with Kelley’s method. In the process we review alternative stabilization techniques used in column generation, comparing them from both primal and dual points of view. Numerical comparisons are presented for five applications: cutting stock (which includes bin packing), vertex coloring, capacitated vehicle routing, multi-item lot sizing, and traveling salesman. We also give a sketchy comparison with the volume algorithm. This research has been supported by Inria New Investigation Grant “Convex Optimization and Dantzig-Wolfe Decomposition”.     

Derivation modules of orthogonal duals of hyperplane arrangements

Let A be an n × d matrix having full rank n. An orthogonal dual A^⊥ of A is a (d-n) × d matrix of rank (d−n) such that every row of A^⊥ is orthogonal (under the usual dot product) to every row of A. We define the orthogonal dual for arrangements by identifying an essential (central) arrangement of d hyperplanes in n-dimensional space with the n × d matrix of coefficients of the homogeneous linear forms for which the hyperplanes are kernels. When n ≥ 5, we show that if the matroid (or the lattice of intersection) of an n-dimensional essential arrangement contains a modular copoint whose complement spans, then the derivation module of the orthogonally dual arrangement ^⊥ has projective dimension at least ⌈ n(n+2)/4 ⌉ - 3.Hal Schenck partially supported by NSF DMS 03-11142, NSA MDA 904-03-1-0006, and ATP 010366-0103.     

Viscosity approximation methods for nonexpansive nonself-mappings

Let E a real reflexive Banach space which admits a weakly sequentially continuous duality mapping from E to E^∗, and K be a closed convex subset of E which is also a sunny nonexpansive retract of E, and be nonexpansive mappings satisfying the weakly inward condition and F(T)≠∅, and be a fixed contractive mapping. The implicit iterative sequence {xt} is defined by for t∈(0,1)

xt=P(tf(xt)+(1−t)Txt).     

Alternating sign matrices with one −1 under vertical reflection

We define a bijection that transforms an alternating sign matrix A with one −1 into a pair (N,E) where N is a (so called) neutral alternating sign matrix (with one −1) and E is an integer. The bijection preserves the classical parameters of Mills, Robbins and Rumsey as well as three new parameters (including E). It translates vertical reflection of A into vertical reflection of N. A hidden symmetry allows the interchange of E with one of the remaining two new parameters. A second bijection transforms (N,E) into a configuration of lattice paths called “mixed configuration.”     

Note on: N.E. Aguilera, M.S. Escalante, G.L. Nasini, “The disjunctive procedure and blocker duality”

Aguilera et al. [Discrete Appl. Math. 121 (2002) 1–13] give a generalization of a theorem of Lehman through an extension of the disjunctive procedure defined by Balas, Ceria and Cornuéjols. This generalization can be formulated as(A) For every clutter , the disjunctive index of its set covering polyhedron coincides with the disjunctive index of the set covering polyhedron of its blocker, .In Aguilera et al. [Discrete Appl. Math. 121 (2002) 1–3], (A) is indeed a corollary of the stronger result(B) .Motivated by the work of Gerards et al. [Math. Oper. Res. 28 (2003) 884–885] we propose a simpler proof of (B) as well as an alternative proof of (A), independent of (B). Both of them are based on the relationship between the “disjunctive relaxations” obtained by and the set covering polyhedra associated with some particular minors of .     

Existence of optimal solutions and duality results under weak conditions

In this paper we consider an ordinary convex program with no qualification conditions (such as Slater’s condition) and for which the optimal set is neither required to be compact, nor to be equal to the sum of a compact set and a linear space. It is supposed only that the infimum α is finite. A very wide class of convex functions is exhibited for which the optimum is always attained and α is equal to the supremum of the ordinary dual program. Additional results concerning the existence of optimal solutions in the non convex case are also given. Received: February 1, 1999 / Accepted: December 15, 1999?Published online February 23, 2000     

Asymptotic Behavior of Loss Probability in GI/M/1/K Queue as K Tends to Infinity

We obtain an asymptotic behavior of the loss probability for the GI/M/1/K queue as K for cases of <1, >1 and =1.     

Topological regular variation: I. Slow variation

Motivated by the Category Embedding Theorem, as applied to convergent automorphisms (Bingham and Ostaszewski (in press) [11]), we unify and extend the multivariate regular variation literature by a reformulation in the language of topological dynamics. Here the natural setting are metric groups, seen as normed groups (mimicking normed vector spaces). We briefly study their properties as a preliminary to establishing that the Uniform Convergence Theorem (UCT) for Baire, group-valued slowly-varying functions has two natural metric generalizations linked by the natural duality between a homogenous space and its group of homeomorphisms. Each is derivable from the other by duality. One of these explicitly extends the (topological) group version of UCT due to Bajšanski and Karamata (1969) [4] from groups to flows on a group. A multiplicative representation of the flow derived in Ostaszewski (2010) [45] demonstrates equivalence of the flow with the earlier group formulation. In companion papers we extend the theory to regularly varying functions: we establish the calculus of regular variation in Bingham and Ostaszewski (2010) [13] and we extend to locally compact, σ-compact groups the fundamental theorems on characterization and representation (Bingham and Ostaszewski (2010) [14]). In Bingham and Ostaszewski (2009) [15], working with topological flows on homogeneous spaces, we identify an index of regular variation, which in a normed-vector space context may be specified using the Riesz representation theorem, and in a locally compact group setting may be connected with Haar measure.