A polyhedral study of triplet formulation for single row facility layout problem

The single row facility layout problem (SRFLP) is the problem of arranging n departments with given lengths on a straight line so as to minimize the total weighted distance between all department pairs. We present a polyhedral study of the triplet formulation of the SRFLP introduced by Amaral [A.R.S. Amaral, A new lower bound for the single row facility layout problem, Discrete Applied Mathematics 157 (1) (2009) 183-190]. For any number of departments n, we prove that the dimension of the triplet polytope is n(n−1)(n−2)/3 (this is also true for the projections of this polytope presented by Amaral). We then prove that several valid inequalities presented by Amaral for this polytope are facet-defining. These results provide theoretical support for the fact that the linear program solved over these valid inequalities gives the optimal solution for all instances studied by Amaral.     

A note on the solution of group knapsack problems

Using the Nicholson principle the algorithm of Shapiro for solving group knapsack problems is improved. An approximation method is derived and numerical results are presented. The solution of the approximation method will be characterized.     

Valid inequalities for MIPs and group polyhedra from approximate liftings

In this paper, we present an approximate lifting scheme to derive valid inequalities for general mixed integer programs and for the group problem. This scheme uses superadditive functions as the building block of integer and continuous lifting procedures. It yields a simple derivation of new and known families of cuts that correspond to extreme inequalities for group problems. This new approximate lifting approach is constructive and potentially efficient in computation. J.-P. P. Richard was supported by NSF grant DMI-348611.     

On the extreme inequalities of infinite group problems

Infinite group relaxations of integer programs (IP) were introduced by Gomory and Johnson (Math Program 3:23–85, 1972) to generate cutting planes for general IPs. These valid inequalities correspond to real-valued functions defined over an appropriate infinite group. Among all the valid inequalities of the infinite group relaxation, extreme inequalities are most important since they are the strongest cutting planes that can be obtained within the group-theoretic framework. However, very few properties of extreme inequalities of infinite group relaxations are known. In particular, it is not known if all extreme inequalities are continuous and what their relations are to extreme inequalities of finite group problems. In this paper, we describe new properties of extreme functions of infinite group problems. In particular, we study the behavior of the pointwise limit of a converging sequence of extreme functions as well as the relations between extreme functions of finite and infinite group problems. Using these results, we prove for the first time that a large class of discontinuous functions is extreme for infinite group problems. This class of extreme functions is the generalization of the functions given by Letchford and Lodi (Oper Res Lett 30(2):74–82, 2002), Dash and Günlük (Proceedings 10th conference on integer programming and combinatorial optimization. Springer, Heidelberg, pp 33–45 (2004), Math Program 106:29–53, 2006) and Richard et al. (Math Program 2008, to appear). We also present several other new classes of discontinuous extreme functions. Surprisingly, we prove that the functions defining extreme inequalities for infinite group relaxations of mixed integer programs are continuous. S.S. Dey and J.-P.P. Richard was supported by NSF Grant DMI-03-48611.     

Properties and least‐squares problems for row extended matrices

In this paper, we discuss basic properties, a least‐squares problem for row extended matrices and the associated approximation problem. First, we obtain their basic properties by applying their particular structure. Then we derive a general representation of the solutions to the least‐squares problem, and we obtain an expression for the solution to the associated approximation problem. Finally, we provide a perturbation analysis and a perturbation bound for the best approximate solution. The results are illustrated by numerical examples. Copyright © 2009 John Wiley & Sons, Ltd.     

Yetter–Drinfeld Modules over the Hopf–Ore Extension of the Group Algebra of Dihedral Group

Let k be an algebraically closed field of characteristic zero, and D _n be the dihedral group of order 2n, where n is a positive even integer. In this paper, we investigate Yetter-Drinfeld modules over the Hopf-Ore extension A(n, 0) of kD _n . We describe the structures and properties of simple Yetter-Drinfeld modules over A(n, 0), and classify all simple Yetter-Drinfeld modules over A(n, 0).     

On a family of minimal blocking sets of the Hermitian surface

An infinite family of minimal blocking sets of ??(3, q²) is constructed for even q, with links to Ceva configurations. Copyright © 2011 John Wiley & Sons, Ltd 19:313‐316, 2011.     

Green functions and related boundary value problems on the Heisenberg group

In this article, a modified Kelvin transform on ? _n using inversion with respect to a ball of arbitrary radius is defined, which gives explicit expressions for Green's function and Poisson's kernel for the Korányi ball of arbitrary radius and annular domain. The solution of the Dirichlet problem for the union of two balls is discussed using the Schwarz's alternating method.     

The rank of finitely generated modules over group algebras

We show the existence of a rank function on finitely generated modules over group algebras , where is an arbitrary field and is a finitely generated amenable group. This extends a result of W. Lück (1998).

     

The backward group preserving scheme for multi-dimensional nonhomogeneous and nonlinear backward wave problems

In this study, we utilize a backward group preserving scheme (BGPS) to cope with the nonhomogeneous as well as nonlinear backward wave problems (BWPs). Because the solution does not continuously count on the given information, the BWP is well-known to be seriously ill-posed. When six numerical instances are examined, we reveal that the BGPS is capable of tackling the nonhomogeneous and nonlinear BWPs. Besides, the BGPS is also robust enough against the perturbation even with the boisterous final data, of which the numerical results are rather accurate, effective and stable.     

Generators for decompositions of tensor products of modules associated with standard Jordan partitions

If K is a field of finite characteristic p, G is a cyclic group of order q = p^α, U and W are indecomposable KG-modules with dim U = m and dim W = n, and λ(m,n,p) is a standard Jordan partition of mn, we describe how to find a generator for each of the indecomposable components of the KG-module U ? W.     

Dual problems for weak and quasi approximation properties

It is shown that for the separable dual X^∗ of a Banach space X if X^∗ has the weak approximation property, then X has the metric quasi approximation property. Using this it is shown that for the separable dual X^∗ of a Banach space X the quasi approximation property and metric quasi approximation property are inherited from X^∗ to X and for a separable and reflexive Banach space X, X having the weak approximation property, bounded weak approximation property, quasi approximation property, metric weak approximation property, and metric quasi approximation property are equivalent. Also it is shown that the weak approximation property, bounded weak approximation property, and quasi approximation property are not inherited from a Banach space X to X^∗.     

Calculus of convex polyhedra and polyhedral convex functions by utilizing a multiple objective linear programming solver

ABSTRACT

The article deals with operations defined on convex polyhedra or polyhedral convex functions. Given two convex polyhedra, operations like Minkowski sum, intersection and closed convex hull of the union are considered. Basic operations for one convex polyhedron are, for example, the polar, the conical hull and the image under affine transformation. The concept of a P-representation of a convex polyhedron is introduced. It is shown that many polyhedral calculus operations can be expressed explicitly in terms of P-representations. We point out that all the relevant computational effort for polyhedral calculus consists in computing projections of convex polyhedra. In order to compute projections we use a recent result saying that multiple objective linear programming (MOLP) is equivalent to the polyhedral projection problem. Based on the MOLP solver bensolve a polyhedral calculus toolbox for Matlab and GNU Octave is developed. Some numerical experiments are discussed.     

First cohomology group of rank two Witt algebra to its Larsson modules

Let U = ℂ², Γ = ℤ², and let ℂ[x ₁^±1, x ₂^±1] be the ring of Laurent polynomials. The Witt algebra L is the Lie algebra of derivations over ℂ[x ₁^±1, x ₂^±1], which is spanned by elements of the form D(u, r) = x ^r (u ₁ d ₁ + u ₂ d ₂), u = (u ₁, u ₂) ∈ U, r ∈ Γ, where d ₁ and d ₂ are the degree derivations of ℂ[x ₁^±1, x ₂^±1]. The image of gl ₂-module V under Larsson functor F ^α , denoted by W = F ^α (V), gives a class of L-modules, often called the Larsson-modules of L. In this paper, we study the derivations from the Witt algebra L to its Larsson-modules W, and we determine the first cohomology group H ¹(L,W).     

Matrix problems and stable homotopy types of polyhedra

This is a survey of the results on stable homotopy types of polyhedra of small dimensions, mainly obtained by H.-J. Baues and the author [3, 5, 6]. The proofs are based on the technique of matrix problems (bimodule categories). Dedicated to C. M. Ringel.     

Dual of bass numbers and dualizing modules

Let R be a Noetherian ring and let C be a semidualizing R-module. In this paper, we impose various conditions on C to be dualizing. For example, as a generalization of Xu [21 Xu, J. (1995). Minimal injective and flat resolutions of modules over Gorenstein rings. J. Algebra 175:451–477.[Crossref], [Web of Science ®] , [Google Scholar], Theorem 3.2], we show that C is dualizing if and only if for an R-module M, the necessary and su?cient condition for M to be C-injective is that π_i(𝔭,M) = 0 for all 𝔭∈Spec (R) and all i≠ht (𝔭), where π_i is the invariant dual to the Bass numbers defined by Enochs and Xu [8 Enochs, E., Xu, J. (1997). On invariants dual to the Bass numbers. Proc. Am. Math. Soc. 125:951–960.[Crossref], [Web of Science ®] , [Google Scholar]].     

Some programming problems for teaching foundations of group theory

This paper contains some programming problems which can be suggested for students starting to learn group theory. These problems are related to important notations such as subgroup, coset, normal divisor, symmetric group, normalizer, centralizer, homomorphism and automorphism. Carefully selected problems provide a successful understanding of the basic themes of finite group theory.     

The classification of 2 and 3 torsion free polyhedra

We classify the stable homotopy types of(n-1)-connected,(n + k)-dimensional polyhedra with 2 and 3-torsion free homologies for k ≤ 6. The technique used is matrix problem(bimodule categories) which is given by Drozd.