Stack-up algorithms for palletizing at delivery industry

We study the following multi-objective combinatorial stack-up problem from delivery industry. Given a sequence q of labeled bins and two positive integers s and p. The aim is to stack-up the bins by iteratively removing one of the first s bins of the sequence and put it to one of p stack-up places. Each of these places has to contain bins of only one label, bins of different labels have to be placed on different places. If all bins of a label are removed from q, the corresponding place becomes available for bins of another label. We analyze the worst-case performance of simple algorithms for the stack-up problem that are very interesting from a practical point of view. In particular, we show that the so-called Most-Frequently on-line algorithm is (2,2)-competitive and has optimal worst-case on-line performance.     

Multicriteria movement synchronization scheduling problems and algorithms

This article deals with multicriteria optimization models and algorithms of movement scheduling for many objects to synchronize their movement (2CMSS problem). The model consists of two parts: (1) node–disjoint path planning visiting specified nodes for K objects with a given vector of intermediate nodes for each one (NDSP problem); (2) movement synchronization in some intermediate nodes (MS problem). For synchronous movement, two categories of criteria are defined: time of movement and ‘distance’ of K-moved objects from the movement pattern. We defined the problem as a discrete-continuous, non-linear, two-criteria mathematical programming problem. We proposed to use a two-stage algorithm to solve the 2CMSS problem (as lexicographic solution): At first we have to find the vector of node–disjoint shortest paths for K objects visiting intermediate nodes to set optimal paths under the assumption that we use maximal possible velocities on each arc belonging to a path for each object (solution of the NDSP problem), and next we try to decrease the values of velocities to optimize the second criterion (synchronization, solution of the MS problem). Experimental analyses of effectiveness and complexity of the algorithms are presented.     

Characteristic fixed‐point sets of semifree actions on spheres

A group action is semifree if it is free away from its fixed‐point set. P. A. Smith showed that when a finite group of order q acts semifreely on a sphere, the fixed set is a mod q homology sphere. Conversely, given a mod q homology sphere as a subset of a sphere, one may try to construct a group action on the sphere fixing the subset. The converse question was first systematically studied by Jones and then by many others. In this note, we give new numerical congruences satisfied by the homology of the fixed sets and give a definitive solution to the problem for characteristic fixed‐point sets. © 1999 John Wiley & Sons, Inc.     

Polynomial-time approximation schemes for packing and piercing fat objects

We consider two problems: given a collection of n fat objects in a fixed dimension, (1) ( packing) find the maximum subcollection of pairwise disjoint objects, and (2) ( piercing) find the minimum point set that intersects every object. Recently, Erlebach, Jansen, and Seidel gave a polynomial-time approximation scheme (PTAS) for the packing problem, based on a shifted hierarchical subdivision method. Using shifted quadtrees, we describe a similar algorithm for packing but with a smaller time bound. Erlebach et al.'s algorithm requires polynomial space. We describe a different algorithm, based on geometric separators, that requires only linear space. This algorithm can also be applied to piercing, yielding the first PTAS for that problem.     

On Abelian Branched Coverings of the Sphere

 We obtain an enumeration formula for the number of weak equivalence classes of the branched (?×ℬ)-covering of the sphere with m-branch points, when ? and ℬ are finite abelian groups with (|?|,|ℬ|)=1. From this, we can deduce an explicit formula for enumerating the weak equivalence classes of pseudofree spherical (ℤ _p ×ℤ _q )-actions on a given surface, when p and q are distinct primes. Received: August 10, 1999 Final version received: June 19, 2000     

On relations for the multiple <Emphasis Type="Italic">q</Emphasis>-zeta values

We prove a new relation for the multiple q-zeta values (MqZV’s). It is a q-analogue of the Ohno-Zagier relation for the multiple zeta values (MZV’s). We discuss the problem of determining the dimension of the space spanned by MqZV’s over ℚ, and present an application to MZV. The first author is supported by Grant-in-Aid for Young Scientists (B) No. 17740026 and the second author is supported by Grant-in-Aid for Young Scientists (B) No. 17740089.     

Some combinatorial interpretations ofq-analogs of Schröder numbers

We introduce two definitions of Schröder numberq-analogs and show some combinatorial interpretations of theseq-numbers. We use the following combinatorial objects for these interpretations: Schröder paths, 1-colored parallelogram polyominoes and permutations with forbidden subsequences (4231, 4132). We enumerate these objects according to various parameters by means of a recentq-counting technique. We prove that the firstq-Schröder number enumerates of Schröder paths with respect to area and the number of permutation inversions, while the second one counts the 1-colored parallelogram polyominoes according to their width and area. Finally, we illustrate some relations among the parameters characterizing the combinatorial objects.     

The number of faces of the tridiagonal Birkhoff polytope

Counting basic objects as the vertices of polyhedra is a demanding problem in general, even for the most basic structured polytope. In this paper, we determine the number of q-faces for some q ≥ 1 of the polytope of tridiagonal doubly stochastic matrices.     

Cohomology and extension problems for semi <Emphasis Type="Italic">q</Emphasis>-coronae

We prove some extension theorems for analytic objects, in particular sections of a coherent sheaf, defined in semi q-coronae of a complex space. Semi q-coronae are domains whose boundary is the union of a Levi flat part, a q-pseudoconvex part and a q-pseudoconcave part. Such results are obtained mainly using cohomological techniques.     

Abelian group pairs having a trivial coGalois group

Torsion-free covers are considered for objects in the category q ₂. Objects in the category q ₂ are just maps in R-Mod. For R = ℤ, we find necessary and sufficient conditions for the coGalois group G(A → B), associated to a torsion-free cover, to be trivial for an object A → B in q ₂. Our results generalize those of E. Enochs and J. Rado for abelian groups.     

On the complexity of the multivariate Sturm–Liouville eigenvalue problem

We study the complexity of approximating the smallest eigenvalue of -Δ+q with Dirichlet boundary conditions on the d-dimensional unit cube. Here Δ is the Laplacian, and the function q is non-negative and has continuous first order partial derivatives. We consider deterministic and randomized classical algorithms, as well as quantum algorithms using quantum queries of two types: bit queries and power queries. We seek algorithms that solve the problem with accuracy . We exhibit lower and upper bounds for the problem complexity. The upper bounds follow from the cost of particular algorithms. The classical deterministic algorithm is optimal. Optimality is understood modulo constant factors that depend on d. The randomized algorithm uses an optimal number of function evaluations of q when d≤2. The classical algorithms have cost exponential in d since they need to solve an eigenvalue problem involving a matrix with size exponential in d. We show that the cost of quantum algorithms is not exponential in d, regardless of the type of queries they use. Power queries enjoy a clear advantage over bit queries and lead to an optimal complexity algorithm.     

A Mathematica package for q-holonomic sequences and power series

We describe a Mathematica package for dealing with q-holonomic sequences and power series. The package is intended as a q-analogue of the Maple package gfun and the Mathematica package GeneratingFunctions. It provides commands for addition, multiplication, and substitution of these objects, for converting between various representations (q-differential equations, q-recurrence equations, q-shift equations), for computing sequence terms and power series coefficients, and for guessing recurrence equations given initial terms of a sequence. C. Koutschan partially supported by the Austrian Science Foundation (FWF) grants SFB F1305.     

A simple proof of a primal affine scaling method

In this paper, we present a simpler proof of the result of Tsuchiya and Muramatsu on the convergence of the primal affine scaling method. We show that the primal sequence generated by the method converges to the interior of the optimum face and the dual sequence to the analytic center of the optimal dual face, when the step size implemented in the procedure is bounded by 2/3. We also prove the optimality of the limit of the primal sequence for a slightly larger step size of 2q/(3q–1), whereq is the number of zero variables in the limit. We show this by proving the dual feasibility of a cluster point of the dual sequence.Partially supported by the grant CCR-9321550 from NSF.     

On Local Integrability Conditions of Jet Groupoids

A jet groupoid ℛ _q over a manifold X is a special Lie groupoid consisting of q-jets of local diffeomorphisms X→X. As a subbundle of J ^q (X,X), a jet groupoid can be considered as a system of nonlinear partial differential equations (PDE). This leads to the question if ℛ _q is formally integrable. On the other hand, each jet groupoid is the symmetry groupoid of a geometric object, which is a section ω of a natural bundle ℱ. Using the jet groupoids, we give a local characterisation of formal integrability for transitive jet groupoids in terms of their corresponding geometric objects. Thanks to M. Barakat and W. Plesken for discussions. The author was supported by DFG Grant Graduiertenkolleg 775.     

Frustrated Magnetic Systems and the q-Oscillator

We analyze the spherical model with frustration induced by an external gauge field. The case of the infinite-dimensional model has recently been reduced to a problem of q-deformed oscillators with q parametrizing the amount of frustration. We find a complete analytic solution of the model by using a convenient representation of the q-oscillator algebra, the q-Hermite polynomials. The low-temperature phase does not exhibit a glassy behavior. With respect to the usual unfrustrated spherical model, the effect of frustration is only quantitative. A glassy low-temperature phase is expected for the more complicated XY model whose study is in progress. Bibliography: 15 titles.     

A characterization of quadrics by intersection numbers

This work is inspired by a paper of Hertel and Pott on maximum non-linear functions (Hertel and Pott, A characterization of a class of maximum non-linear functions. Preprint, 2006). Geometrically, these functions correspond with quasi-quadrics; objects introduced in De Clerck et al. (Australas J Combin 22:151–166, 2000). Hertel and Pott obtain a characterization of some binary quasi-quadrics in affine spaces by their intersection numbers with hyperplanes and spaces of codimension 2. We obtain a similar characterization for quadrics in projective spaces by intersection numbers with low-dimensional spaces. Ferri and Tallini (Rend Mat Appl 11(1): 15–21, 1991) characterized the non-singular quadric Q(4,q) by its intersection numbers with planes and solids. We prove a corollary of this theorem for Q(4,q) and then extend this corollary to all quadrics in PG(n,q),n ≥ 4. The only exceptions occur for q even, where we can have an oval or an ovoid as intersection with our point set in the non-singular part.      

The Dolbeault complex in infinite dimensions III. Sheaf cohomology in Banach spaces

We prove that the sheaf cohomology groups H ^q (Ω,?) vanish if Ω is a pseudoconvex open subset of a Banach space with unconditional basis, and q≥1. Oblatum 23-XII-1999 & 12-V-2000?Published online: 16 August 2000     

Existence of (q,k, 1) difference families with q a prime power and k = 4, 5

The existence of a (q, k, 1) difference family in GF(q) has been completely solved for k = 3. For k = 4, 5 partial results have been given by Bose, Wilson, and Buratti. In this article, we continue the investigation and show that the necessary condition for the existence of a (q, k, 1) difference family in GF(q), i.e., q ≡ 1 (mod k(k − 1)) is also sufficient for k = 4, 5. For general k, Wilson's bound shows that a (q, k, 1) difference family in GF(q) exists whenever q ≡ 1 (mod k(k − 1)) and q > [k(k − 1)/2]^k(k−1). An improved bound on q is also presented. © 1999 John Wiley & Sons, Inc. J Combin Designs 7: 21–30, 1999