A unified analysis for the single-machine scheduling problem with controllable and non-controllable variable job processing times

We present a unified analysis for single-machine scheduling problems in which the actual job processing times are controlled by either a linear or a convex resource allocation function and also vary concurrently depending on either the job’s position in the sequence and/or on the total processing time of the already processed jobs. We show that the problem is solvable in O(nlogn)$O(n\log n)$ time by using a weight-matching approach when a convex resource allocation function is in effect. In the case of a linear resource allocation function, we show that the problem can be solved in O(n³)$O(n^3)$ time by using an assignment formulation. Our approach generalizes the solution approach for the corresponding problems with controllable job processing times to incorporate the variability of the job processing times stemming from either the job’s position in the sequence and/or the total processing time of the already processed jobs.     

Due dates assignment and JIT scheduling with equal-size jobs

This paper deals with due date assignment and just-in-time scheduling for single machine and parallel machine problems with equal-size jobs where the objective is to minimize the total weighted earliness–tardiness and due date cost. These two problems, but with a common due date to be calculated, were shown to be polynomially solvable in O(n⁴)$O(n^4)$ time. We first show that this complexity can be reduced to O(n³)$O(n^3)$ by modeling the single machine scheduling problem as an assignment problem without necessary due date enumeration. We next prove that the general case with identical parallel machines and a given set of assignable due dates where the cardinality of this set is bounded by a constant number is still polynomially solvable.     

Sur la répartition des puissances modulo 1

For almost all x>1$x>1$, (xⁿ)$(x^n)$(n=1,2,…)$(n=1,2,\dots )$ is equidistributed modulo 1, a classical result. What can be said on the exceptional set? It has Hausdorff dimension one. Much more: given an (b_n)$(b_n)$ in [0,1[$[0,1[$ and ε>0$\epsilon >0$, the x  -set such that |xⁿ−b_n|<ε$|x^n-b_n|<\epsilon$ modulo 1 for n   large enough has dimension 1. However, its intersection with an interval [1,X]$[1,X]$ has a dimension <1, depending on ε and X. Some results are given and a question is proposed.     

An improvement for the Trudinger–Moser inequality and applications

In line with the Concentration–Compactness Principle due to P.-L. Lions [19], we study the lack of compactness of Sobolev embedding of W^1,n(Rⁿ)$W^{1,n}({\mathbb{R}}^n)$, n?2$n?2$, into the Orlicz space _LΦα$L_{{\Phi }_{\alpha }}$ determined by the Young function _Φα(s)${\Phi }_{\alpha }(s)$ behaving like e^{α|s|n/(n−1)}−1$e^{\alpha {|s|}^{n/(n-1)}}-1$ as |s|→+∞$|s|\to +\infty$. In the light of this result we also study existence of ground state solutions for a class of quasilinear elliptic problems involving critical growth of the Trudinger–Moser type in the whole space Rⁿ${\mathbb{R}}^n$.     

A note on the single machine scheduling to minimize the number of tardy jobs with deadlines

It is known that the single machine scheduling problem of minimizing the number of tardy jobs is polynomially solvable. However, it becomes NP-hard if each job has a deadline. Recently, Huo et al. solved some special cases by a backwards scheduling approach. In this note we present a dual approach—forwards greedy algorithms which may have better running time. For example, in the case that the due dates, deadlines, and processing times are agreeable, the running time of the backwards scheduling algorithm is O(n²)$O(n^2)$, while that of the forwards algorithm is O(nlogn)$O(n\log n)$.     

The Dirichlet problem for the fractional Laplacian: Regularity up to the boundary

We study the regularity up to the boundary of solutions to the Dirichlet problem for the fractional Laplacian. We prove that if u   is a solution of (−Δ)^su=g${(-\mathrm{\Delta })}^{s}u=g$ in Ω  , u≡0$u\equiv 0$ in Rⁿ\Ω${\mathbb{R}}^n\backslash \Omega$, for some s∈(0,1)$s\in (0,1)$ and g∈L^∞(Ω)$g\in L^{\infty }(\Omega )$, then u   is C^s(Rⁿ)$C^s({\mathbb{R}}^n)$ and u/δ^s_|Ω$u/{\delta }^s{|}_{\Omega }$ is C^α$C^{\alpha }$ up to the boundary ∂Ω   for some α∈(0,1)$\alpha \in (0,1)$, where δ(x)=dist(x,∂Ω)$\delta (x)=\mathrm{dist}(x,\partial \Omega )$. For this, we develop a fractional analog of the Krylov boundary Harnack method.     

Characterizing graphic matroids by a system of linear equations

Given a rank-r   binary matroid we construct a system of O(r³)$O(r^3)$ linear equations in O(r²)$O(r^2)$ variables that has a solution over GF(2)$\mathrm{GF}(2)$ if and only if the matroid is graphic.     

The topological structure of fuzzy sets with sendograph metric

For a non-degenerate convex subset Y of the n  -dimensional Euclidean space Rⁿ${\mathbb{R}}^n$, let F(Y)$\mathbb{F}(Y)$ be the family of all fuzzy sets of Rⁿ${\mathbb{R}}^n$ which are upper semicontinuous, fuzzy convex and normal with compact supports contained in Y  . We show that the space F(Y)$\mathbb{F}(Y)$ with the topology of sendograph metric is homeomorphic to the separable Hilbert space ?²${?}^2$ if Y   is compact; and the space F(Rⁿ)$\mathbb{F}({\mathbb{R}}^n)$ is also homeomorphic to ?²${?}^2$.     

Gaussian bounds for higher-order elliptic differential operators with Kato type potentials

Let P(D)$P(D)$ be a nonnegative homogeneous elliptic operator of order 2m   with real constant coefficients on Rⁿ${\mathbb{R}}^n$ and V   be a suitable real measurable function. In this paper, we are mainly devoted to establish the Gaussian upper bound for Schrödinger type semigroup e^−tH$e^{-tH}$ generated by H=P(D)+V$H=P(D)+V$ with Kato type perturbing potential V  , which naturally generalizes the classical result for Schrödinger semigroup e^−t(Δ+V)$e^{-t(\mathrm{\Delta }+V)}$ as V∈_K2(Rⁿ)$V\in K_2({\mathbb{R}}^n)$, the famous Kato potential class. Our proof significantly depends on the analyticity of the free semigroup e^−tP(D)$e^{-tP(D)}$ on L¹(Rⁿ)$L^1({\mathbb{R}}^n)$. As a consequence of the Gaussian upper bound, the L^p$L^p$-spectral independence of H is concluded.     

Nonuniform continuity of the solution map to the two component Camassa–Holm system

We prove that the solution map of the two-component Camassa–Holm system is not uniformly continuous as a map from a bounded subset of the Sobolev space H^s(T)×H^r(T)$H^s(\mathbb{T})\times H^r(\mathbb{T})$ to C([0,1],H^s(T)×H^r(T))$C([0,1],H^s(\mathbb{T})\times H^r(\mathbb{T}))$ when s?1$s?1$ and r?0$r?0$. We also demonstrate the nonuniform continuous property in the continuous function space C¹(T)×C¹(T)$C^1(\mathbb{T})\times C^1(\mathbb{T})$.     

p-Laplacian boundary value problems on exterior regions

This paper treats some variational principles for solutions of inhomogeneous p  -Laplacian boundary value problems on exterior regions U?R^N$U?{\mathbb{R}}^N$ with dimension N?3$N?3$. Existence-uniqueness results when p∈(1,N)$p\in (1,N)$ are provided in a space E^1,p(U)$E^{1,p}(U)$ of functions that contains W^1,p(U)$W^{1,p}(U)$. Functions in E^1,p(U)$E^{1,p}(U)$ are required to decay at infinity in a measure theoretic sense. Various properties of this space are derived, including results about equivalent norms, traces and an L^p$L^p$-imbedding theorem. Also an existence result for a general variational problem of this type is obtained.