Two-agent scheduling on uniform parallel machines with min-max criteria

We consider the problem of scheduling two agents A and B on a set of m uniform parallel machines. Each agent is assumed to be independent from the other: agent A and agent B are made up of n _A and n _B jobs, respectively. Each job is defined by its processing time and possibly additional data such as a due date, a weight, etc., and must be processed on a single machine. All machines are uniform, i.e. each machine has its own processing speed. Notice that we consider the special case of equal-size jobs, i.e. all jobs share the same processing time. Our goal is to minimize two maximum functions associated with agents A and B and referred to as $F_{max}^{A}=\max_{i\in A} f^{A}_{i}(C_{i})$ and $F_{max}^{B}=\max_{i\in B}f^{B}_{i}(C_{i})$ , respectively, with C _i the completion time of job i and $f_{i}^{X}$ a non-decreasing function. These kinds of problems are called multi-agent scheduling problems. As we are dealing with two conflicting criteria, we focus on the calculation of the strict Pareto optima for the $(F_{max}^{A}, F_{max}^{B} )$ criteria vector. In this paper we develop a minimal complete Pareto set enumeration algorithm with time complexity and memory requirements.     

On $$(\ell,m)$$-regular partitions with distinct parts

Let \(a_{\ell ,m}(n)\) denote the number of \((\ell ,m)\)-regular partitions of a positive integer n into distinct parts, where \(\ell \) and m are relatively primes. In this paper, we establish several infinite families of congruences modulo 2 for \(a_{3,5}(n)\). For example,

$$\begin{aligned} a_{3, 5}\left(2^{6\alpha +4}5^{2\beta }n+\frac{ 2^{6\alpha +3}5^{2\beta +1}-1}{3}\right) \equiv 0 , \end{aligned}$$

where \(\alpha , \beta \ge 0\).

     

Improved online algorithms for the batch scheduling of equal-length jobs with incompatible families to maximize the weighted number of early jobs

We consider the online scheduling of equal-length jobs with incompatible families on \(m\) identical batch machines. Each job has a release time, a deadline and a weight. Each batch machine can process up to \(b\) jobs (which come from the same family) simultaneously as a batch, where \(b\) is called the capacity of the machines. Our goal is to determine a preemption-restart schedule which maximizes the weighted number of early jobs. For this problem, Li et al. (Inf Process Lett 112:503–508, 2012) provided an online algorithm of competitive ratio \(3+2\sqrt{2}\) for both \(b=\infty \) and \(b<\infty \) . In this paper, we study two special cases of this problem. For the case that \(m=2\) , we first present a lower bound 2, and then provide an online algorithm with a competitive ratio of 3 for both \(b=\infty \) and \(b<\infty \) . For the case in which \(m=3\) , \(b=\infty \) and all jobs come from a common family, we present an online algorithm with a competitive ratio of \((8+2\sqrt{15})/3\approx 5.249\) .     

Families of log canonically polarized varieties

Determining the number of singular fibers in a family of varieties over a curve is a generalization of Shafarevich’s Conjecture and has implications for the types of subvarieties that can appear in the corresponding moduli stack. We consider families of log canonically polarized varieties over \({\mathbb {P}^1}\) , i.e. families \({g:(Y, D) \to \mathbb {P}^1}\) where D is an effective snc divisor and the sheaf \({\omega_{Y/\mathbb {P}^1}(D)}\) is g-ample. After first defining what it means for fibers of such a family to be singular, we show that with the addition of certain mild hypotheses (the fibers have finite automorphism group, \({\mathcal {O}_Y(D)}\) is semi-ample, and the components of D must avoid the singular locus of the fibers and intersect the fibers transversely), such a family must either be isotrivial or contain at least 3 singular fibers.     

Bavrin’s Type Factorization of the Temljakov Operator for Holomorphic Functions in Circular Domains of $$\mathbb {C}^{n}$$

The paper concerns investigations of holomorphic functions of several complex variables with a factorization of their Temljakov transform. Firstly, there were considered some inclusions between the families \(\mathcal {C}_{\mathcal {G}},\mathcal {M}_{\mathcal {G}},\mathcal {N}_{\mathcal {G}},\mathcal {R}_{\mathcal {G}},\mathcal {V}_{\mathcal {G}}\) of such holomorphic functions on complete n-circular domain \(\mathcal {G}\) of \(\mathbb {C}^{n}\) in some papers of Bavrin, Fukui, Higuchi, Michiwaki. A motivation of our investigations is a condensation of the mentioned inclusions by some new families of Bavrin’s type. Hence we consider some families \(\mathcal {K}_{ \mathcal {G}}^{k},k\ge 2,\) of holomorphic functions f :  \(\mathcal {G}\rightarrow \mathbb {C},f(0)=1,\) defined also by a factorization of \( \mathcal {L}f\) onto factors from \(\mathcal {C}_{\mathcal {G}}\) and \(\mathcal {M} _{\mathcal {G}}.\) We present some interesting properties and extremal problems on \(\mathcal {K}_{\mathcal {G}}^{k}\).     

A family of discrete semi-classical orthogonal polynomials of class one

In this work, we solve the system of Laguerre–Freud equations for the recurrence coefficients \(\beta _n\), \(\gamma _{n+1} , n \ge 0\) of the \(D_{w}\)-semi-classical orthogonal polynomials sequences of class one in the case when \(\beta _{0}=-t_{0}\), \(\beta _{n+1}=t_{n}-t_{n+1}\) and \(\gamma _{n+1}=-t_{n}^{2}\) with \(t_{n}\ne 0\;n\ge 0\), where \(D_w\) is the divided difference operator. There are essentially four canonical families.     

Ranks of ideals in inverse semigroups of difunctional binary relations

The set \(\mathcal {D}_n\) of all difunctional relations on an n element set is an inverse semigroup under a variation of the usual composition operation. We solve an open problem of Kudryavtseva and Maltcev (Publ Math Debrecen 78(2):253–282, 2011), which asks: What is the rank (smallest size of a generating set) of \(\mathcal {D}_n\)? Specifically, we show that the rank of \(\mathcal {D}_n\) is \(B(n)+n\), where B(n) is the nth Bell number. We also give the rank of an arbitrary ideal of \(\mathcal {D}_n\). Although \(\mathcal {D}_n\) bears many similarities with families such as the full transformation semigroups and symmetric inverse semigroups (all contain the symmetric group and have a chain of \(\mathscr {J}\)-classes), we note that the fast growth of \({\text {rank}}(\mathcal {D}_n)\) as a function of n is a property not shared with these other families.     

Complete weight enumerators of a class of linear codes

Let \(\mathbb {F}_{q}\) be the finite field with \(q=p^{m}\) elements, where p is an odd prime and m is a positive integer. For a positive integer t, let \(D\subset \mathbb {F}^{t}_{q}\) and let \({\mathrm {Tr}}_{m}\) be the trace function from \(\mathbb {F}_{q}\) onto \(\mathbb {F}_{p}\). In this paper, let \(D=\{(x_{1},x_{2},\ldots ,x_{t}) \in \mathbb {F}_{q}^{t}\setminus \{(0,0,\ldots ,0)\} : {\mathrm {Tr}}_{m}(x_{1}+x_{2}+\cdots +x_{t})=0\},\) we define a p-ary linear code \(\mathcal {C}_{D}\) by

$$\begin{aligned} \mathcal {C}_{D}=\{\mathbf {c}(a_{1},a_{2},\ldots ,a_{t}) : (a_{1},a_{2},\ldots ,a_{t})\in \mathbb {F}^{t}_{q}\}, \end{aligned}$$

where

$$\begin{aligned} \mathbf {c}(a_{1},a_{2},\ldots ,a_{t})=({\mathrm {Tr}}_{m}(a_{1}x^{2}_{1}+a_{2}x^{2}_{2}+\cdots +a_{t}x^{2}_{t}))_{(x_{1},x_{2},\ldots ,x_{t}) \in D}. \end{aligned}$$

We shall present the complete weight enumerators of the linear codes \(\mathcal {C}_{D}\) and give several classes of linear codes with a few weights. This paper generalizes the results of Yang and Yao (Des Codes Cryptogr, 2016).

     

Relative Difference Sets and Hadamard Matrices from Perfect Quaternionic Arrays

Let \(G=\mathbf{C}_{n_1}\times \cdots \times \mathbf{C}_{n_m}\) be an abelian group of order \(n=n_1\dots n_m\), where each \(\mathbf{C}_{n_t}\) is cyclic of order \(n_t\). We present a correspondence between the (4n, 2, 4n, 2n)-relative difference sets in \(G\times Q_8\) relative to the centre \(Z(Q_8)\) and the perfect arrays of size \(n_1\times \dots \times n_m\) over the quaternionic alphabet \(Q_8\cup qQ_8\), where \(q=(1+i+j+k)/2\). In view of this connection, for \(m=2\) we introduce new families of relative difference sets in \(G\times Q_8\), as well as new families of Williamson and Ito Hadamard matrices with G-invariant components.     

The Minimal Size of Infinite Maximal Antichains in Direct Products of Partial Orders

For a partial order \(\mathbb {P}\) having infinite antichains by \(\mathfrak {a}(\mathbb {P})\) we denote the minimal cardinality of an infinite maximal antichain in \(\mathbb {P}\) and investigate how does this cardinal invariant of posets behave in finite products. In particular we show that \(\min \{ \mathfrak {a}(\mathbb {P}),\mathfrak {p} (\text {sq} \mathbb {P}) \} \leq \mathfrak {a} (\mathbb {P}^{n} ) \leq \mathfrak {a} (\mathbb {P})\), for all \(n\in \mathbb {N}\), where \(\mathfrak {p} (\text {sq} \mathbb {P})\) is the minimal size of a centered family without a lower bound in the separative quotient of the poset \(\mathbb {P}\), or \(\mathfrak {p} (\text {sq} \mathbb {P})=\infty \), if there is no such family. So we have \(\mathfrak {a} (\mathbb {P} \times \mathbb {P})=\mathfrak {a} (\mathbb {P})\) whenever \(\mathfrak {p} (\text {sq} \mathbb {P})\geq \mathfrak {a} (\mathbb {P})\) and we show that, in addition, this equality holds for all posets obtained from infinite Boolean algebras of size ≤ø ₁ by removing zero, all reversed trees, all atomic posets and, in particular, for all posets of the form \(\langle \mathcal {C} ,\subset \rangle \), where \(\mathcal {C}\) is a family of nonempty closed sets in a compact T ₁-space containing all singletons. As a by-product we obtain the following combinatorial statement: If X is an infinite set and {A _i ×B _i :i∈I} an infinite partition of the square X ², then at least one of the families {A _i :i∈I} and {B _i :i∈I} contains an infinite partition of X.     

Infinite-dimensional quasigroups of finite orders

Let Σ be a finite set of cardinality k > 0, let $\mathbb{A}$ be a finite or infinite set of indices, and let $\mathcal{F} \subseteq \Sigma ^\mathbb{A}$ be a subset consisting of finitely supported families. A function $f:\Sigma ^\mathbb{A} \to \Sigma$ is referred to as an $\mathbb{A}$ -quasigroup (if $\left| \mathbb{A} \right| = n$ , then an n-ary quasigroup) of order k if $f\left( {\bar y} \right) \ne f\left( {\bar z} \right)$ for any ordered families $\bar y$ and $\bar z$ that differ at exactly one position. It is proved that an $\mathbb{A}$ -quasigroup f of order 4 is reducible (representable as a superposition) or semilinear on every coset of $\mathcal{F}$ . It is shown that the quasigroups defined on Σ^?, where ? are positive integers, generate Lebesgue nonmeasurable subsets of the interval [0, 1].     

Uniform parallel machine scheduling problems with fixed machine cost

This paper considers two uniform parallel machine scheduling problems with fixed machine cost under the background of cloud manufacturing. The goal is to minimize the makespan with a given budget of total cost, \(\hat{U}\). All the jobs are homogeneous, i.e., the processing times of the jobs are identical. Non-preemptive and preemptive problems are studied. For the non-preemptive problem, we give a \(2[1+1{/}(h-1)]\)-approximation algorithm, where h is the number of the machine which can not be selected the first time. For the preemptive problem, we give an algorithm whose worst-case bound equals to \(1+1{/}(h-1)\). Preliminary experimental results indicate that the proposed algorithms are reasonably accurate compared with the lower bounds.     

Study of LG-Holling type III predator–prey model with disease in predator

Let \(\mathbb F_{q}\) be a finite field with \(q=p^{m}\) elements, where p is an odd prime and m is a positive integer. In this paper, let \(D=\{(x_{1},x_{2},\ldots ,x_{n})\in \mathbb F_{q}^{n}\backslash \{(0,0,\ldots )\}: Tr(x_{1}^{p^{k_{1}}+1}+x_{2}^{p^{k_{2}}+1}+\cdots +x_{n}^{p^{k_{n}}+1})=c\}\), where \(c\in \mathbb F_p\), Tr is the trace function from \(\mathbb F_{q}\) to \(\mathbb F_{p}\) and each \(m/(m,k_{i})\) ( \(1\le i\le n\) ) is odd. we define a p-ary linear code \(C_{D}=\{c(a_{1},a_{2},\ldots ,a_{n}):(a_{1},a_{2},\ldots ,a_{n})\in \mathbb F_{q}^{n}\}\), where \(c(a_{1},a_{2},\ldots ,a_{n})=(Tr(a_{1}x_{1}+a_{2}x_{2}+\cdots +a_{n}x_{n}))_{(x_{1},x_{2},\ldots ,x_{n})\in D}\). We present the weight distributions of the classes of linear codes which have at most three weights.     

Cohomological and Poisson structures and integrable hierarchies in tautological subbundles for Birkhoff strata of the Sato Grassmannian

We consider cohomological and Poisson structures associated with the special tautological subbundles $TB_{W_{1,2, \ldots n} }$ for the Birkhoff strata of the Sato Grassmannian. We show that the tangent bundles of $TB_{W_{1,2, \ldots n} }$ are isomorphic to the linear spaces of two-coboundaries with vanishing Harrison cohomology modules. A special class of two-coboundaries is provided by a system of integrable quasilinear partial differential equations. For the big cell, it is the hierarchy of dispersionless Kadomtsev-Petvishvili (dKP) equations. We also demonstrate that the families of ideals for algebraic varieties in $TB_{W_{1,2, \ldots n} }$ can be viewed as Poisson ideals. This observation establishes a relation between families of algebraic curves in $TB_{W_{\hat S} }$ and coisotropic deformations of such curves of zero and nonzero genus described by hierarchies of systems of hydrodynamic type; the dKP hierarchy is such a hierarchy. We note the interrelation between cohomological and Poisson structures.     

On Standard Derived Equivalences of Orbit Categories

Let k be a commutative ring, \(\mathcal {A}\) and \(\mathcal {B}\) – two k-linear categories with an action of a group G. We introduce the notion of a standard G-equivalence from \(\mathcal {K}_{p}^{\mathrm {b}}\mathcal {B}\) to \(\mathcal {K}_{p}^{\mathrm {b}}\mathcal {A}\), where \(\mathcal {K}_{p}^{\mathrm {b}}\mathcal {A}\) is the homotopy category of finitely generated projective \(\mathcal {A}\)-complexes. We construct a map from the set of standard G-equivalences to the set of standard equivalences from \(\mathcal {K}_{p}^{\mathrm {b}}\mathcal {B}\) to \(\mathcal {K}_{p}^{\mathrm {b}}\mathcal {A}\) and a map from the set of standard G-equivalences from \(\mathcal {K}_{p}^{\mathrm {b}}\mathcal {B}\) to \(\mathcal {K}_{p}^{\mathrm {b}}\mathcal {A}\) to the set of standard equivalences from \(\mathcal {K}_{p}^{\mathrm {b}}(\mathcal {B}/G)\) to \(\mathcal {K}_{p}^{\mathrm {b}}(\mathcal {A}/G)\), where \(\mathcal {A}/G\) denotes the orbit category. We investigate the properties of these maps and apply our results to the case where \(\mathcal {A}=\mathcal {B}=R\) is a Frobenius k-algebra and G is the cyclic group generated by its Nakayama automorphism ν. We apply this technique to obtain the generating set of the derived Picard group of a Frobenius Nakayama algebra over an algebraically closed field.     

On sums of binomial coefficients involving Catalan and Delannoy numbers modulo $$p^2$$

In this paper, we prove some congruences conjectured by Z.-W. Sun: For any prime \(p>3\), we determine

$$\begin{aligned} \sum \limits _{k = 0}^{p - 1} {\frac{{{C_k}C_k^{(2)}}}{{{{27}^k}}}} \quad {\text { and }}\quad \sum \limits _{k = 1}^{p - 1} {\frac{{\left( {\begin{array}{l} {2k} \\ {k - 1} \\ \end{array}} \right) \left( { \begin{array}{l} {3k} \\ {k - 1} \\ \end{array} } \right) }}{{{{27}^k}}}} \end{aligned}$$

modulo \(p^2\), where \(C_k=\frac{1}{k+1}\left( {\begin{array}{c}2k\\ k\end{array}}\right) \) is the k-th Catalan number and \(C_k^{(2)}=\frac{1}{2k+1}\left( {\begin{array}{c}3k\\ k\end{array}}\right) \) is the second-order Catalan numbers of the first kind. And we prove that

$$\begin{aligned} \sum _{k=1}^{p-1}\frac{D_k}{k}\equiv -q_p(2)+pq_p(2)^2\pmod {p^2}, \end{aligned}$$

where \(D_n=\sum _{k=0}^{n}\left( {\begin{array}{c}n\\ k\end{array}}\right) \left( {\begin{array}{c}n+k\\ k\end{array}}\right) \) is the n-th Delannoy number and \(q_p(2)=(2^{{p-1}}-1)/p\) is the Fermat quotient.

     

Analysing the Wu metric on a class of eggs in ℂ<Superscript><Emphasis Type="Italic">n</Emphasis></Superscript> – I

We study the Wu metric on convex egg domains of the form

$$E_{2m} = \big\{ z \in \mathbb{C}^{n}: \vert{z_{1}} \vert^{2m} + \vert {z_{2}} \vert^{2} + {\cdots} + \vert {z_{n-1}} \vert^{2} + \vert {z_{n}} \vert^{2} <1 \big\}, $$

where m ≥ 1/2,m ≠ 1. The Wu metric is shown to be real analytic everywhere except on a lower dimensional subvariety where it fails to be C ²-smooth. Overall however, the Wu metric is shown to be continuous when m = 1/2 and even C ¹-smooth for each m > 1/2, and in all cases, a non-Kähler Hermitian metric with its holomorphic curvature strongly negative in the sense of currents. This gives a natural answer to a conjecture of S. Kobayashi and H. Wu for such E _2m .     

Extremal Problems for Mappings with Generalized Parametric Representation in $${{\mathbb {C}}}^{n}$$

In this paper we are concerned with the family \(\widetilde{S}^t_A(\mathbb {B}^n)\) (\(t\ge 0\)) of normalized biholomorphic mappings on the Euclidean unit ball \(\mathbb {B}^n\) in \({\mathbb {C}}^n\) that can be embedded in normal Loewner chains whose normalizations are given by time-dependent operators \(A\in \widetilde{\mathcal {A}}\), where \(\widetilde{\mathcal {A}}\) is a family of measurable mappings from \([0,\infty )\) into \(L({\mathbb {C}}^n)\) which satisfy certain natural assumptions. In particular, we consider extreme points and support points associated with the compact family \(\widetilde{S}^t_A(\mathbb {B}^n)\), where \(A\in \widetilde{\mathcal {A}}\). We prove that if \(f(z,t)=V(t)^{-1}z+\cdots \) is a normal Loewner chain such that \(V(s)f(\cdot ,s)\in \mathrm{ex}\,\widetilde{S}^s_A(\mathbb {B}^n)\) (resp. \(V(s)f(\cdot ,s)\in \mathrm{supp}\,\widetilde{S}^s_A(\mathbb {B}^n)\)), then \(V(t)f(\cdot ,t)\in \mathrm{ex}\, \widetilde{S}^t_A(\mathbb {B}^n)\), for all \(t\ge s\) (resp. \(V(t)f(\cdot ,t)\in \mathrm{supp}\,\widetilde{S}^t_A(\mathbb {B}^n)\), for all \(t\ge s\)), where V(t) is the unique solution on \([0,\infty )\) of the initial value problem: \(\frac{d V}{d t}(t)=-A(t)V(t)\), a.e. \(t\ge 0\), \(V(0)=I_n\). Also, we obtain an example of a bounded support point for the family \(\widetilde{S}_A^t(\mathbb {B}^2)\), where \(A\in \widetilde{\mathcal {A}}\) is a certain time-dependent operator. We also consider the notion of a reachable family with respect to time-dependent linear operators \(A\in \widetilde{\mathcal {A}}\), and obtain characterizations of extreme/support points associated with these families of bounded biholomorphic mappings on \(\mathbb {B}^n\). Useful examples and applications yield that the study of the family \(\widetilde{S}^t_A(\mathbb {B}^n)\) for time-dependent operators \(A\in \widetilde{\mathcal {A}}\) is basically different from that in the case of constant time-dependent linear operators.     

Regularity of semi-stable solutions to fourth order nonlinear eigenvalue problems on general domains

We examine the fourth order problem $\Delta ^2 u = \lambda f(u) $ in $ \Omega $ with $ \Delta u = u =0 $ on $ {\partial \Omega }$ , where $ \lambda > 0$ is a parameter, $ \Omega $ is a bounded domain in $\mathbb{R }^N$ and where $f$ is one of the following nonlinearities: $ f(u)=e^u$ , $ f(u)=(1+u)^p $ or $ f(u)= \frac{1}{(1-u)^p}$ where $ p>1$ . We show the extremal solution is smooth, provided $$\begin{aligned} N < 2 + 4 \sqrt{2} + 4 \sqrt{ 2 - \sqrt{2}} \approx 10.718 \text{ when} f(u)=e^u, \end{aligned}$$ and $$\begin{aligned} N < \frac{4p}{p-1} + \frac{4(p+1)}{p-1} \left( \sqrt{ \frac{2p}{p+1}} + \sqrt{ \frac{2p}{p+1} - \sqrt{ \frac{2p}{p+1}}} - \frac{1}{2} \right) \end{aligned}$$ when $ f(u)=(u+1)^p$ . New results are also obtained in the case where $ f(u)=(1-u)^{-p}$ . These are substantial improvements to various results on critical dimensions obtained recently by various authors. To do that, we derive a new stability inequality satisfied by minimal solutions of the above equation, which is more amenable to estimates as it allows a method of proof reminiscent of the second order case.     

Existence of multi-bump solutions for a class of elliptic problems involving the biharmonic operator

Using variational methods, we establish existence of multi-bump solutions for the following class of problems

$$\begin{aligned} \left\{ \begin{array}{l} \Delta ^2 u +(\lambda V(x)+1)u = f(u), \quad \text{ in } \quad \mathbb {R}^{N},\\ u \in H^{2}(\mathbb {R}^{N}), \end{array} \right. \end{aligned}$$

where \(N \ge 1\), \(\Delta ^2\) is the biharmonic operator, f is a continuous function with subcritical growth, \(V : \mathbb {R}^N \rightarrow \mathbb {R}\) is a continuous function verifying some conditions and \(\lambda >0\) is a real constant large enough.