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\) .     

Tree metrics and edge-disjoint S-paths

Given an undirected graph \(G=(V,E)\) with a terminal set \(S \subseteq V\) , a weight function on terminal pairs, and an edge-cost \(a: E \rightarrow \mathbf{Z}_+\) , the \(\mu \) -weighted minimum-cost edge-disjoint \(S\) -paths problem ( \(\mu \) -CEDP) is to maximize \(\sum \nolimits _{P \in \mathcal{P}} \mu (s_P,t_P) - a(P)\) over all edge-disjoint sets \(\mathcal{P}\) of \(S\) -paths, where \(s_P,t_P\) denote the ends of \(P\) and \(a(P)\) is the sum of edge-cost \(a(e)\) over edges \(e\) in \(P\) . Our main result is a complete characterization of terminal weights \(\mu \) for which \(\mu \) -CEDP is tractable and admits a combinatorial min–max theorem. We prove that if \(\mu \) is a tree metric, then \(\mu \) -CEDP is solvable in polynomial time and has a combinatorial min–max formula, which extends Mader’s edge-disjoint \(S\) -paths theorem and its minimum-cost generalization by Karzanov. Our min–max theorem includes the dual half-integrality, which was earlier conjectured by Karzanov for a special case. We also prove that \(\mu \) -EDP, which is \(\mu \) -CEDP with \(a = 0\) , is NP-hard if \(\mu \) is not a truncated tree metric, where a truncated tree metric is a weight function represented as pairwise distances between balls in a tree. On the other hand, \(\mu \) -CEDP for a truncated tree metric \(\mu \) reduces to \(\mu '\) -CEDP for a tree metric \(\mu '\) . Thus our result is best possible unless P = NP. As an application, we obtain a good approximation algorithm for \(\mu \) -EDP with “near” tree metric \(\mu \) by utilizing results from the theory of low-distortion embedding.     

Scattered linear sets generated by collineations between pencils of lines

Let \(A\) and \(B\) be two points of \(\mathrm{{PG}}(2,q^n)\) , and let \(\Phi \) be a collineation between the pencils of lines with vertices \(A\) and \(B\) . In this paper, we prove that the set of points of intersection of corresponding lines under \(\Phi \) is either the union of a scattered \(\mathrm{{GF}}(q)\) -linear set of rank \(n+1\) with the line \(AB\) or the union of \(q-1\) scattered \(\mathrm{{GF}}(q)\) -linear sets of rank \(n\) with \(A\) and \(B\) . We also determine the intersection configurations of two scattered \(\mathrm{{GF}}(q)\) -linear sets of rank \(n+1\) of \(\mathrm{{PG}}(2,q^n)\) both meeting the line \(AB\) in a \(\mathrm{{GF}}(q)\) -linear set of pseudoregulus type with transversal points \(A\) and \(B\) .     

The large rank of a finite semigroup using prime subsets

The large rank of a finite semigroup \(\Gamma \) , denoted by \(r_5(\Gamma )\) , is the least number \(n\) such that every subset of \(\Gamma \) with \(n\) elements generates \(\Gamma \) . Howie and Ribeiro showed that \(r_5(\Gamma ) = |V| + 1\) , where \(V\) is a largest proper subsemigroup of \(\Gamma \) . This work considers the complementary concept of subsemigroups, called prime subsets, and gives an alternative approach to find the large rank of a finite semigroup. In this connection, the paper provides a shorter proof of Howie and Ribeiro’s result about the large rank of Brandt semigroups. Further, this work obtains the large rank of the semigroup of order-preserving singular selfmaps.     

Neighbour-transitive codes in Johnson graphs

The Johnson graph \(J(v,k)\) has, as vertices, the \(k\) -subsets of a \(v\) -set \(\mathcal {V}\) and as edges the pairs of \(k\) -subsets with intersection of size \(k-1\) . We introduce the notion of a neighbour-transitive code in \(J(v,k)\) . This is a proper vertex subset \(\Gamma \) such that the subgroup \(G\) of graph automorphisms leaving \(\Gamma \) invariant is transitive on both the set \(\Gamma \) of ‘codewords’ and also the set of ‘neighbours’ of \(\Gamma \) , which are the non-codewords joined by an edge to some codeword. We classify all examples where the group \(G\) is a subgroup of the symmetric group \(\mathrm{Sym}\,(\mathcal {V})\) and is intransitive or imprimitive on the underlying \(v\) -set \(\mathcal {V}\) . In the remaining case where \(G\le \mathrm{Sym}\,(\mathcal {V})\) and \(G\) is primitive on \(\mathcal {V}\) , we prove that, provided distinct codewords are at distance at least \(3\) , then \(G\) is \(2\) -transitive on \(\mathcal {V}\) . We examine many of the infinite families of finite \(2\) -transitive permutation groups and construct surprisingly rich families of examples of neighbour-transitive codes. A major unresolved case remains.     

Optimal mass transport and symmetric representations of their cost functions

We consider Monge–Kantorovich problems corresponding to general cost functions \(c(x,y)\) but with symmetry constraints on a Polish space \(X\times X\) . Such couplings naturally generate anti-symmetric Hamiltonians on \(X\times X\) that are \(c\) -convex with respect to one of the variables. In particular, if \(c\) is differentiable with respect to the first variable on an open subset \(X\) in \( \mathbb {R}^d\) , we show that for every probability measure \(\mu \) on \(X\) , there exists a symmetric probability measure \(\pi _0\) on \(X\times X\) with marginals \(\mu \) , and an anti-symmetric Hamiltonian \(H\) such that \(\nabla _2H(y, x)=\nabla _1c(x,y)\) for \( \pi _0\) -almost all \((x,y) \in X \times X.\) If \(\pi _0\) is supported on a graph \((x, Sx)\) , then \(S\) is necessarily a \(\mu \) -measure preserving involution (i.e., \(S^2=I\) ) and \(\nabla _2H(x, Sx)=\nabla _1c(Sx,x)\) for \(\mu \) -almost all \(x \in X.\) For monotone cost functions such as those given by \(c(x,y)=\langle x, u(y)\rangle \) or \(c(x,y)=-|x-u(y)|^2\) where \(u\) is a monotone operator, \(S\) is necessarily the identity yielding a classical result by Krause, namely that \(u(x)=\nabla _2H(x, x)\) where \(H\) is anti-symmetric and concave-convex.     

Stationary and invariant densities and disintegration kernels

Let \(G\) be a locally compact topological group, acting measurably on some Borel spaces \(S\) and \(T\) , and consider some jointly stationary random measures \(\xi \) on \(S\times T\) and \(\eta \) on \(S\) such that \(\xi (\cdot \times T)\ll \eta \) a.s. Then there exists a stationary random kernel \(\zeta \) from \(S\) to \(T\) such that \(\xi =\eta \otimes \zeta \) a.s. This follows from the existence of an invariant kernel \(\varphi \) from \(S\times {\mathcal {M}}_{S\times T}\times {\mathcal {M}}_S\) to \(T\) such that \(\mu =\nu \otimes \varphi (\cdot ,\mu ,\nu )\) whenever \(\mu (\cdot \times T)\ll \nu \) . Also included are some related results on stationary integration, absolute continuity, and ergodic decomposition.     

Some totally geodesic submanifolds of the nonlinear Grassmannian of a compact symmetric space

Let \(M\) and \(N\) be two connected smooth manifolds, where \(M\) is compact and oriented and \(N\) is Riemannian. Let \(\mathcal {E}\) be the Fréchet manifold of all embeddings of \(M\) in \(N\) , endowed with the canonical weak Riemannian metric. Let \(\sim \) be the equivalence relation on \(\mathcal {E}\) defined by \(f\sim g\) if and only if \(f=g\circ \phi \) for some orientation preserving diffeomorphism \(\phi \) of \(M\) . The Fréchet manifold \(\mathcal {S}= \mathcal {E}/_{\sim }\) of equivalence classes, which may be thought of as the set of submanifolds of \(N\) diffeomorphic to \(M\) and is called the nonlinear Grassmannian (or Chow manifold) of \(N\) of type \(M\) , inherits from \( \mathcal {E}\) a weak Riemannian structure. We consider the following particular case: \(N\) is a compact irreducible symmetric space and \(M\) is a reflective submanifold of \(N\) (that is, a connected component of the set of fixed points of an involutive isometry of \( N\) ). Let \(\mathcal {C}\) be the set of submanifolds of \(N\) which are congruent to \(M\) . We prove that the natural inclusion of \(\mathcal {C}\) in \(\mathcal {S}\) is totally geodesic.     

Mean Squared Error Minimization for Inverse Moment Problems

We consider the problem of approximating the unknown density \(u\in L^2(\Omega ,\lambda )\) of a measure \(\mu \) on \(\Omega \subset \mathbb {R}^n\) , absolutely continuous with respect to some given reference measure \(\lambda \) , only from the knowledge of finitely many moments of \(\mu \) . Given \(d\in \mathbb {N}\) and moments of order \(d\) , we provide a polynomial \(p_d\) which minimizes the mean square error \(\int (u-p)^2d\lambda \) over all polynomials \(p\) of degree at most \(d\) . If there is no additional requirement, \(p_d\) is obtained as solution of a linear system. In addition, if \(p_d\) is expressed in the basis of polynomials that are orthonormal with respect to \(\lambda \) , its vector of coefficients is just the vector of given moments and no computation is needed. Moreover \(p_d\rightarrow u\) in \(L^2(\Omega ,\lambda )\) as \(d\rightarrow \infty \) . In general nonnegativity of \(p_d\) is not guaranteed even though \(u\) is nonnegative. However, with this additional nonnegativity requirement one obtains analogous results but computing \(p_d\ge 0\) that minimizes \(\int (u-p)^2d\lambda \) now requires solving an appropriate semidefinite program. We have tested the approach on some applications arising from the reconstruction of geometrical objects and the approximation of solutions of nonlinear differential equations. In all cases our results are significantly better than those obtained with the maximum entropy technique for estimating \(u\) .     

On lower bounds for cohomology growth in p-adic analytic towers

Let \(p\) and \(\ell \) be two distinct prime numbers and let \(\Gamma \) be a group. We study the asymptotic behaviour of the mod- \(\ell \) Betti numbers in \(p\) -adic analytic towers of finite index subgroups. If \(\Theta \) is a finite \(\ell \) -group of automorphisms of \(\Gamma \) , our main theorem allows to lift lower bounds for the mod- \(\ell \) cohomology growth in the fixed point group \(\Gamma ^\Theta \) to lower bounds for the growth in \(\Gamma \) . We give applications to \(S\) -arithmetic groups and we also obtain a similar result for cohomology with rational coefficients.     

Non-Lipschitz points and the {\textit{SBV}} regularity of the minimum time function

This paper is devoted to the study of the Hausdorff dimension of the singular set of the minimum time function \(T\) under controllability conditions which do not imply the Lipschitz continuity of \(T\) . We consider first the case of normal linear control systems with constant coefficients in \({\mathbb {R}}^N\) . We characterize points around which \(T\) is not Lipschitz as those which can be reached from the origin by an optimal trajectory (of the reversed dynamics) with vanishing minimized Hamiltonian. Linearity permits an explicit representation of such set, that we call \(\mathcal {S}\) . Furthermore, we show that \(\mathcal {S}\) is countably \(\mathcal {H}^{N-1}\) -rectifiable with positive \(\mathcal {H}^{N-1}\) -measure. Second, we consider a class of control-affine planar nonlinear systems satisfying a second order controllability condition: we characterize the set \(\mathcal {S}\) in a neighborhood of the origin in a similar way and prove the \(\mathcal {H}^1\) -rectifiability of \(\mathcal {S}\) and that \(\mathcal {H}^1(\mathcal {S})>0\) . In both cases, \(T\) is known to have epigraph with positive reach, hence to be a locally \(BV\) function (see Colombo et al.: SIAM J Control Optim 44:2285–2299, 2006; Colombo and Nguyen.: Math Control Relat 3: 51–82, 2013). Since the Cantor part of \(DT\) must be concentrated in \(\mathcal {S}\) , our analysis yields that \(T\) is locally \(SBV\) , i.e., the Cantor part of \(DT\) vanishes. Our results imply also that \(T\) is differentiable outside a \(\mathcal {H}^{N-1}\) -rectifiable set. With small changes, our results are valid also in the case of multiple control input.     

The theme of a vanishing period

Consider a multivalued formal function of the type 1 $$\begin{aligned} \varphi (s) : = \sum _{j=0}^k\,c_j(s).s^{\lambda + m_j}.(\mathrm{Log}\,s)^j, \end{aligned}$$ where \(\lambda \) is a positive rational number, \(c_j\) is in \({{\mathrm{\mathbb {C}}}}[[s]]\) and \(m_j \in \mathbb {N}\) for \(j \in [0,k-1]\) . The theme associated with such a \(\varphi \) is the “minimal filtered integral equation” satisfied by \(\varphi \) , in a sense which is made precise in this article. We study such objects and show that their isomorphism classes may be characterized by a finite set of complex numbers, when we assume the Bernstein polynomial of \(\varphi \) to be fixed. For a given \(\lambda \) , to fix the Bernstein polynomial is equivalent to fix a finite set of integers associated with the logarithm of the monodromy in the geometric situation described below. Our aim is to construct some analytic invariants, for instance in the following situation, let \(f : X \rightarrow D\) be a proper holomorphic function defined on a complex manifold \(X\) with values in a disc \(D\) . We assume that the only critical value is \(0 \in D\) and we consider this situation as a degenerating family of compact complex manifolds to a singular compact complex space \(f^{-1}(0)\) . To a smooth \((p+1)\) -form \(\omega \) on \(X\) such that \(\mathrm{d}\omega = 0 = \mathrm{d}f \wedge \omega \) and to a vanishing \(p\) -cycle \(\gamma \) chosen in the generic fiber \(f^{-1}(s_0), s_0 \in D \setminus \{0\}\) , we associated a “vanishing period” \(F_{\gamma }(s) : = \int _{\gamma _s} \omega \big /\mathrm{d}f \) which has an asymptotic expansion at \(0\) of the form \((1)\) above, when \(\gamma \) is chosen in the spectral subspace of \(H_p(f^{-1}(s_0), {{\mathrm{\mathbb {C}}}})\) for the eigenvalue \(\mathrm{e}^{2i\pi .\lambda }\) of the monodromy of \(f\) . Here \((\gamma _s)_{s \in D^*}\) is the horizontal multivalued family of \(p\) -cycles in the fibers of \(f\) obtained from the choice of \(\gamma \) . The aim of this article was to study the module generated by such a \(\varphi \) over the algebra \(\tilde{\mathcal {A}}\) , which is the \(b\) -completion of the algebra \(\mathcal {A}\) generated by the operators \(\mathrm{a} : = \times s\) and \(\mathrm{b} : = \int _{0}^{s}\) .     

The Cauchy–Riemann equations in the unit ball of l^{2}

We study the local exactness of the \(\overline{\partial }\) operator in the Hilbert space \(l^2\) for a particular class of \((0,1)\) -forms \(\omega \) of the type \(\omega (z) = \sum _i z_i\omega ^i(z) d\overline{z}_i\) , \(z = (z_i)\) in \(l^2\) . We suppose each function \(\omega ^i\) of class \(C^\infty \) in the closed unit ball of \(l^2\) , of the form \(\omega ^i(z) = \sum _k \omega ^i_k\left( z^k\right) \) , where \(\mathbf N = \bigcup I_k\) is a partition of \(\mathbf N\) , \((\) card \(I_k < +\infty )\) and \(z^k\) is the projection of \(z\) on \(\mathbf C^{I_k}\) . We establish sufficient conditions for exactness of \(\omega \) related to the expansion in Fourier series of the functions \(\omega ^i_k\) .     

Sur un problème de capitulation du corps ℚ\sqrt {p_1 p_2 } , i dont le 2-groupe de classes est élémentaire

Let p ₁ ≡ p ₂ ≡ 1 (mod 8) be primes such that \(\left( {\tfrac{{p_1 }} {{p_2 }}} \right) = - 1\) and \(\left( {\tfrac{2} {{a + b}}} \right) = - 1\) , where p ₁ p ₂ = a ²+b ². Let \(i = \sqrt { - 1} \) , d = p ₁ p ₂, \(\Bbbk = \mathbb{Q}(\sqrt {d,} i),\Bbbk _2^{(1)} \) be the Hilbert 2-class field and \(\Bbbk ^{(*)} = \mathbb{Q}(\sqrt {p_1 } ,\sqrt {p_2 } ,i)\) be the genus field of \(\Bbbk \) . The 2-part \(C_{\Bbbk ,2} \) of the class group of \(\Bbbk \) is of type (2, 2, 2), so \(\Bbbk _2^{(1)} \) contains seven unramified quadratic extensions \(\mathbb{K}_j /\Bbbk \) and seven unramified biquadratic extensions \(\mathbb{L}_j /\Bbbk \) . Our goal is to determine the fourteen extensions, the group \(C_{\Bbbk ,2} \) and to study the capitulation problem of the 2-classes of \(\Bbbk \) .     

Efficiently Hex-Meshing Things with Topology

A topological quadrilateral mesh \(Q\) of a connected surface in \(\mathbb {R}^3\) can be extended to a topological hexahedral mesh of the interior domain \(\varOmega \) if and only if \(Q\) has an even number of quadrilaterals and no odd cycle in \(Q\) bounds a surface inside \(\varOmega \) . Moreover, if such a mesh exists, the required number of hexahedra is within a constant factor of the minimum number of tetrahedra in a triangulation of \(\varOmega \) that respects \(Q\) . Finally, if \(Q\) is given as a polyhedron in \(\mathbb {R}^3\) with quadrilateral facets, a topological hexahedral mesh of the polyhedron can be constructed in polynomial time if such a mesh exists. All our results extend to domains with disconnected boundaries. Our results naturally generalize results of Thurston, Mitchell, and Eppstein for genus-zero and bipartite meshes, for which the odd-cycle criterion is trivial.     

Salem numbers in dynamics on Kähler threefolds and complex tori

Let \(X\) be a compact Kähler manifold of dimension \(k\!\le \! 4\) and \(f{:}X\!\rightarrow \! X\) a pseudo-automorphism. If the first dynamical degree \(\lambda _1(f)\) is a Salem number, we show that either \(\lambda _1(f)=\lambda _{k-1}(f)\) or \(\lambda _1(f)^2=\lambda _{k-2}(f)\) . In particular, if \({\dim }(X)=3\) then \(\lambda _1(f)=\lambda _2(f)\) . We use this to show that if \(X\) is a complex 3-torus and \(f\) is an automorphism of \(X\) with \(\lambda _1(f)>1\) , then \(f\) has a non-trivial equivariant holomorphic fibration if and only if \(\lambda _1(f)\) is a Salem number. If \(X\) is a complex 3-torus having an automorphism \(f\) with \(\lambda _1(f)=\lambda _2(f)>1\) but is not a Salem number, then the Picard number of \(X\) must be 0, 3 or 9, and all these cases can be realized.     

Identification of a convolution kernel in a control problem for the heat equation with a boundary memory term

We consider the evolution of the temperature \(u\) in a material with thermal memory characterized by a time-dependent convolution kernel \(h\) . The material occupies a bounded region \(\Omega \) with a feedback device controlling the external temperature located on the boundary \(\Gamma \) . Assuming both \(u\) and \(h\) unknown, we formulate an inverse control problem for an integrodifferential equation with a nonlinear and nonlocal boundary condition. Existence and uniqueness results of a solution to the inverse problem are proved.     

The \bar{\partial }-Equation on an Annulus Between Two Strictly q-Convex Domains with Smooth Boundaries

In this paper, we study the global boundary regularity of the \(\bar{\partial }\) - equation on an annulus domain \(\Omega \) between two strictly \(q\) -convex domains with smooth boundaries in \(\mathbb{C }^n\) for some bidegree. To this finish, we first show that the \(\bar{\partial }\) -operator has closed range on \(L^{2}_{r, s}(\Omega )\) and the \(\bar{\partial }\) -Neumann operator exists and is compact on \(L^{2}_{r,s}(\Omega )\) for all \(r\ge 0\) , \(q\le s\le n-q- 1\) . We also prove that the \(\bar{\partial }\) -Neumann operator and the Bergman projection operator are continuous on the Sobolev space \(W^{k}_{r,s}(\Omega )\) , \(k\ge 0\) , \(r\ge 0\) , and \(q\le s\le n-q-1\) . Consequently, the \(L^{2}\) -existence theorem for the \(\bar{\partial }\) -equation on such domain is established. As an application, we obtain a global solution for the \(\bar{\partial }\) equation with Hölder and \(L^p\) -estimates on strictly \(q\) -concave domain with smooth \(\mathcal C ^2\) boundary in \(\mathbb{C }^n\) , by using the local solutions and applying the pushing out method of Kerzman (Commun Pure Appl Math 24:301–380, 1971).