Multi-dimensional vector assignment problems

We consider a special class of axial multi-dimensional assignment problems called multi-dimensional vector assignment (MVA) problems. An instance of the MVA problem is defined by $m$ disjoint sets, each of which contains the same number $n$ of $p$-dimensional vectors with nonnegative integral components, and a cost function defined on vectors. The cost of an $m$-tuple of vectors is defined as the cost of their component-wise maximum. The problem is now to partition the $m$ sets of vectors into $n$   $m$-tuples so that no two vectors from the same set are in the same $m$-tuple and so that the sum of the costs of the $m$-tuples is minimized. The main motivation comes from a yield optimization problem in semi-conductor manufacturing. We consider a particular class of polynomial-time heuristics for MVA, namely the sequential heuristics, and we study their approximation ratio. In particular, we show that when the cost function is monotone and subadditive, sequential heuristics have a finite approximation ratio for every fixed $m$. Moreover, we establish smaller approximation ratios when the cost function is submodular and, for a specific sequential heuristic, when the cost function is additive. We provide examples to illustrate the tightness of our analysis. Furthermore, we show that the MVA problem is APX-hard even for the case $m=3$ and for binary input vectors. Finally, we show that the problem can be solved in polynomial time in the special case of binary vectors with fixed dimension $p$.     

Scheduling jobs with time-resource tradeoff via nonlinear programming

We consider a scheduling problem where the processing time of any job is dependent on the usage of a discrete renewable resource, e.g. personnel. An amount of k units of that resource can be allocated to the jobs at any time, and the more of that resource is allocated to a job, the smaller its processing time. The objective is to find a resource allocation and a schedule that minimizes the makespan. We explicitly allow for succinctly encodable time-resource tradeoff functions, which calls for mathematical programming techniques other than those that have been used before. Utilizing a (nonlinear) integer mathematical program, we obtain the first polynomial time approximation algorithm for the scheduling problem, with performance bound (3+ε) for any ε>0. Our approach relies on a fully polynomial time approximation scheme to solve the nonlinear mathematical programming relaxation. We also derive lower bounds for the approximation.     

A Monte Carlo algorithm for real time task scheduling on multi-core processors with software controlled dynamic voltage scaling

The task scheduling problem for multi-core processors is an important algorithm design issue. Dynamic voltage scaling (DVS) is used to reduce the energy consumption of cores. We ponder the problem of task scheduling on a multi-core processor with software controlled DVS where the objective is to reduce the energy consumption. We consider a system with a single multi-core processor with software controlled DVS having a finite set of core speeds and discuss a task scheduling problem associated with it. The problem that we address is to find a minimum energy task schedule for a given set of independent tasks that have to be completed within a given common deadline. We propose a Monte Carlo algorithm of complexity $O(t(\mathit{mp}+q+\mathit{log}(t))+p(t+q)(D^{\mathit{pq}}+n))$ for solving the task scheduling problem and compare it with the optimal algorithm. Here t is the number of tasks, p is the number of cores, q is the number of core speeds, m is an integer parameter that is the number of iterations we should try to get a feasible solution before declaring that no solution is possible, n is an integer parameter that is the number of iterations we should try to reduce the energy consumption when we get a feasible solution, and D is the common deadline of the tasks.     

Distribution of extremal order statistics from large subsets of concomitants

From a random sample of size $n$ from an absolutely continuous bivariate population $(X,Y)$ we consider two complementary (upper and lower) subsets of $Y$-values formed by a sorting on the basis of the corresponding $X$-values. We derive the finite-sample and asymptotic joint distributions of the extreme order statistics of these $Y$ subsets assuming that the subset sizes remain proportional to $n$ as $n\to \infty$. We illustrate the use of our results with the bivariate normal example and provide an approximation to the probability of an event of interest in selection problems.     

The Cauchy problem for the 2D magnetohydrodynamic-α equations

In this paper, we consider the Cauchy problem for the 2D incompressible magnetohydrodynamics-$\alpha$ (MHD-$\alpha$) equations. We obtain the global solution for the 2D incompressible MHD-$\alpha$ simulation model in the fractional index Sobolev space, and prove that the incompressible MHD-$\alpha$ equations reduce to the incompressible homogeneous MHD equations as $\alpha \to 0$, and the solution of MHD-$\alpha$ equations will converge to the weak solution of the corresponding MHD equations. Moreover, it is convenient to construct a numerical algorithm based on an iteration scheme in our proof.     

On flow of a Navier–Stokes fluid in curved pipes. Part I: Steady flow

We consider the steady, fully developed motion of a Navier–Stokes fluid in a curved pipe of cross-section $D$ under a given axial pressure gradient $G$. We show that, if $G$ is constant, this problem has a smooth steady solution, for arbitrary values of the Dean’s number $\kappa$, for $D$ of arbitrary shape and for any curvature ratio $\delta$ of the pipe. This solution is also unique for $\kappa$ sufficiently small. Moreover, we prove that the solution is unidirectional (no secondary motion) if and only if $\kappa =0$. Finally, we show the same properties for the approximations to the Navier–Stokes equations called “Dean’s equations” and provide a rigorous way in which solutions to the full Navier–Stokes equations approach those to this approximation in the limit of $\delta \to 0$.     

A linear-time algorithm for finding an edge-partition with max-min ratio at most two

Given a positive integer $k$ and an undirected edge-weighted connected simple graph $G$ with at least $k$ edges of positive weight, we wish to partition the graph into $k$ edge-disjoint connected components of approximately the same size. We focus on the max-min ratio of the partition, which is the weight of the maximum component divided by that of the minimum component. It has been shown that for some instances, the max-min ratio is at least two. In this paper, for any graph with no edge weight larger than one half of the average weight, we provide a linear-time algorithm for delivering a partition with max-min ratio at most two. Furthermore, by an extreme example, we show that the above restriction on edge weights is the loosest possible.     

Stabilization and stability for the spherically symmetric Navier–Stokes–Poisson system

We consider global behaviour of viscous compressible flows with spherical symmetry driven by gravitation and an outer pressure, outside a hard core. For a general state function $p=p\left(\rho \right)$, we present global-in-time bounds for solutions with arbitrarily large data. For non-decreasing $p$, the $\omega$-limit set for the density $\rho$ is studied. For increasing $p$, uniqueness and static stability of the stationary solutions (including variational aspects) are investigated. Moreover, stabilization rate bounds toward the statically stable solutions are given and their nonlinear dynamical stability is shown.     

On the approximation of weakly plurifinely plurisubharmonic functions

In this note, we study the approximation of singular plurifine plurisubharmonic function $u$ defined on a plurifine domain $\Omega$. Under some condition we prove that $u$ can be approximated by an increasing sequence of plurisubharmonic functions defined on Euclidean neighborhoods of $\Omega$.     

The curse of dimensionality for the class of monotone functions and for the class of convex functions

We study the integration and approximation problems for monotone or convex bounded functions that depend on $d$ variables, where $d$ can be arbitrarily large. We consider the worst case error for algorithms that use finitely many function values. We prove that these problems suffer from the curse of dimensionality. That is, one needs exponentially many (in $d$) function values to achieve an error $\epsilon$.     

Existence and non-existence results for strong external difference families

We consider strong external difference families (SEDFs); these are external difference families satisfying additional conditions on the patterns of external differences that occur, and were first defined in the context of classifying optimal strong algebraic manipulation detection codes. We establish new necessary conditions for the existence of $(n,m,k,\lambda )$-SEDFs; in particular giving a near-complete treatment of the $\lambda =2$ case. For the case $m=2$, we obtain a structural characterization for partition type SEDFs (of maximum possible $k$ and $\lambda$), showing that these correspond to Paley partial difference sets. We also prove a version of our main result for generalized SEDFs, establishing non-trivial necessary conditions for their existence.