No abstract uploaded!

No abstract uploaded!

We propose a dynamically bi-orthogonal method (DyBO) to solve time dependent stochastic partial differential equations (SPDEs). The objective of our method is to exploit some intrinsic sparse structure in the stochastic solution by constructing the sparsest representation of the stochastic solution via a bi-orthogonal basis. It is well-known that the KarhunenLoeve expansion (KLE) minimizes the total mean squared error and gives the sparsest representation of stochastic solutions. However, the computation of the KL expansion could be quite expensive since we need to form a covariance matrix and solve a large-scale eigenvalue problem. The main contribution of this paper is that we derive an equivalent system that governs the evolution of the spatial and stochastic basis in the KL expansion. Unlike other reduced model methods, our method constructs the reduced basis on-the-fly without the need to form the

We introduce a parallel machine scheduling problem in which the processing times of jobs are not given in advance but are determined by a system of linear constraints. The objective is to minimize the makespan, i.e., the maximum job completion time among all feasible choices. This novel problem is motivated by various real-world application scenarios. We discuss the computational complexity and algorithms for various settings of this problem. In particular, we show that if there is only one machine with an arbitrary number of linear constraints, or there is an arbitrary number of machines with no more than two linear constraints, or both the number of machines and the number of linear constraints are fixed constants, then the problem is polynomial-time solvable via solving a series of linear programming problems. If both the number of machines and the number of constraints are inputs of the problem instance, then the problem is NP-Hard. We further propose several approximation algorithms for the latter case.

Let W be an extended affine Weyl group. We prove that the minimal length elements W of any conjugacy class W of W satisfy some nice properties, generalizing results of Geck and Pfeiffer [<i>On the irreducible characters of Hecke algebras</i>, Adv. Math. <b>102</b> (1993), 7994] on finite Weyl groups. We also study a special class of conjugacy classes, the straight conjugacy classes. These conjugacy classes are in a natural bijection with the Frobenius-twisted conjugacy classes of some W -adic group and satisfy additional interesting properties. Furthermore, we discuss some applications to the affine Hecke algebra W