A graph theory approach to subcontracting, machine duplication and intercell moves in cellular manufacturing

We address in this paper the problem of finding an optimal strategy for dealing with bottleneck machines and bottleneck parts in the cell formation process in group technology. Three types of economic decisions are considered: subcontracting, machine duplication and intercell moves. The problem is formulated as a minimum weighted node covering problem in a hypergraph, and we show that it can be solved in polynomial time by finding a maximum weighted stable set in a bipartite graph. We extend this result to cellular manufacturing systems in which the sequence of operations of each part is known in advance.     

Partition Lattice q-Analogs Related to q-Stirling Numbers

We construct a family of partially ordered sets (posets) that are q-analogs of the set partition lattice. They are different from the q-analogs proposed by Dowling [5]. One of the important features of these posets is that their Whitney numbers of the first and second kind are just the q-Stirling numbers of the first and second kind, respectively. One member of this family [4] can be constructed using an interpretation of Milne [9] for S[n, k] as sequences of lines in a vector space over the Galois field F _q. Another member is constructed so as to mirror the partial order in the subspace lattice.     

Multiple domain dynamics simulated with coupled level sets

We adapt the level-set method to simulate epitaxial growth of thin films on a surface that consists of different reconstruction domains. Both the island boundaries and the boundaries of the reconstruction domains are described by different level-set functions. A formalism of coupled level-set functions that describe entirely different physical properties is introduced, where the velocity of each level-set function is determined by the value of the other level-set functions.     

Extending the Balas-Yu bounds on the number of maximal independent sets in graphs to hypergraphs and lattices

A result of Balas and Yu (1989) states that the number of maximal independent sets of a graph G is at most ^p+1, where is the number of pairs of vertices in G at distance 2, and p is the cardinality of a maximum induced matching in G. In this paper, we give an analogue of this result for hypergraphs and, more generally, for subsets of vectors in the product of n lattices =₁××_n, where the notion of an induced matching in G is replaced by a certain binary tree each internal node of which is mapped into . We show that our bounds may be nearly sharp for arbitrarily large hypergraphs and lattices. As an application, we prove that the number of maximal infeasible vectors x=₁××_n for a system of polymatroid inequalities does not exceed max{Q,^logt/c(2Q,)}, where is the number of minimal feasible vectors for the system, , , and c(,) is the unique positive root of the equation 2^c(^c/log–1)=1. This bound is nearly sharp for the Boolean case ={0,1}ⁿ, and it allows for the efficient generation of all minimal feasible sets to a given system of polymatroid inequalities with quasi-polynomially bounded right-hand sides . This research was supported by the National Science Foundation (Grant IIS-0118635), and by the Office of Naval Research (Grant N00014-92-J-1375). The second and third authors are also grateful for the partial support by DIMACS, the National Science Foundation's Center for Discrete Mathematics and Theoretical Computer Science.Mathematics Subject Classification (2000):20E28, 20G40, 20C20     

DIMENSIONS FORRANDOM SELF——CONFORMAL SETS

A set is called regular if its Hausdorff dimension and upper box-counting dimension coincide. In this paper, we prove that the random self-con formal set is regular almost surely. Also we determine the dimen-sions for a class of random self-con formal sets.     

On the Pesin set of expansive geodesic flows in manifolds with no conjugate points

In this paper, we show that the Pesin set of an expansive geodesic flow in compact manifold with no conjugate points and bounded asymptote coincides a.e with an open and dense set of the unit tangent bundle. We also show that the set of hyperbolic periodic orbits is dense in the unit tangent bundle.     

Generalized Padé-Type Approximation and Integral Representations

In several complex variables, the multivariate Padé-type approximation theory is based on the polynomial interpolation of the multidimensional Cauchy kernel and leads to complicated computations. In this paper, we replace the multidimensional Cauchy kernel by the Bergman kernel function K (z,x) into an open bounded subset of C ⁿ and, by using interpolating generalized polynomials for K (z,x), we define generalized Padé-type approximants to any f in the space OL ²() of all analytic functions on which are of class L ². The characteristic property of such an approximant is that its Fourier series representation with respect to an orthonormal basis for OL ²() matches the Fourier series expansion of f as far as possible. After studying the error formula and the convergence problem, we show that the generalized Padé-type approximants have integral representations which give rise to the consideration of an integral operator – the so-called generalized Padé-type operator – which maps every f OL ²() to a generalized Padé-type approximant to f. By the continuity of this operator, we obtain some convergence results about series of analytic functions of class L ². Our study concludes with the extension of these ideas into every functional Hilbert space H and also with the definition and properties of the generalized Padé-type approximants to a linear operator of H into itself. As an application we prove a Painlevé-type theorem in C ⁿ and we give two examples making use of generalized Padé-type approximants.     

Primal separation algorithms

Given an integer polyhedron , an integer point , and a point , the primal separation problem is the problem of finding a linear inequality which is valid for P _I , violated by x ^*, and satisfied at equality by . The primal separation problem plays a key role in the primal approach to integer programming. In this paper we examine the complexity of primal separation for several well-known classes of inequalities for various important combinatorial optimization problems, including the knapsack, stable set and travelling salesman problems.Received: November 2002, Revised: March 2003,     

Multi-bump solutions to Carrier's problem

We study the existence of well-known singularly perturbed BVP problem ε²y″=1−y²−2b(1−x²)y, y(−1)=y(1)=0 introduced by G.F. Carrier. In particular, we show that there exist multi-spike solutions, and the locations of interior spikes are clustered near x=0 and are separated by an amount of O(ε|lnε|), while only single spikes are allowed near the boundaries x=±1.     

Further results on large sets of disjoint group‐divisible designs with block size three and type 2n41

Large sets of disjoint group‐divisible designs with block size three and type 2ⁿ4¹ were first studied by Schellenberg and Stinson because of their connection with perfect threshold schemes. It is known that such large sets can exist only for n ≡0 (mod 3) and do exist for all odd n ≡ (mod 3) and for even n=24m, where m odd ≥ 1. In this paper, we show that such large sets exist also for n=2^k(3m), where m odd≥ 1 and k≥ 5. To accomplish this, we present two quadrupling constructions and two tripling constructions for a special large set called ^*LS(2ⁿ). © 2002 Wiley Periodicals, Inc. J Combin Designs 11: 24–35, 2003; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10032