Single Supplier Scheduling for Multiple Deliveries

The problem of scheduling the production and delivery of a supplier to feed the production of F manufacturers is studied. The orders fulfilled by the supplier are delivered to the manufacturers in batches of the same size. The supplier's production line has to be set up whenever it switches from processing an order of one manufacturer to an order of another manufacturer. The objective is to minimize the total setup cost, subject to maintaining continuous production for all manufacturers. The problem is proved to be NP-hard. It is reduced to a single machine scheduling problem with deadlines and jobs belonging to F part types. An O(NlogF) algorithm, where N is the number of delivery batches, is presented to find a feasible schedule. A dynamic programming algorithm with O(N ^F /F ^F–2) running time is presented to find an optimal schedule. If F=2 and setup costs are unit, an O(N) time algorithm is derived.     

Fredholm and Propernes Properties of Quasilinear Elliptic Operators on RN

We discuss the Fredholm and properness properties of second-order quasilinear elliptic operators viewed as mappings from W^2,p( R ^N) to L^p( R ^N) with N < p < ∞. The unboundedness of the domain makes the standard Sobolev embedding theorems inadequate to investigate such issues. Instead, we develop several new tools and methods to obtain fairly simple necessary and suffcient conditions for such operators to be Fredholm with a given index and to be proper on the closed bounded subsets of W^2,p( R ^N). It is noteworthy that the translation invariance of the domain, well-known to be responsible for the lack of compactness in the Sobolev embedding theorems, is taken advantage of to establish results in the opposite direction and is indeed crucial to the proof of the properness criteria. The limitation to second-order and scalar equations chosen in our exposition is relatively unimportant, as none of the arguments involved here relies upon either of these assumptions. Generalizations to higher order equations or to systems are thus clearly possible with a variableamount of extra work. Various applications, notably but not limited, to global bifurcation problems, are described elsewhere.     

The rotor-router model on regular trees

The rotor-router model is a deterministic analogue of random walk. It can be used to define a deterministic growth model analogous to internal DLA. We show that the set of occupied sites for this model on an infinite regular tree is a perfect ball whenever it can be, provided the initial rotor configuration is acyclic (that is, no two neighboring vertices have rotors pointing to one another). This is proved by defining the rotor-router group of a graph, which we show is isomorphic to the sandpile group. We also address the question of recurrence and transience: We give two rotor configurations on the infinite ternary tree, one for which chips exactly alternate escaping to infinity with returning to the origin, and one for which every chip returns to the origin. Further, we characterize the possible “escape sequences” for the ternary tree, that is, binary words a₁…an for which there exists a rotor configuration so that the kth chip escapes to infinity if and only if ak=1.     

Application of fast spherical Fourier transform to density estimation

This paper is on density estimation on the 2-sphere, S², using the orthogonal series estimator corresponding to spherical harmonics. In the standard approach of truncating the Fourier series of the empirical density, the Fourier transform is replaced with a version of the discrete fast spherical Fourier transform, as developed by Driscoll and Healy. The fast transform only applies to quantitative data on a regular grid. We will apply a kernel operator to the empirical density, to produce a function whose values at the vertices of such a grid will be the basis for the density estimation. The proposed estimation procedure also contains a deconvolution step, in order to reduce the bias introduced by the initial kernel operator. The main issue is to find necessary conditions on the involved discretization and the bandwidth of the kernel operator, to preserve the rate of convergence that can be achieved by the usual computationally intensive Fourier transform. Density estimation is considered in L²(S²) and more generally in Sobolev spaces H_v(S²), any v?0, with the regularity assumption that the probability density to be estimated belongs to H_s(S²) for some s>v. The proposed technique to estimate the Fourier transform of an unknown density keeps computing cost down to order O(n), where n denotes the sample size.     

Evaluating the boundary and covering degree of planar Minkowski sums and other geometrical convolutions

Algorithms are developed, based on topological principles, to evaluate the boundary and “internal structure” of the Minkowski sum of two planar curves. A graph isotopic to the envelope curve is constructed by computing its characteristic points. The edges of this graph are in one-to-one correspondence with a set of monotone envelope segments. A simple formula allows a degree   to be assigned to each face defined by the graph, indicating the number of times its points are covered by the Minkowski sum. The boundary can then be identified with the set of edges that separate faces of zero and non-zero degree, and the boundary segments corresponding to these edges can be approximated to any desired geometrical accuracy. For applications that require only the Minkowski sum boundary, the algorithm minimizes geometrical computations on the “internal” envelope edges, that do not contribute to the final boundary. In other applications, this internal structure is of interest, and the algorithm provides comprehensive information on the covering degree for different regions within the Minkowski sum. Extensions of the algorithm to the computation of Minkowski sums in R³${\mathbb{R}}^3$, and other forms of geometrical convolution, are briefly discussed.     

Improving the Data Augmentation Algorithm in the Two-Block Setup

The data augmentation (DA) approach to approximate sampling from an intractable probability density f_X is based on the construction of a joint density, f_{X, Y}, whose conditional densities, f_X|Y and f_Y|X, can be straightforwardly sampled. However, many applications of the DA algorithm do not fall in this “single-block” setup. In these applications, X is partitioned into two components, X = (U, V), in such a way that it is easy to sample from f_Y|X, f_{U|V, Y}, and f_{V|U, Y}. We refer to this alternative version of DA, which is effectively a three-variable Gibbs sampler, as “two-block” DA. We develop two methods to improve the performance of the DA algorithm in the two-block setup. These methods are motivated by the Haar PX-DA algorithm, which has been developed in previous literature to improve the performance of the single-block DA algorithm. The Haar PX-DA algorithm, which adds a computationally inexpensive extra step in each iteration of the DA algorithm while preserving the stationary density, has been shown to be optimal among similar techniques. However, as we illustrate, the Haar PX-DA algorithm does not lead to the required stationary density f_X in the two-block setup. Our methods incorporate suitable generalizations and modifications to this approach, and work in the two-block setup. A theoretical comparison of our methods to the two-block DA algorithm, a much harder task than the single-block setup due to nonreversibility and structural complexities, is provided. We successfully apply our methods to applications of the two-block DA algorithm in Bayesian robit regression and Bayesian quantile regression. Supplementary materials for this article are available online.     

The π-π-theorem for manifold pairs with boundaries

The surgery obstruction of a normal map to a simple Poincaré pair (X, Y) lies in the relative surgery obstruction group L _*(π ₁(Y) → π ₁(X)). A well-known result of Wall, the so-called π-π-theorem, states that in higher dimensions a normal map of a manifold with boundary to a simple Poincaré pair with π ₁(X) ? π ₁(Y) is normally bordant to a simple homotopy equivalence of pairs. In order to study normal maps to a manifold with a submanifold, Wall introduced the surgery obstruction groups LP _* for manifold pairs and splitting obstruction groups LS _*. In the present paper, we formulate and prove for manifold pairs with boundary results similar to the π-π-theorem. We give direct geometric proofs, which are based on the original statements of Wall’s results and apply obtained results to investigate surgery on filtered manifolds.     

A multi-round generalization of the traveling tournament problem and its application to Japanese baseball

In a double round-robin tournament involving n teams, every team plays 2(n − 1) games, with one home game and one away game against each of the other n − 1 teams. Given a symmetric n by n matrix representing the distances between each pair of home cities, the traveling tournament problem (TTP) seeks to construct an optimal schedule that minimizes the sum total of distances traveled by the n teams as they move from city to city, subject to several natural constraints to ensure balance and fairness. In the TTP, the number of rounds is set at r = 2. In this paper, we generalize the TTP to multiple rounds (r = 2k, for any k ? 1) and present an algorithm that converts the problem to finding the shortest path in a directed graph, enabling us to apply Dijkstra’s Algorithm to generate the optimal multi-round schedule. We apply our shortest-path algorithm to optimize the league schedules for Nippon Professional Baseball (NPB) in Japan, where two leagues of n = 6 teams play 40 sets of three intra-league games over r = 8 rounds. Our optimal schedules for the Pacific and Central Leagues achieve a 25% reduction in total traveling distance compared to the 2010 NPB schedule, implying the potential for considerable savings in terms of time, money, and greenhouse gas emissions.     

Conceptualism and the Problem of Illusory Experience

According to the conceptualist view in the philosophy of perception, we possess concepts for all the objects, properties, and relations which feature in our experiences. Richard Heck has recently argued that the phenomenon of illusory experience provides us with conclusive reasons to reject this view. In this paper, I examine Heck’s argument, I explain why I think that Bill Brewer’s conceptualist response to it is ineffective, and I then outline an alternative conceptualist response which I myself endorse. My argument turns on the fact that both Heck, in constructing his objection to conceptualism, and Brewer, in responding to it, miss a crucial distinction between perceptual demonstrative concepts of objects, on the one hand, and perceptual demonstrative concepts of properties, on the other.

Cyclic networks with general blocking and starvation

We introducegeneral starvation and consider cyclic networks withgeneral blocking and starvation (GBS). The mechanism of general blocking allows the server to process a limited number of jobs when the buffer downstream is full, and that of general starvation allows the server to perform a limited number of services in anticipation of jobs that are yet to arrive. The two main goals of this paper are to investigate how the throughput of cyclic GBS networks is affected by varying (1) the total number of jobsJ, and (2) the buffer allocationk=(k₁..., k_m) subject to a fixed total buffer capacityK=k ₁ +... + k_m. In particular, we obtain sufficient conditions for the throughput to be symmetric inJ and to be maximized whenJ=K/2. We also show that the equal buffer allocation is optimal under the two regimes of light or heavy usage. In order to establish these results, we obtain several intermediate structural properties of the throughput, using duality, reversibility, and concavity, which are of independent interest.Research supported in part by NSF Grant No. ECS-8919818.     

Embedding up to homotopy type— The first obstruction

For a 2n?m connected map from an n-dimensional complex to a m-dimensional manifold, an obstruction to embedding up to homotopy type is defined. The vanishing of this obstruction is a necessary and sufficient condition (in the 2n?m connected case, 2n?m ? 2, m?n ?3) to obtain an embedding up to homotopy type. In case the target manifold is Euclidean space, it is shown that the obstruction vanishes if and only if certain Thom operations are trivial. A classification theorem is given in the 2n?m+1 connected case.     

The Transitive Minimum Manhattan Subnetwork Problem in 3 dimensions

We consider the Minimum Manhattan Subnetwork (MMSN) Problem which generalizes the already known Minimum Manhattan Network (MMN) Problem: Given a set P of n points in the plane, find shortest rectilinear paths between all pairs of points. These paths form a network, the total length of which has to be minimized. From a graph theoretical point of view, a MMN is a 1-spanner with respect to the L₁ metric. In contrast to the MMN problem, a solution to the MMSN problem does not demand L₁-shortest paths for all point pairs, but only for a given set R⊆P×P of pairs. The complexity status of the MMN problem is still unsolved in ≥2 dimensions, whereas the MMSN was shown to be NP-complete considering general relations R in the plane. We restrict the MMSN problem to transitive relations R_T (Transitive Minimum Manhattan Subnetwork (TMMSN) Problem) and show that the TMMSN problem in 3 dimensions is NP-complete.     

Efficient algorithms for the matrix cosine and sine

Several improvements are made to an algorithm of Higham and Smith for computing the matrix cosine. The original algorithm scales the matrix by a power of 2 to bring the ∞-norm to 1 or less, evaluates the [8/8] Padé approximant, then uses the double-angle formula cos (2A)=2cos ²A−I to recover the cosine of the original matrix. The first improvement is to phrase truncation error bounds in terms of ‖A²‖^1/2 instead of the (no smaller and potentially much larger quantity) ‖A‖. The second is to choose the degree of the Padé approximant to minimize the computational cost subject to achieving a desired truncation error. A third improvement is to use an absolute, rather than relative, error criterion in the choice of Padé approximant; this allows the use of higher degree approximants without worsening an a priori error bound. Our theory and experiments show that each of these modifications brings a reduction in computational cost. Moreover, because the modifications tend to reduce the number of double-angle steps they usually result in a more accurate computed cosine in floating point arithmetic. We also derive an algorithm for computing both cos (A) and sin (A), by adapting the ideas developed for the cosine and intertwining the cosine and sine double angle recurrences. AMS subject classification 65F30 Numerical Analysis Report 461, Manchester Centre for Computational Mathematics, February 2005. Gareth I. Hargreaves: This work was supported by an Engineering and Physical Sciences Research Council Ph.D. Studentship. Nicholas J. Higham: This work was supported by Engineering and Physical Sciences Research Council grant GR/T08739 and by a Royal Society–Wolfson Research Merit Award.     

Generic representations of the finite general linear groups and the Steenrod algebra: II

The category of generic representations over the finite fieldF _q , used in PartI to study modules over the Steenrod algebra, is here related to the modular representation theory of the groups GL _n (F _q ). This leads to a simple and elegant approach to the classic objects of study: irreducible representations, extensions of modules, homology stability, etc. Connections to current research in algebraicK-theory involving stableK-theory and Topological Hochschild Homology are also explained.Partially funded by the NSF.     

Approximations and Well-Posedness in Multicriteria Games

First, sufficient conditions of minimal character are given which guarantee the sequential closedness of the set-valued function defined by the parametric weak-multicriteria Nash equilibria of a parametric multicriteria game, that is to say: a convergent sequence of parametric weak-multicriteria Nash equilibria, corresponding to an approximate value of the parameter x_n, converges to a weak-multicriteria Nash equilibrium corresponding to the limit value x of the sequence (x_n)_n. Then, approximating sequences and parametrically well-posedness for a multicriteria game are introduced and investigated.     

On error operators related to the arbitrary functions principle

The error on a real quantity Y due to the graduation of the measuring instrument may be asymptotically represented, when the graduation is regular and fines down, by a Dirichlet form on R whose square field operator does not depend on the probability law of Y as soon as this law possesses a continuous density. This feature is related to the “arbitrary functions principle” (Poincaré, Hopf). We give extensions of this property to Rd and to the Wiener space for some approximations of the Brownian motion. This gives new approximations of the Ornstein-Uhlenbeck gradient. These results apply to the discretization of some stochastic differential equations encountered in mechanics.     

Attracting cycles for the relaxed Newton’s method

We study the relaxed Newton’s method applied to polynomials. In particular, we give a technique such that for any n≥2, we may construct a polynomial so that when the method is applied to a polynomial, the resulting rational function has an attracting cycle of period n. We show that when we use the method to extract radicals, the set consisting of the points at which the method fails to converge to the roots of the polynomial p(z)=z^m−c (this set includes the Julia set) has zero Lebesgue measure. Consequently, iterate sequences under the relaxed Newton’s method converge to the roots of the preceding polynomial with probability one.