On the inapproximability of <Emphasis Type="Italic">M</Emphasis>/<Emphasis Type="Italic">G</Emphasis>/<Emphasis Type="Italic">K</Emphasis>: why two moments of job size distribution are not enough

The M/G/K queueing system is one of the oldest models for multiserver systems and has been the topic of performance papers for almost half a century. However, even now, only coarse approximations exist for its mean waiting time. All the closed-form (nonnumerical) approximations in the literature are based on (at most) the first two moments of the job size distribution. In this paper we prove that no approximation based on only the first two moments can be accurate for all job size distributions, and we provide a lower bound on the inapproximability ratio, which we refer to as “the gap.” This is the first such result in the literature to address “the gap.” The proof technique behind this result is novel as well and combines mean value analysis, sample path techniques, scheduling, regenerative arguments, and asymptotic estimates. Finally, our work provides insight into the effect of higher moments of the job size distribution on the mean waiting time.     

Systematic Construction of <Emphasis Type="Italic">q</Emphasis>-Analogs of <Emphasis Type="Italic">t</Emphasis>−(<Emphasis Type="Italic">v</Emphasis>,<Emphasis Type="Italic">k</Emphasis>,λ)-Designs

In the present paper we consider a q-analog of t–(v,k,)-designs. It is canonic since it arises by replacing sets by vector spaces over GF(q), and their orders by dimensions. These generalizations were introduced by Thomas [Geom.Dedicata vol. 63, pp. 247–253 (1996)] they are called t –(v,k,;q)- designs. A few of such q-analogs are known today, they were constructed using sophisticated geometric arguments and case-by-case methods. It is our aim now to present a general method that allows systematically to construct such designs, and to give complete catalogs (for small parameters, of course) using an implemented software package. &nbsp; In order to attack the (highly complex) construction, we prepare them for an enormous data reduction by embedding their definition into the theory of group actions on posets, so that we can derive and use a generalization of the Kramer-Mesner matrix for their definition, together with an improved version of the LLL-algorithm. By doing so we generalize the methods developed in a research project on t –(v,k,)-designs on sets, obtaining this way new results on the existence of t–(v,k,;q)-designs on spaces for further quintuples (t,v,k,;q) of parameters. We present several 2–(6,3,;2)-designs, 2–(7,3,;2)-designs and, as far as we know, the very first 3-designs over GF(q).classification 05B05     

Better <Emphasis Type="Italic">s</Emphasis>–<Emphasis Type="Italic">t</Emphasis>-tours by Gao trees

We consider the s–t-path TSP: given a finite metric space with two elements s and t, we look for a path from s to t that contains all the elements and has minimum total distance. We improve the approximation ratio for this problem from 1.599 to 1.566. Like previous algorithms, we solve the natural LP relaxation and represent an optimum solution \(x^*\) as a convex combination of spanning trees. Gao showed that there exists a spanning tree in the support of \(x^*\) that has only one edge in each narrow cut [i.e., each cut C with \(x^*(C)<2\)]. Our main theorem says that the spanning trees in the convex combination can be chosen such that many of them are such “Gao trees” simultaneously at all sufficiently narrow cuts.     

On Analytic Campanato and <Emphasis Type="Italic">F</Emphasis>(<Emphasis Type="Italic">p</Emphasis>, <Emphasis Type="Italic">q</Emphasis>, <Emphasis Type="Italic">s</Emphasis>) Spaces

We investigate the relation between analytic Campanato spaces \(\mathcal {AL}_{p,s}\) and the spaces F(p, q, s), characterize the bounded and compact Riemann–Stieltjes operators from \(\mathcal {AL}_{p,s}\) to \(F(p,p-s-1,s)\). We also describe the corona theorem and the interpolating sequences for the class \(F(p,p-2,s)\), which is the Möbius invariant subspace of the analytic Besov type spaces \(B_p(s)\).     

On the equation Δ<Emphasis Type="Italic">u</Emphasis> + <Emphasis Type="Italic">q</Emphasis>(<Emphasis Type="Italic">x</Emphasis>)<Emphasis Type="Italic">u</Emphasis> = 0

Sufficient conditions for the blow-up of nontrivial generalized solutions of the interior Dirichlet problem with homogeneous boundary condition for the homogeneous elliptic-type equation Δu + q(x)u = 0, where either q(x) ≠ const or q(x) = const= λ > 0, are obtained. A priori upper bounds (Theorem 4 and Remark 6) for the exact constants in the well-known Sobolev and Steklov inequalities are established.     

Relative <Emphasis Type="Italic">t</Emphasis>-designs in binary Hamming association scheme <Emphasis Type="Italic">H</Emphasis>(<Emphasis Type="Italic">n</Emphasis>, 2)

A relative t-design in the binary Hamming association schemes H(n, 2) is equivalent to a weighted regular t-wise balanced design, i.e., certain combinatorial t-design which allows different sizes of blocks and a weight function on blocks. In this paper, we study relative t-designs in H(n, 2), putting emphasis on Fisher type inequalities and the existence of tight relative t-designs. We mostly consider relative t-designs on two shells. We prove that if the weight function is constant on each shell of a relative t-design on two shells then the subset in each shell must be a combinatorial \((t-1)\)-design. This is a generalization of the result of Kageyama who proved this under the stronger assumption that the weight function is constant on the whole block set. Using this, we define tight relative t-designs for odd t, and a strong restriction on the possible parameters of tight relative t-designs in H(n, 2). We obtain a new family of such tight relative t-designs, which were unnoticed before. We will give a list of feasible parameters of such relative 3-designs with \(n \le 100\), and then we discuss the existence and/or the non-existence of such tight relative 3-designs. We also discuss feasible parameters of tight relative 4-designs on two shells in H(n, 2) with \(n \le 50\). In this study we come up with the connection on the topics of classical design theory, such as symmetric 2-designs (in particular 2-\((4u-1,2u-1,u-1)\) Hadamard designs) and Driessen’s result on the non-existence of certain 3-designs. We believe Problems 1 and 2 presented in Sect. 5.2 open a new way to study relative t-designs in H(n, 2). We conclude our paper listing several open problems.     

A theorem of the alternatives for the equation |<Emphasis Type="Italic">Ax</Emphasis>| − |<Emphasis Type="Italic">B</Emphasis>||<Emphasis Type="Italic">x</Emphasis>| = <Emphasis Type="Italic">b</Emphasis>

A theorem of the alternatives for the equation \({|Ax|-|B||x|=b\ (A,B\in{\mathbb{R}}^{n\times n},\, b\in{\mathbb{R}}^n)}\) is proved and several consequences are drawn. In particular, a class of matrices A, B is identified for which the equation has exactly 2 ⁿ solutions for each positive right-hand side b.     

On blocks with <Emphasis Type="Italic">K</Emphasis>(<Emphasis Type="Italic">B</Emphasis>)−<Emphasis Type="Italic">L</Emphasis>(<Emphasis Type="Italic">B</Emphasis>)=1

We use the method of local representation and original method of Brauer to study the block with K(B)−L(B)=1, and get some properties on the defect group and the structure of this kind of blocks. Then, we show that K(B) conjecture holds for this kind of blocks.     

(<Emphasis Type="Italic">K</Emphasis>, <Emphasis Type="Italic">N</Emphasis>)-Convexity and the Curvature-Dimension Condition for Negative <Emphasis Type="Italic">N</Emphasis>

We extend the range of N to negative values in the (K, N)-convexity (in the sense of Erbar–Kuwada–Sturm), the weighted Ricci curvature \(\mathop {\mathrm {Ric}}\nolimits _N\) and the curvature-dimension condition \(\mathop {\mathrm {CD}}\nolimits (K,N)\). We generalize a number of results in the case of \(N>0\) to this setting, including Bochner’s inequality, the Brunn–Minkowski inequality and the equivalence between \(\mathop {\mathrm {Ric}}\nolimits _N \ge K\) and \(\mathop {\mathrm {CD}}\nolimits (K,N)\). We also show an expansion bound for gradient flows of Lipschitz (K, N)-convex functions.     

Derivatives for smooth representations of <Emphasis Type="Italic">GL</Emphasis>(<Emphasis Type="Italic">n</Emphasis>, ℝ) and <Emphasis Type="Italic">GL</Emphasis>(<Emphasis Type="Italic">n</Emphasis>, ℂ)

The notion of derivatives for smooth representations of GL(n, ? _p ) was defined in [BZ77]. In the archimedean case, an analog of the highest derivative was defined for irreducible unitary representations in [Sah89] and called the “adduced” representation. In this paper we define derivatives of all orders for smooth admissible Fréchet representations of moderate growth. The real case is more problematic than the p-adic case; for example, arbitrary derivatives need not be admissible. However, the highest derivative continues being admissible, and for irreducible unitarizable representations coincides with the space of smooth vectors of the adduced representation.In the companion paper [AGS] we prove exactness of the highest derivative functor, and compute highest derivatives of all monomial representations.We apply those results to finish the computation of adduced representations for all irreducible unitary representations and to prove uniqueness of degenerate Whittaker models for unitary representations, thus completing the results of [Sah89, Sah90, SaSt90, GS13a].     

Max-Min Problems on the Ranks and Inertias of the Matrix Expressions <Emphasis Type="Italic">A</Emphasis>−<Emphasis Type="Italic">BXC</Emphasis>±(<Emphasis Type="Italic">BXC</Emphasis>)<Superscript>∗</Superscript> with Applications

We introduce a simultaneous decomposition for a matrix triplet (A,B,C ^∗), where A=±A ^∗ and (⋅)^∗ denotes the conjugate transpose of a matrix, and use the simultaneous decomposition to solve some conjectures on the maximal and minimal values of the ranks of the matrix expressions A−BXC±(BXC)^∗ with respect to a variable matrix X. In addition, we give some explicit formulas for the maximal and minimal values of the inertia of the matrix expression A−BXC−(BXC)^∗ with respect to X. As applications, we derive the extremal ranks and inertias of the matrix expression D−CXC ^∗ subject to Hermitian solutions of a consistent matrix equation AXA ^∗=B, as well as the extremal ranks and inertias of the Hermitian Schur complement D−B ^∗ A ^∼ B with respect to a Hermitian generalized inverse A ^∼ of A. Various consequences of these extremal ranks and inertias are also presented in the paper.     

An <Emphasis Type="Italic">L</Emphasis>-approach for packing (<Emphasis Type="Italic">ℓ</Emphasis>, <Emphasis Type="Italic">w</Emphasis>)-rectangles into rectangular and <Emphasis Type="Italic">L</Emphasis>-shaped pieces

This paper presents an approach using a recursive algorithm for packing (?, w)-rectangles into larger rectangular and L-shaped pieces. Such a problem has actual applications for non-guillotine cutting and pallet/container loading. Our motivation for developing the L-approach is based on the fact that it can solve difficult pallet loading instances. Indeed, it is able to solve all testing problems (more than 20 000 representatives of infinite equivalence classes of the literature), including the 18 hard instances unresolved by other heuristics. We conjecture that the L-approach always finds optimum packings of (?, w)-rectangles into rectangular pieces. Moreover, the approach may also be useful when dealing with cutting and packing problems involving L-shaped pieces.     

The crossing number of <Emphasis Type="Italic">G</Emphasis> ▭ <Emphasis Type="Italic">C</Emphasis><Subscript><Emphasis Type="Italic">n</Emphasis></Subscript> for the graph <Emphasis Type="Italic">G</Emphasis> on six vertices

The crossing numbers of Cartesian products of paths, cycles or stars with all graphs of order at most four are known. The crossing numbers of G□C _n for some graphs G on five and six vertices and the cycle C _n are also given. In this paper, we extend these results by determining the crossing number of the Cartesian product G □ C _n , where G is a specific graph on six vertices.     

The commutation relation <Emphasis Type="Italic">xy</Emphasis>=<Emphasis Type="Italic">qyx</Emphasis>+<Emphasis Type="Italic">hf</Emphasis>(<Emphasis Type="Italic">y</Emphasis>) and Newton’s binomial formula

Let x and y be two variables satisfying the commutation relation xy=qyx+hf(y), where f(y) is a polynomial. In this paper, using Young diagrams and generating functions techniques, we study the binomial formula (x+y) ⁿ and we present an identity for x ^m y. The connection to Operator Calculus is discussed and several special cases are treated explicitly.     

On common values of <Emphasis Type="Italic">φ</Emphasis>(<Emphasis Type="Italic">n</Emphasis>) and <Emphasis Type="Italic">σ</Emphasis>(<Emphasis Type="Italic">m</Emphasis>). I

We show, conditional on a uniform version of the prime k-tuples conjecture, that there are x/(log x)^1+o(1) numbers not exceeding x common to the ranges of φ and σ. Here φ is Euler’s totient function and σ is the sum-of-divisors function.     

Vector-valued interval functions and the Dedekind completion of <Emphasis Type="Italic">C</Emphasis>(<Emphasis Type="Italic">X</Emphasis>, <Emphasis Type="Italic">E</Emphasis>)

We consider interval valued functions with values in a Banach lattice E. Certain notions of continuity introduced earlier for real interval valued functions are generalised to the more general case considered here. As an application, we characterise the Dedekind completion of the space of continuous, E-valued functions on a paracompact \(T_{1}\)-space, extending a result of Anguelov.     

Period of the adelic Ikeda lift for <Emphasis Type="Italic">U</Emphasis>(<Emphasis Type="Italic">m</Emphasis>, <Emphasis Type="Italic">m</Emphasis>)

We give a period formula for the adelic Ikeda lift of an elliptic modular form f for U(m, m) in terms of special values of the adjoint L-functions of f. This is an adelic version of Ikeda’s conjecture on the period of the classical Ikeda lift for U(m, m).     

On nonregular ideals and <Emphasis Type="Italic">z</Emphasis>°-ideals in <Emphasis Type="Italic">C</Emphasis>(<Emphasis Type="Italic">X</Emphasis>)

The spaces X in which every prime z°-ideal of C(X) is either minimal or maximal are characterized. By this characterization, it turns out that for a large class of topological spaces X, such as metric spaces, basically disconnected spaces and one-point compactifications of discrete spaces, every prime z°-ideal in C(X) is either minimal or maximal. We will also answer the following questions: When is every nonregular prime ideal in C(X) a z°-ideal? When is every nonregular (prime) z-ideal in C(X) a z°-ideal? For instance, we show that every nonregular prime ideal of C(X) is a z°-ideal if and only if X is a ?-space (a space in which the boundary of any zeroset is contained in a zeroset with empty interior).     

On the Spectrum of the Sizes of Maximal Partial Line Spreads in <Emphasis Type="Italic">PG</Emphasis>(2<Emphasis Type="Italic">n</Emphasis>,<Emphasis Type="Italic">q</Emphasis>), <Emphasis Type="Italic">n</Emphasis> ≥ 3

A lot of research has been done on the spectrum of the sizes of maximal partial spreads in PG(3,q) [P. Govaerts and L. Storme, Designs Codes and Cryptography, Vol. 28 (2003) pp. 51–63; O. Heden, Discrete Mathematics, Vol. 120 (1993) pp. 75–91; O. Heden, Discrete Mathematics, Vol. 142 (1995) pp. 97–106; O. Heden, Discrete Mathematics, Vol. 243 (2002) pp. 135–150]. In [A. Gács and T. Sznyi, Designs Codes and Cryptography, Vol. 29 (2003) pp. 123–129], results on the spectrum of the sizes of maximal partial line spreads in PG(N,q), N 5, are given. In PG(2n,q), n 3, the largest possible size for a partial line spread is q^2n-1+q^2n-3+...+q³+1. The largest size for the maximal partial line spreads constructed in [A. Gács and T. Sznyi, Designs Codes and Cryptography, Vol. 29 (2003) pp. 123–129] is (q²ⁿ⁺¹–q)/(q²–1)–q³+q²–2q+2. This shows that there is a non-empty interval of values of k for which it is still not known whether there exists a maximal partial line spread of size k in PG(2n,q). We now show that there indeed exists a maximal partial line spread of size k for every value of k in that interval when q 9.J. Eisfeld: Supported by the FWO Research Network WO.011.96NP. Sziklai: The research of this author was partially supported by OTKA D32817, F030737, F043772, FKFP 0063/2001 and Magyary Zoltan grants. The third author is grateful for the hospitality of Ghent University.     

Further remarks on <Emphasis Type="Italic">δ</Emphasis>- and <Emphasis Type="Italic">θ</Emphasis>-modifications

In generalizing constructions of N.V. Veličko, the paper starts from two generalized topologies μ and μ′ on a set X and introduces two more generalized topologies gd(μ, μ′) and δ(μ,μ′) with the examination of their properties. Research (partially) supported by Hungarian Foundation for Scientific Research, grant Nos. T 49786, T 046846, K 68398.