Scheduling Malleable Tasks on Parallel Processors to Minimize the Makespan

The problem of optimal scheduling n tasks in a parallel processor system is studied. The tasks are malleable, i.e., a task may be executed by several processors simultaneously and the processing speed of a task is a nonlinear function of the number of processors allocated to it. The total number of processors is m and it is an upper bound on the number of processors that can be used by all the tasks simultaneously. It is assumed that the number of processors is sufficient to process all the tasks simultaneously, i.e. n≤m. The objective is to find a task schedule and a processor allocation such that the overall task completion time, i.e. the makespan, is minimized. The problem is motivated by real-life applications of parallel computer systems in scientific computing of highly parallelizable tasks. An O(n) algorithm is presented to solve this problem when all the processing speed functions are convex. If these functions are all concave and the number of tasks is a constant, the problem can be solved in polynomial time. A relaxed problem, in which the number of processors allocated to each task is not required to be integer, can be solved in O(nmax {m,nlog ² m}) time. It is proved that the minimum makespan values for the original and relaxed problems coincide. For n=2 or n=3, an optimal solution for the relaxed problem can be converted into an optimal solution for the original problem in a constant time.     

Twisted inner products and contraction inequalities on spaces of contravariant and covariant tensors

Given positive integers n and p, and a complex finite dimensional vector space V, we let S_n,p(V) denote the set of all functions from V×V×?×V-(n+p copies) to C that are linear and symmetric in the first n positions, and conjugate linear symmetric in the last p positions. Letting κ=min{n,p} we introduce twisted inner products, [·,·]_s,t,1?s,t?κ, on S_n,p(V), and prove the monotonicity condition [F,F]_s,t?[F,F]_u,v is satisfied when s?u?κ,t?v?κ, and F∈S_n,p(V). Using the monotonicity condition, and the Cauchy-Schwartz inequality, we obtain as corollaries many known inequalities involving norms of symmetric multilinear functions, which in turn imply known inequalities involving permanents of positive semidefinite Hermitian matrices. New tensor and permanental inequalities are also presented. Applications to partial differential equations are indicated.     

A combinatorial problem involving graphs and matrices

In this paper we discuss a combinatorial problem involving graphs and matrices. Our problem is a matrix analogue of the classical problem of finding a system of distinct representatives (transversal) of a family of sets and relates closely to an extremal problem involving 1-factors and a long standing conjecture in the dimension theory of partially ordered sets. For an integer n ?1, let n denote the n element set {1,2,3,…, n}. Then let A be a k×t matrix. We say that A satisfies property P(n, k) when the following condition is satisfied: For every k-taple (x₁,x₂,…,x_k?n^k there exist k distinct integers j₁,j₂,…,j_k so that x_i= a_ii for i= 1,2,…,k. The minimum value of t for which there exists a k × t matrix A satisfying property P(n,k) is denoted by f(n,k). For each k?1 and n sufficiently large, we give an explicit formula for f(n, k): for each n?1 and k sufficiently large, we use probabilistic methods to provide inequalities for f(n,k).     

Fast Deterministic Processor Allocation

Interval allocation has been suggested as a possible formalization for the PRAM of the (vaguely defined) processor allocation problem, which is of fundamental importance in parallel computing. The interval allocation problem is, given n nonnegative integers x₁, . . ., x_n, to allocate n nonoverlapping subarrays of sizes x₁, . . ., x_n from within a base array of O(Σⁿ_j=1x_j) cells. We show that interval allocation problems of size n can be solved in O((log log n)³) time with optimal speedup on a deterministic CRCW PRAM. In addition to a general solution to the processor allocation problem, this implies an improved deterministic algorithm for the problem of approximate summation. For both interval allocation and approximate summation, the fastest previous deterministic algorithms have running times of Θ(log n/log log n). We describe an application to the problem of computing the connected components of an undirected graph. Finally we show that there is a nonuniform deterministic algorithm that solves interval allocation problems of size n in O(log log n) time with optimal speedup.     

Cyclic even cycle systems of the complete graph

In this article, it is proved that for each even integer m?4 and each admissible value n with n>2m, there exists a cyclic m‐cycle system of K_n, which almost resolves the existence problem for cyclic m‐cycle systems of K_n with m even. © 2011 Wiley Periodicals, Inc. J Combin Designs 20:23–39, 2012     

Solution of the wave equation in Rn + 1 with data on a characteristic cone

A unified treatment of the problem is presented for both odd and even space dimensions. In contrast to previous results for odd n, when the space dimension is even, there is no general existence although the uniqueness holds. A necessary and sufficient condition for admissible data is given. Of independent interest are several versions of the “Plancherel theorem” of the Radon transform, in the space L₂¹(Rⁿ) of all functions whose gradients are square integrable.     

Resonances and standing waves

Recent investigations on aperiodic waves, which are generated by time-harmonic forces in waveguides, indicate a close relationship between resonances and certain time-harmonic solutions of homogeneous boundary value problems for the wave equation (“standing waves”). This paper is motivated by the observation that, in all known cases, standing waves are connected with resonances if and only if they are subject to suitable asymptotic restrictions as |x| → ∞. These asymptotic properties are used to introduce a class of “admissible” standing waves. We prove that admissible standing waves do not exist in a certain class of local perturbations Ω of the n-dimensional domain Ω₀ bounded by the hyperplanes x_n = 0 and x_n = π. This extends a result of M. Faulhaber on the absence of eigenvalues. As we shall show in a subsequent paper, absence of admissible standing waves implies absence of resonances.     

Approximability results for the resource-constrained project scheduling problem with a single type of resources

In this paper, we consider the well-known resource-constrained project scheduling problem. We give some arguments that already a special case of this problem with a single type of resources is not approximable in polynomial time with an approximation ratio bounded by a constant. We prove that there exist instances for which the optimal makespan values for the non-preemptive and the preemptive problems have a ratio of O(logn), where n is the number of jobs. This means that there exist instances for which the lower bound of Mingozzi et al. has a bad relative error of O(logn), and the calculation of this bound is an NP-hard problem. In addition, we give a proof that there exists a type of instances for which known approximation algorithms with polynomial time complexity have an approximation ratio of at least equal to $O(\sqrt{n})$ , and known lower bounds have a relative error of at least equal to O(logn). This type of instances corresponds to the single machine parallel-batch scheduling problem 1|p?batch,b=∞|C _max.     

Multivariate stress scenarios and solvency

We show how the probabilistic concepts of half-space trimming and depth may be used to define convex scenario sets Q_α for stress testing the risk factors that affect the solvency of an insurance company over a prescribed time period. By choosing the scenario in Q_α which minimizes net asset value at the end of the time period, we propose the idea of the least solvent likely event (LSLE) as a solution to the forward stress testing problem. By considering the support function of the convex scenario set Q_α, we establish theoretical properties of the LSLE when financial risk factors can be assumed to have a linear effect on the net assets of an insurer. In particular, we show that the LSLE may be interpreted as a scenario causing a loss equivalent to the Value-at-Risk (VaR) at confidence level α, provided the α-quantile is a subadditive risk measure on linear combinations of the risk factors. In this case, we also show that the LSLE has an interpretation as a per-unit allocation of capital to the underlying risk factors when the overall capital is determined according to the VaR. These insights allow us to define alternative scenario sets that relate in similar ways to coherent measures, such as expected shortfall. We also introduce the most likely ruin event (MLRE) as a solution to the problem of reverse stress testing.     

On orthogonal matrices with constant diagonal

In connection with the problem of finding the best projections of k-dimensional spaces embedded in n-dimensional spaces Hermann König asked: Given m∈$\text{R}$ and n∈$\text{N}$, are there n×n matrices C=(c_ij), i, j=1,…,n, such that c_ii=m for all i, |c_ij|=1 for i≠j, and C²=(m²+n?1)I_n? König was especially interested in symmetric C, and we find some families of matrices satisfying this condition. We also find some families of matrices satisfying the less restrictive condition CC^T=(m²+n?1)I_n.     

A decision process over variables and their number: Two-phase optimality conditions

The paper considers the following unconstrained optimization problem: minimize f_n(x_n, n) = g_n(x_n) + h(n), where g_n(x_n) = α?_{i = 0}^n?1 ∫ _xi^{x_i = 1} [ ∫ _x^{x_i + 1}b (t) d(t)]d x, over both the variables x₁, x₂, …, x_n?1, and their number n, when x₀, x_n ≡ X are known boundary conditions, and h (n) is increasing, unbounded and weakly convex. Examples that demonstrate the practical usefulness of this decision process are given, and a two-phase approach for solving it, namely, minimize first over the arguments for a fixed n, and then over n, is suggested. Simple conditions, for a general g_n(x_n), under which phase II can be carried out by a finite search are stated, and then the question: “Under what circumstances does the search for the optimal n reduce to a simple condition?” is posed. Kuhn-Tucker type two-phase optimality conditions that answer this question are established, and moreover, specifications on the dominating single variable function b (x) for which the conditions hold are set forth.     

Partitions and sums of integers with repetition

A partition of N is called “admissible” provided some cell has arbitrarily long arithmetic progressions of even integers in a fixed increment. The principal result is that the statement “Whenever {A_i}_{i < r} is an admissible partition of N, there are some i < r and some sequence 〈x_n〉_{n < ω} of distinct members of N such that x_n + x_m?A_i whenever {m, n} ? ω″ is true when r = 2 and false when r ? 3.     

Markov measures and extended zeta functions

In this paper we study a family of representations of the Cuntz algebras O _p where p is a prime. These algebras are built on generators and relations. They are C ^?-algebras and their representations are a part of non-commutative harmonic analysis. Starting with specific generators and relations we pass to an ambient C ^?-algebra, for example in one of the Cuntz-algebras. Our representations are motivated by the study of frequency bands in signal processing: We construct induced measures attached to those representations which turned out to be related to a class of zeta functions. For a particular case those measures give rise to a class of Markov measures and q-Bernoulli polynomials. Our approach is amenable to applications in problems from dynamics and mathematical physics: We introduce a deformation parameter q, and an associated family of q-relations where the number q is a ??quantum-deformation,?? and also a parameter in a scale of (Riemann-Ruelle) zeta functions. Our representations are used in turn in a derivation of formulas for this q-zeta function.     

Rings and semigroups with permutable zero products

We consider rings R, not necessarily with 1, for which there is a nontrivial permutation σ on n letters such that x₁?x_n=0 implies x_σ(1)?x_σ(n)=0 for all x₁,…,x_n∈R. We prove that this condition alone implies very strong permutability conditions for zero products with sufficiently many factors. To this end we study the infinite sequences of permutation groups P_n(R) consisting of those permutations σ on n letters for which the condition above is satisfied in R. We give the full characterization of such sequences both for rings and for semigroups with 0. This enables us to generalize some recent results by Cohn on reversible rings and by Lambek, Anderson and Camillo on rings and semigroups whose zero products commute. In particular, we prove that rings with permutable zero products satisfy the Köthe conjecture.     

Averaging of boundary-value problem in domain perforated along (<Emphasis Type="Italic">n</Emphasis> − 1)-dimensional manifold with nonlinear third type boundary conditions on the boundary of cavities

The research considers the asymptotic behavior of solutions u _? of the Poisson equation in a domain ?-periodically perforated along manifold γ = ω ∩ {x ₁ = 0} ≠ Ø with a nonlinear third type boundary condition ? _v u _? + ?^?ασ(x, u _?) = 0 on the boundary of the cavities. It is supposed that the perforations are balls of radius C ₀?^α, C ₀ > 0, α = n ? 1 / n ? 2, n ≥ 3, periodically distributed along the manifold γ with period ? > 0. It has been shown that as ? → 0 the microscopic solutions can be approximated by the solution of an effective problem which contains in a transmission conditions a new nonlinear term representing the macroscopic contribution of the processes on the boundary of the microscopic cavities. This effect was first noticed in [1] where the similar problem was investigated for n = 3 and for the case where Ω is a domain periodically perforated over the whole volume. This paper provides a new method for the proof of the convergence of the solutions {u _?} to the solution of the effective problem is given. Furthermore, an improved approximation for the gradient of the microscopic solutions is constructed, and more accurate results are obtained with respect to the energy norm proved via a corrector term. Note that this approach can be generalized to achieve results for perforations of more complex geometry.     

A universal sequence of integers generating balanced Steinhaus figures modulo an odd number

In this paper, we partially solve an open problem, due to J.C. Molluzzo in 1976, on the existence of balanced Steinhaus triangles modulo a positive integer n, that are Steinhaus triangles containing all the elements of Z/nZ with the same multiplicity. For every odd number n, we build an orbit in Z/nZ, by the linear cellular automaton generating the Pascal triangle modulo n, which contains infinitely many balanced Steinhaus triangles. This orbit, in Z/nZ, is obtained from an integer sequence called the universal sequence. We show that there exist balanced Steinhaus triangles for at least 2/3 of the admissible sizes, in the case where n is an odd prime power. Other balanced Steinhaus figures, such as Steinhaus trapezoids, generalized Pascal triangles, Pascal trapezoids or lozenges, also appear in the orbit of the universal sequence modulo n odd. We prove the existence of balanced generalized Pascal triangles for at least 2/3 of the admissible sizes, in the case where n is an odd prime power, and the existence of balanced lozenges for all admissible sizes, in the case where n is a square-free odd number.     

Robust interpolation of random fields homogeneous in time and isotropic on a sphere,which are observed with noise

We study the problem of optimal linear estimation of the functional $$A_N \xi = \sum\limits_{k = 0}^{\rm N} {\int\limits_{S_n } {a(k,x)\xi (k,x)m_n (dx),} }$$ , which depends on unknown values of a random field ξ(k, x),k?Z,x?S _n homogeneous in time and isotropic on a sphereS _n, by observations of the field ξ(k,x)+η(k,x) with k? Z{0, 1, ...,N},x?S_n (here, η (k, x) is a random field uncorrelated with ξ(k, x), homogeneous in time, and isotropic on a sphere S_n). We obtain formulas for calculation of the mean square error and spectral characteristic of the optimal estimate of the functionalA _Nξ. The least favorable spectral densities and minimax (robust) spectral characteristics are found for optimal estimates of the functionalA _Nξ.     

Classifying Erdős type spaces of higher descriptive complexity

Let ${({E_n})_{n \in \omega }}$ be a sequence of zero-dimensional subsets of the reals, ?. The Erd?s type space ? corresponding to this sequence is defined by ? = {x ∈ ? ²: x _n ∈ E _n , n ∈ω}. The most famous examples are Erd?s space, with E _n equal to the rationals for each n, and complete Erd?s space, with E _n = {0} ∪ {1/m: m ∈ ?} for each n. If all sets E _n are ${G_\delta }$ and the space ? is not zero-dimensional, then ? is known to be homeomorphic to complete Erd?s space, and if all sets E _n are ${F_{\sigma \delta }}$ , then under a mild additional condition ? is known to be homeomorphic to Erd?s space. In this paper we investigate the situation where all sets E _n are Borel sets in the same multiplicative class. Many of these spaces can be linked to the Erd?s type space with all sets E _n equal to the element of that multiplicative Borel class which absorbs the class. Furthermore, we introduce coanalytic Erd?s space and we establish a link between this space and homeomorphism groups of manifolds that leave the zero-dimensional pseudoboundary invariant. The general framework that we develop gives analogous results for nonseparable Erd?s type spaces.     

Searching monotone multi-dimensional arrays

A d-dimensional array of real numbers is called monotone increasing if its entries are increasing along each dimension. Given A_n,d, a monotone increasing d-dimensional array with n entries along each dimension, and a real number x, we want to decide whether x∈A_n,d, by performing a sequence of comparisons between x and some entries of A_n,d. We want to minimize the number of comparisons used. In this paper we investigate this search problem, we generalize Linial and Saks’ search algorithm [N. Linial, M. Saks, Searching ordered structures, J. Algorithms 6 (1985) 86-103] for monotone three-dimensional arrays to d-dimensions for d?4. For d=4, our new algorithm is optimal up to the lower order terms.     

Good equidistant codes constructed from certain combinatorial designs

An (n,M,d;q) code is called equidistant code if the Hamming distance between any two codewords is d. It was proved that for any equidistant (n,M,d;q) code, d?nM(q-1)/(M-1)q(=d_opt, say). A necessary condition for the existence of an optimal equidistant code is that d_opt be an integer. If d_opt is not an integer, i.e. the equidistant code is not optimal, then the code with d=⌊d_opt⌋ is called good equidistant code, which is obviously the best possible one among equidistant codes with parameters n,M and q. In this paper, some constructions of good equidistant codes from balanced arrays and nested BIB designs are described.