Permutation Polyhedra and Minimisation of the Variance of Completion Times on a Single Machine

We consider the problem of minimising variance of completion times when n-jobs are to be processed on a single machine. This problem is known as the CTV problem. The problem has been shown to be difficult. In this paper we consider the polytope P _n whose vertices are in one-to-one correspondence with the n! permutations of the processing times [p ₁, p ₂, ..., p _n]. Thus each vertex of P _n represents a sequence in which the n-jobs can be processed. We define a V-shaped local optimal solution to the CTV problem to be the V-shaped sequence of jobs corresponding to which the variance of completion times is smaller than for all the sequences adjacent to it on P _n. We show that this local solution dominates V-shaped feasible solutions of the order of 2 ^n–3 where 2 ^n–2 is the total number of V-shaped feasible solutions.Using adjacency structure an P _n, we develop a heuristic for the CTV problem which has a running time of low polynomial order, which is exact for n 10, and whose domination number is (2 ^n–3). In the end we mention two other classes of scheduling problems for which also ADJACENT provides solutions with the same domination number as for the CTV problem.     

On reduction of block matrices in a Hilbert space

We study the problem of the reduction of self-adjoint block matrices B = (B _ij ) with given graph by a group of unitary block diagonal matrices. Under the condition that the matrices B ² and B ⁴ are orthoscalar, we describe the graphs of block matrices for which this problem is a problem of *-finite, *-tame, or *-wild representation type.     

Asymptotic analysis of a spectral problem in a periodic thick junction of type 3:2:1

Convergence theorems and asymptotic estimates (as ϵ→0) are proved for eigenvalues and eigenfunctions of a mixed boundary value problem for the Laplace operator in a junction Ω_ϵ of a domain Ω₀ and a large number N² of ϵ‐periodically situated thin cylinders with thickness of order ϵ=O(N⁻¹). We construct an extension operator that is only asymptotically bounded in ϵ on the eigenfunctions in the Sobolev space H¹. An approach based on the asymptotic theory of elliptic problem in singularly perturbed domains is used. Copyright © 2000 John Wiley & Sons, Ltd.     

Extremum Problem for Periodic Functions Supported in a Ball

We consider the Turan n-dimensional extremum problem of finding the value of A_n(hB ⁿ ) which is equal to the maximum zero Fourier coefficient of periodic functions f supported in the Euclidean ball hB ⁿ of radius h, having nonnegative Fourier coefficients, and satisfying the condition f(0)= 1. This problem originates from applications to number theory. The case of A₁([–h,h]) was studied by S. B. Stechkin. For A_n(hB ⁿ we obtain an asymptotic series as h 0 whose leading term is found by solving an n-dimensional extremum problem for entire functions of exponential type.     

Perturbation Analysis for the Eigenvalue Problem of a Formal Product of Matrices

We study the perturbation theory for the eigenvalue problem of a formal matrix product A ₁ ^{s 1} ··· A _p ^{s p}, where all A _k are square and s _k {–1, 1}. We generalize the classical perturbation results for matrices and matrix pencils to perturbation results for generalized deflating subspaces and eigenvalues of such formal matrix products. As an application we then extend the structured perturbation theory for the eigenvalue problem of Hamiltonian matrices to Hamiltonian/skew-Hamiltonian pencils.     

A finite algorithm for the continuousp-center location problem on a graph

LetG=(V,E) be an undirected graph with positive integer edge lengths. Letm be the number of edges inE, and letd be the sum of the edge lengths. We prove that the solution value to the continuousp-center location problem is a rationalp ₁/p ₂, where logp ₁=O(m ⁵ logd+m ⁶ logp),i=1,2. This result is then used to construct a finite algorithm for the continuousp-center problem.     

Nonnegative solutions of a nonlinear recurrence

Orthonormal polynomials with weight ¦τ¦ exp(−τ⁴) have leading coefficients with recurrence properties which motivate the more general equations ξ_m(ξ_{m − 1} + ξ_m + ξ_{m + 1}) = γ_m², M = 1, 2,…, where ξ_o is a fixed nonnegative value and γ₁, γ₂,… are positive constants. For this broader problem, the existence of a nonnegative solution is proved and criteria are found for its uniqueness. Then, for the motivating problem, an asymptotic expansion of its unique nonnegative solution is obtained and a fast computational algorithm, with error estimates, is given.     

An elliptic boundary problem in a half–space

The spectral theory for general non–selfadjoint elliptic boundary problems involving a discontinuous weight function has been well developed under certain restrictions concerning the weight function. In the course of extending the results so far established to a more general weight function, there arises the problem of establishing, in an L_p Sobolev space setting, the existence of and a priori estimates for solutions for a boundary problem for the half–space ?ⁿ₊ involving a weight function which vanishes at the boundary x_n = 0. In this paper we resolve this problem.     

A necessary and sufficient condition to a pareto optimal without optimizing the weighting criterion

The easiest thecnique to reduce the classical multiple criteria decision problem into a reasonable single criterion decision problem is the weighting method. Po-Lung Yu (1985) gives a well known necessary condition fory ⁰ to be a Pareto optimal, namelyy ⁰ maximizes λ^ty overY, for some λ ∈ℝ ^p, such that λ_i≥0 for alli and some λ_j>0. In this brief note we generalize the necessary condition of Po-Lung Yu.     

Solution of the Dirichlet problem for a singularly perturbed reaction-diffusion equation in a square on a Bakhvalov grid

The Dirichlet problem for a singularly perturbed reaction-diffusion equation in a square is solved with the help of the classic five-point difference scheme and a grid that is the tensor product of 1D Bakhvalov grids. Without imposing additional matching conditions in the corners of the domain, it is shown that the grid solution to the problem has the accuracy O(N ⁻²) in the norm L _∞ ^h , where N is the number of grid nodes along each direction. The accuracy is uniform with respect to a small parameter. A simulation confirms the theoretical prediction.     

L 2 -discrete hedging in a continuous-time model

In the setting of the Black-Scholes option pricing market model, the seller of a European option must trade continuously in time. This is, of course, unrealistic from the practical viewpoint. He must then follow a discrete trading strategy. However, it does not seem natural to hedge at deterministic times regardless of moves of the spot price. In this paper, it is supposed that the hedger trades at a fixed number N of rebalancing (stopping) times. The problem (P^N) of selecting the optimal hedging times and ratios which allow one to minimize the variance of replication error is considered. For given N rebalancing, the discrete optimal hedging strategy is identified for this criterion. The problem (P^N) is then transformed into a multidimensional optimal stopping problem with boundary constraints. The restrictive problem (P^N _BS) of selecting the optimal rebalancing for the same criterion is also considered when the ratios are given by Black-Scholes. Using the vector-valued optimal stopping theory, the existence is shown of an optimal sequence of rebalancing for each one of the problems (P^N) and (P^N _BS). It also shown BS that they are asymptotically equivalent when the number of rebalances becomes large and an optimality criterion is stated for the problem (P^N). The same study is made when more realistic restrictions are imposed on the hedging times. In the special case of two rebalances, the problem (P² _BS) is solved and the problems (P² _BS) and (P²) are transformed into two optimal stopping problems. This transformation is useful for numerical purposes.     

On-line covering a cube by a sequence of cubes

A procedure for packing or covering a given convex bodyK with a sequence of convex bodies {C _i} is anon-line method if the setC _i are given in sequence. andC _i+1 is presented only afterC _i has been put in place, without the option of changing the placement afterward. The “one-line” idea was introduced by Lassak and Zhang [6] who found an asymptotic volume bound for the problem of on-line packing a cube with a sequence of convex bodies. In this note a problem of Lassak is solved, concerning on-line covering a cube with a sequence of cubes, by proving that every sequence of cubes in the Euclidean spaceE ^d whose total volume is greater than 4 ^d admits an on-line covering of the unit cube. Without the “on-line” restriction, the best possible volume bound is known to be 2 ^d −1, obtained by Groemer [2] and, independently, by Bezdek and Bezdek [1]. The on-line covering method described in this note is based on a suitable cube-filling Peano curve.     

Nonlinear filtering and large deviations:a pde-control theoretic approach

We consider the asymptotic nonlinear filtering problem dx=f(x)dt + ?^1/2 dw,dy=h(x) dt + ? dv and obtain lim_?→0 ? log q ²(x,t) = -W(x,t) for unnormalized conditional densities q ²(x,t) using PDE methods. HereW(x,t) is the value function for a deterministic optimal control problem arising in Mortensen's deterministic estimation, and is the unique viscosity solution of a Hamilton-Jacobi-Bellman equation. ijab has also studied this filtering problem, and we extend his large deviation result for certain unnormalized conditional measures. The resulting variational problem corresponds to the above control problem     

Homogenization of a non‐linear degenerate parabolic problem in a highly heterogeneous periodic medium

We consider the homogenization of a time‐dependent heat transfer problem in a highly heterogeneous periodic medium made of two connected components having comparable heat capacities and conductivities, separated by a third material with thickness of the same order ε as the basic periodicity cell but having a much lower conductivity such that the resulting interstitial heat flow is scaled by a factor λ tending to zero with a rate λ=λ(ε). The heat flux vectors a_j, j=1,2,3 are non‐linear, monotone functions of the temperature gradient. The heat capacities c_j(x) are positive, but may vanish at some subsets such that the problem can be degenerate (parabolic–elliptic). We show that the critical value of the problem is δ=lim_ε→0ε^p/λ and identify the homogenized problem depending on whether δ is zero, strictly positive finite or infinite. Copyright © 2005 John Wiley & Sons, Ltd.     

Quantified propositional calculus and a second-order theory for NC1

Let H be a proof system for quantified propositional calculus (QPC). We define the Σ^q_j-witnessing problem for H to be: given a prenex Σ^q_j-formula A, an H-proof of A, and a truth assignment to the free variables in A, find a witness for the outermost existential quantifiers in A. We point out that the Σ^q₁-witnessing problems for the systems G^*₁and G₁ are complete for polynomial time and PLS (polynomial local search), respectively. We introduce and study the systems G^*₀ and G₀, in which cuts are restricted to quantifier-free formulas, and prove that the Σ^q_j-witnessing problem for each is complete for NC¹. Our proof involves proving a polynomial time version of Gentzen’s midsequent theorem for G^*₀ and proving that G₀-proofs are TC⁰-recognizable. We also introduce QPC systems for TC⁰ and prove witnessing theorems for them. We introduce a finitely axiomatizable second-order system VNC¹ of bounded arithmetic which we prove isomorphic to Arai’s first order theory AID + Σ^b ₀-CA for uniform NC¹. We describe simple translations of VNC¹ proofs of all bounded theorems to polynomial size families of G^*₀ proofs. From this and the above theorem we get alternative proofs of the NC¹ witnessing theorems for VNC¹ and AID.This research was carried while this author was a student at the University of Toronto.     

Cryptanalysis of a Matrix-based MOR System

We cryptanalyze a recently proposed matrix-based MOR cryptosystem. The security of the system depends on the difficulty of solving the following discrete logarithm problem: given an inner automorphism φ of SL(d, 𝔽 _q ) and φ ^a (each given in terms of their images on generators of SL(d, 𝔽 _q )), find a. We show that this problem can be reduced to a small number of similar problems in quotients of polynomial rings and solved in subexponential-time.     

A dynamic programming algorithm for preemptive scheduling of a single machine to minimize the number of late jobs

The scheduling problem 1|pmtn, r _j |w _j U _j calls forn jobs with arbitrary release dates and due dates to be preemptively scheduled for processing by a single machine, with the objective of minimizing the sum of the weights of the late jobs. A dynamic programming algorithm for this problem is described. Time and space bounds for the algorithm are, respectively,O(nk ² W ²) andO(k ² W), wherek is the number of distinct release dates andW is the sum of the integer job weights. Thus, for the problem 1|pmtn, r _j |U _j , in which the objective is simply to minimize the number of late jobs, the pseudopolynomial time bound becomes polynomial, i.e.O(n ³ k ²).     

Estimation of a Mean Vector in a Two-Sample Problem

We consider the problem of estimating a p-dimensional vector μ₁ based on independent variables X₁, X₂, and U, where X₁ is N_p(μ₁, σ²Σ₁), X₂ is N_p(μ₂, σ²Σ₂), and U is σ²χ²_n (Σ₁ and Σ₂ are known). A family of minimax estimators is proposed. Some of these estimators can be obtained via Bayesian arguments as well. Comparisons between our results and the one of Ghosh and Sinha (1988, J. Multivariate Anal.27 206-207) are presented.     

An a priori estimate for Douglas problem in Riemannian manifolds

This paper is concerned with the Douglas problem in general Riemannian manifolds. For its perturbed problem we establish a uniform a priori estimate under the energy level min {d ^*,m ^* +s ₀} (see Theorem 3.3). This level seems to be the best possible since in case of ⁿ it is just the Douglas condition.Project supported by the post-doctoral fellowship of the Chinese Academy of Sciences. Many thanks are due to Prof. J. G. Peng for his encouragement and generous help.     

Computing an Eigenvector of a Monge Matrix in Max-Plus Algebra

The problem of finding one eigenvector of a given Monge matrix A in a max-plus algebra is considered. For a general matrix, the problem can be solved in O(n ³) time by computing one column of the corresponding metric matrix Δ(A _λ), where λ is the eigenvalue of A. An algorithm is presented, which computes an eigenvector of a Monge matrix in O(n ²) time.