Preemptive Semi-online Algorithms for Parallel Machine Scheduling with Known Total Size

This paper investigates preemptive semi-online scheduling problems on m identical parallel machines, where the total size of all jobs is known in advance. The goal is to minimize the maximum machine completion time or maximize the minimum machine completion time. For the first objective, we present an optimal semi-online algorithm with competitive ratio 1. For the second objective, we show that the competitive ratio of any semi-online algorithm is at least （2m-3）/（m-1） for any m〉2 and present optimal semi-online algorithms for m = 2, 3.     

Onp-absolutely summing constants of banach spaces

Given 1≦p<∞ and a real Banach spaceX, we define thep-absolutely summing constantμ _p(X) as inf{Σ _i ^=1/m |x*(x _i)|^p p Σ _i ^=1/m ‖x _i‖^p p]¹ p}, where the supremum ranges over {x*∈X*; ‖x*‖≤1} and the infimum is taken over all sets {x ₁,x ₂, …,x _m} ⊂X such that Σ _i ^=1/m ‖x _i‖>0. It follows immediately from [2] thatμ _p(X)>0 if and only ifX is finite dimensional. In this paper we find the exact values ofμ _p(X) for various spaces, and obtain some asymptotic estimates ofμ _p(X) for general finite dimensional Banach spaces. This is a part of the author’s Ph.D. Thesis prepared at the Hebrew University of Jerusalem, under the supervision of Prof. A. Dvoretzky and Prof. J. Lindenstrauss.     

Strongly almost convergent generalized difference sequences associated with multiplier sequences

Let Λ = (λ _k ) be a sequence of non-zero complex numbers. In this paper we introduce the strongly almost convergent generalized difference sequence spaces associated with multiplier sequences i.e. w ₀[A,Δ ^m ,Λ,p], w ₁[A,Λ ^m ,Λ,p], w _∞[A,Δ ^m ,Λ,p] and study their different properties. We also introduce Δ _Λ ^m -statistically convergent sequences and give some inclusion relations between w ₁[Δ ^m ,λ,p] convergence and Δ _Λ ^m -statistical convergence. Communicated by Pavel Kostyrko     

Fast algorithms for determining the linear complexities of sequences over GF(pm) with the period 3n

In this paper, for the the primes p such that 3 is a divisor of p − 1, we prove a result which reduces the computation of the linear complexity of a sequence over GF(p ^m) (any positive integer m) with the period 3n (n and p ^m − 1 are coprime) to the computation of the linear complexities of three sequences with the period n. Combined with some known algorithms such as generalized Games-Chan algorithm, Berlekamp-Massey algorithm and Xiao-Wei-Lam-Imamura algorithm, we can determine the linear complexity of any sequence over GF(p ^m) with the period 3n (n and p ^m − 1 are coprime) more efficiently.     

A Criterion for Elliptic Curves with Second Lowest 2-Power in L（1）（Ⅱ）

Let D = p1p2 …pm, where p1,p2, ……,pm are distinct rational primes with p1 ≡p2 ≡3（mod 8）, pi =1（mod 8）（3 ≤ i ≤ m）, and m is any positive integer. In this paper, we give a simple combinatorial criterion for the value of the complex L-function of the congruent elliptic curve ED2 ： y^2 = x^3- D^2x at s = 1, divided by the period ω defined below, to be exactly divisible by 2^2m-2, the second lowest 2-power with respect to the number of the Gaussian prime factors of D. As a corollary, we obtain a new series of non-congruent numbers whose prime factors can be arbitrarily many. Our result is in accord with the predictions of the conjecture of Birch and Swinnerton-Dyer.     

On the cohomology of orbit space of free ℤ<Subscript><Emphasis Type="Italic">p</Emphasis></Subscript>-actions on lens spaces

Let G = ℤ _p , p an odd prime, act freely on a finite-dimensional CW-complex X with mod p cohomology isomorphic to that of a lens space L ^2m−1(p; q ₁, …, q _m ). In this paper, we determine the mod p cohomology ring of the orbit space X/G, when p ² ∤ m.     

On some generalized difference paranormed sequence spaces associated with multiplier sequence defined by modulus function

In this article we introduce the paranormed sequence spaces(f,Λ,△m,p),c0(f,Λ,△m,p) and ■∞(f,Λ,△m,p),associated with the multiplier sequence Λ =(λk),defined by a modulus function f.We study their different properties like solidness,symmetricity,completeness etc.and prove some inclusion results.     

Modes and moments of unimodal distributions

Summary For a unimodal distribution relations of its modea with its absolute momentβ _p and central absolute momentγ _p of orderp are considered. The best constantA _p andB _p are given for the inequalities |a|≦A _p β _p ^1/p (p>0) and |a−m|≦B _p γ _p ^1/p (p≧1) wherem is the mean. the results follow from discussion of more general moments.     

Preemptive scheduling with rejection

 We consider the problem of preemptively scheduling a set of n jobs on m (identical, uniformly related, or unrelated) parallel machines. The scheduler may reject a subset of the jobs and thereby incur job-dependent penalties for each rejected job, and he must construct a schedule for the remaining jobs so as to optimize the preemptive makespan on the m machines plus the sum of the penalties of the jobs rejected. We provide a complete classification of these scheduling problems with respect to complexity and approximability. Our main results are on the variant with an arbitrary number of unrelated machines. This variant is APX-hard, and we design a 1.58-approximation algorithm for it. All other considered variants are weakly -hard, and we provide fully polynomial time approximation schemes for them. Finally, we argue that our results for unrelated machines can be carried over to the corresponding preemptive open shop scheduling problem with rejection. Received: October 30, 2000 / Accepted: September 26, 2001 Published online: September 5, 2002 Key words. scheduling – preemption – approximation algorithm – worst case ratio – computational complexity – in-approximability Supported in part by the EU Thematic Network APPOL, Approximation and Online Algorithms, IST-1999-14084 Supported by the START program Y43-MAT of the Austrian Ministry of Science.     

The Permutations 123p 4…p m and 321p 4…p m are Wilf-Equivalent

Write p ₁, p ₂…p _m for the permutation matrix δ _{pi, j} . Let S _n (M) be the set of n×n permutation matrices which do not contain the m×m permutation matrix M as a submatrix. In [7] Simion and Schmidt show bijectively that |S _n (123) |=|S _n (213) |. In [9] this was generalised to a bijection between S _n (12 p ₃…p _m ) and S _n (21 p ₃…p _m ). In the present paper we obtain a bijection between S _n (123 p ₄…p _m ) and S _n (321 p ₄…p _m ). Revised: March 24, 1999     

Finiteness conditions on subgroups of profinite p-Poincaré duality groups

For a prime number p let G be a profinite p-PD _n group with a closed normal subgroup N such that G/N is a profinite p-PD _m group and that H _i (V, $ \mathbb{F} $ \mathbb{F} _p ) is finite for every open subgroup V of N and all i ≤ [n/2]. Generalising [12, Thm. 3.7.4] we show that m ≤ n and N is a profinite p-PD _{n − m} group. In case that G is a pro-p PD _n group of Euler characteristic 0 with a closed normal subgroup N of type FP _{[n−1 / 2]} such that G/N is soluble-by-finite pro-p group of finite rank, we show that N is a pro-p PD _{n − m} group, where m = vcd _p (G/N). As a corollary we obtain that a pro-p PD ₃ group with infinite abelianization is either soluble or contains a free nonprocyclic pro-p subgroup.     

On a Delay Reaction-Diffusion Difference Equation of Neutral Type

In this paper, we first consider a delay difference equation of neutral type of the form: Δ(y _n + py _n−k + q _n y _n−l = 0 for n∈ℤ⁺(0) (1*) and give a different condition from that of Yu and Wang (Funkcial Ekvac, 1994, 37(2): 241–248) to guarantee that every non-oscillatory solution of (1*) with p = 1 tends to zero as n→∞. Moreover, we consider a delay reaction-diffusion difference equation of neutral type of the form: Δ₁(u _n,m + pu _n−k,m ) + q _n,m u _n−l,m = a ²Δ² ₂ u _{n +1, m−1} for (n,m) ∈ℤ⁺ (0) ×Ω, (2*) study various cases of p in the neutral term and obtain that if p≥−1 then every non-oscillatory solution of (2*) tends uniformly in m∈Ω to zero as n→∞; if p = −1 then every solution of (2*) oscillates and if p < −1 then every non-oscillatory solution of (2*) goes uniformly in m∈Ω to infinity or minus infinity as n→∞ under some hypotheses. Received July 14, 1999, Revised August 10, 2000, Accepted September 30, 2000     

On the Erlang Loss Model with Time Dependent Input

We consider the M(t)/M(t)/m/m queue, where the arrival rate λ(t) and service rate μ(t) are arbitrary (smooth) functions of time. Letting p_n(t) be the probability that n servers are occupied at time t (0≤ n≤ m, t > 0), we study this distribution asymptotically, for m→∞ with a comparably large arrival rate λ(t) = O(m) (with μ(t) = O(1)). We use singular perturbation techniques to solve the forward equation for p_n(t) asymptotically. Particular attention is paid to computing the mean number of occupied servers and the blocking probability p_m(t). The analysis involves several different space-time ranges, as well as different initial conditions (we assume that at t = 0 exactly n₀ servers are occupied, 0≤ n₀≤ m). Numerical studies back up the asymptotic analysis. AMS subject classification: 60K25,34E10 Supported in part by NSF grants DMS-99-71656 and DMS-02-02815     

The nearness problems for symmetric centrosymmetric with a special submatrix constraint

We say that X=[x_ij]_i,j=1ⁿX=[x_{ij}]_{i,j=1}^n is symmetric centrosymmetric if x _ij  = x _ji and x _{n − j + 1,n − i + 1}, 1 ≤ i,j ≤ n. In this paper we present an efficient algorithm for minimizing ||AXA ^T  − B|| where ||·|| is the Frobenius norm, A ∈ ℝ ^m×n , B ∈ ℝ ^m×m and X ∈ ℝ ^n×n is symmetric centrosymmetric with a specified central submatrix [x _ij ] _{p ≤ i,j ≤ n − p} . Our algorithm produces a suitable X such that AXA ^T  = B in finitely many steps, if such an X exists. We show that the algorithm is stable any case, and we give results of numerical experiments that support this claim.     

On zeta functions and families of Siegel modular forms

Let p be a prime, and let G = \textS\textp_g( \mathbbZ ) \Gamma = {\text{S}}{{\text{p}}_g}\left( \mathbb{Z} \right) be the Siegel modular group of genus g. This paper is concerned with p-adic families of zeta functions and L-functions of Siegel modular forms; the latter are described in terms of motivic L-functions attached to Sp _g ; their analytic properties are given. Critical values for the spinor L-functions are discussed in relation to p-adic constructions. Rankin’s lemma of higher genus is established. A general conjecture on a lifting of modular forms from GSp_2m   × GSp_2m to GSp_4m (of genus g = 4 m) is formulated. Constructions of p-adic families of Siegel modular forms are given using Ikeda–Miyawaki constructions.     

Description of polygonal regions by polynomials of bounded degree

We show that every (possibly unbounded) convex polygon P in \mathbbR²{\mathbb{R}^2} with m edges can be represented by inequalities p ₁ ≥ 0, . . ., p _n ≥ 0, where the p _i ’s are products of at most k affine functions each vanishing on an edge of P and n = n(m, k) satisfies s(m, k) ￡ n(m, k) ￡ (1+e_m) s(m, k){s(m, k) \leq n(m, k) \leq (1+\varepsilon_m) s(m, k)} with s(m,k) ≔ max {m/k, log₂ m} and e_m ? 0{\varepsilon_m \rightarrow 0} as m ? ￥{m \rightarrow \infty}. This choice of n is asymptotically best possible. An analogous result on representing the interior of P in the form p ₁ > 0, . . ., p _n >  0 is also given. For k ≤ m/log₂ m these statements remain valid for representations with arbitrary polynomials of degree not exceeding k.     

Competitive online scheduling of perfectly malleable jobs with setup times

We study how to efficiently schedule online perfectly malleable parallel jobs with arbitrary arrival times on m ? 2 processors. We take into account both the linear speedup of such jobs and their setup time, i.e., the time to create, dispatch, and destroy multiple processes. Specifically, we define the execution time of a job with length p_j running on k_j processors to be p_j/k_j + (k_j − 1)c, where c > 0 is a constant setup time associated with each processor that is used to parallelize the computation. This formulation accurately models data parallelism in scientific computations and realistically asserts a relationship between job length and the maximum useful degree of parallelism. When the goal is to minimize makespan, we show that the online algorithm that simply assigns k_j so that the execution time of each job is minimized and starts jobs as early as possible has competitive ratio 4(m − 1)/m for even m ? 2 and 4m/(m + 1) for odd m ? 3. This algorithm is much simpler than previous offline algorithms for scheduling malleable jobs that require more than a constant number of passes through the job list.     

Positivity Preserving Hadamard Matrix Functions

For every positive real number p that lies between even integers 2(m − 2) and 2(m − 1) we demonstrate a matrix A = [a_ij] of order 2m such that A is positive definite but the matrix with entries |a_ij|^p is not.     

Subspaces ofl p N of small codimension

In this paper the structure of subspaces and quotients ofl _p ^N of dimension very close toN is studied, for 1≤p≤∞. In particular, the maximal dimensionk=k(p, m, N) so that an arbitrarym-dimensional subspaceX ofl _p ^N contains a good copy ofl _p ^k , is investigated form=N−o(N). In several cases the obtained results are sharp.     

Extinction and Positivity for a Doubly Nonlinear Degenerate Parabolic Equation

The aims of this paper are to discuss the extinction and positivity for the solution of the initial boundary value problem and Cauchy problem of ut = div（[↓△u^m｜p-2↓△u^m）. It is proved that the weak solution will be extinct for 1 〈 p ≤ 1 ＋ 1/m and will be positive for p 〉 1 ＋ 1/m for large t, where m 〉 0.