An approximation algorithm for the generalized assignment problem

The generalized assignment problem can be viewed as the following problem of scheduling parallel machines with costs. Each job is to be processed by exactly one machine; processing jobj on machinei requires timep _ij and incurs a cost ofc _ij ; each machinei is available forT _i time units, and the objective is to minimize the total cost incurred. Our main result is as follows. There is a polynomial-time algorithm that, given a valueC, either proves that no feasible schedule of costC exists, or else finds a schedule of cost at mostC where each machinei is used for at most 2T _i time units.We also extend this result to a variant of the problem where, instead of a fixed processing timep _ij , there is a range of possible processing times for each machine—job pair, and the cost linearly increases as the processing time decreases. We show that these results imply a polynomial-time 2-approximation algorithm to minimize a weighted sum of the cost and the makespan, i.e., the maximum job completion time. We also consider the objective of minimizing the mean job completion time. We show that there is a polynomial-time algorithm that, given valuesM andT, either proves that no schedule of mean job completion timeM and makespanT exists, or else finds a schedule of mean job completion time at mostM and makespan at most 2T. Research partially supported by an NSF PYI award CCR-89-96272 with matching support from UPS, and Sun Microsystems, and by the National Science Foundation, the Air Force Office of Scientific Research, and the Office of Naval Research, through NSF grant DMS-8920550.Research supported in part by a Packard Fellowship, a Sloan Fellowship, an NSF PYI award, and by the National Science Foundation, the Air Force Office of Scientific Research, and the Office of Naval Research, through NSF grant DMS-8920550.     

Optimal maps for the multidimensional Monge-Kantorovich problem

Let μ₁,…, μ_N be Borel probability measures on ℝ^d. Denote by Γ(μ₁,…, μ_N) the set of all N-tuples T=(T₁,…, T_N) such that T_i:ℝ^d ↔ ℝ^d (i = 1,…, N) are Borel-measurable and satisfy μ₁ = μ_i[V] for all Borel V ⊂ ℝ^d. The multidimensional Monge-Kantorovich problem investigated in this paper consists of finding S=(S₁,…, S_N) ∈ Γ(μ₁,…, μ_N) minimizing over the set Γ(μ₁, ···, μ_N). We study the case where the μ_i's have finite second moments and vanish on (d - 1)-rectifiable sets. We prove existence and uniqueness of optimal maps S when we impose that S₁( x ) ≡ x and give an explicit form of the maps S_i. The result is obtained by variational methods and to the best of our knowledge is the first available in the literature in this generality. As a consequence, we obtain uniqueness and characterization of an optimal measure for the multidimensional Kantorovich problem. © 1998 John Wiley & Sons, Inc.     

Strongly maximal antichains in posets

Given a collection S of sets, a set S∈S is said to be strongly maximal in S if |T?S|≤|S?T| for every T∈S. In Aharoni (1991) [3] it was shown that a poset with no infinite chain must contain a strongly maximal antichain. In this paper we show that for countable posets it suffices to demand that the poset does not contain a copy of posets of two types: a binary tree (going up or down) or a “pyramid”. The latter is a poset consisting of disjoint antichains A_i,i=1,2,…, such that |A_i|=i and x<y whenever x∈A_i,y∈A_j and j<i (a “downward” pyramid), or x<y whenever x∈A_i,y∈A_j and i<j (an “upward” pyramid).     

A stochastic production planning model with a dynamic chance constraint

This paper deals with the optimal production planning for a single product over a finite horizon. The holding and production costs are assumed quadratic as in Holt, Modigliani, Muth and Simon (HMMS) [7] model. The cumulative demand is compound Poisson and a chance constraint is included to guarantee that the inventory level is positive with a probability of at least α at each time point. The resulting stochastic optimization problem is transformed into a deterministic optimal control problem with control variable and of the optimal solution is presented. The form of state variable inequality constraints. A discussion the optimal control (production rate) is obtained as follows: if there exists a time t₁ such that t₁?[O, T]where T is the end of the planning period, then (i) produce nothing until t₁ and (ii) produce at a rate equal to the expected demand plus a ‘correction factor’ between t₁ and T. If t₁ is found to be greater than T, then the optimal decision is to produce nothing and always meet the demand from the inventory.     

Optimal two-layer selection policy for a flexible manufacturing system

This paper deals with the selection problem in a manufacturing system. The manufacturing system consists of a flexible manufacturing cellC ₀ which feedsM flexible manufacturing cellsC _1i ,i=1, ...,M. In addition, each cellC _1i ,i=1, ...,M, is feeding several production lines. Sufficient conditions on optimal feedback selection policies for theM+1 flexible manufacturing cells are derived. These selection policies maximize the probability of the system output reaching some demand before any of the system buffers is being overflowed. A numerical study is conducted.     

Extensions and biextensions of locally constant group schemes,tori and abelian schemes

Let S be a scheme. We compute explicitly the group of homomorphisms, the S-sheaf of homomorphisms, the group of extensions, and the S-sheaf of extensions involving locally constant S-group schemes, abelian S-schemes, and S-tori. Using the obtained results, we study the categories of biextensions involving these geometrical objects. In particular, we prove that if G _i (for i = 1, 2, 3) is an extension of an abelian S-scheme A _i by an S-torus T _i , the category of biextensions of (G ₁, G ₂) by G ₃ is equivalent to the category of biextensions of the underlying abelian S-schemes (A ₁, A ₂) by the underlying S-torus T ₃.      

Analysis of two commodity Markovian inventory system with lead time

A two commodity continuous review inventory system with independent Poisson processes for the demands is considered in this paper. The maximum inventory level for the i-th commodity is fixed asS ⁱ (i = 1,2). The net inventory level at timet for the i-th commodity is denoted byI ⁱ(t),i = 1,2. If the total net inventory levelI(t) =I ¹(t) +I ²(t) drops to a prefixed level s[ \leqslant \tfrac(S₁ - 2)2or\tfrac(S₂ - 2)2]s[ \leqslant \tfrac{{(S_1 - 2)}}{2}or\tfrac{{(S_2 - 2)}}{2}] , an order will be placed for (S ⁱ −s) units of i-th commodity(i=1,2). The probability distribution for inventory level and mean reorders and shortage rates in the steady state are computed. Numerical illustrations of the results are also provided.     

An unexpected separation result in Linearly Bounded Arithmetic

The theories Sⁱ₁(α) and Tⁱ₁(α) are the analogues of Buss' relativized bounded arithmetic theories in the language where every term is bounded by a polynomial, and thus all definable functions grow linearly in length. For every i, a Σ^b_i+1(α)‐formula TOPⁱ(a), which expresses a form of the total ordering principle, is exhibited that is provable in Sⁱ⁺¹₁ (α), but unprovable in Tⁱ₁(α). This is in contrast with the classical situation, where Sⁱ⁺¹₂ is conservative over Tⁱ₂ w. r. t. Σ^b_i+1‐sentences. The independence results are proved by translations into propositional logic, and using lower bounds for corresponding propositional proof systems. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

On the Common Substring Alignment Problem

The Common Substring Alignment Problem is defined as follows: Given a set of one or more strings S₁, S₂ … S_c and a target string T, Y is a common substring of all strings S_i, that is, S_i = B_iYF_i. The goal is to compute the similarity of all strings S_i with T, without computing the part of Y again and again. Using the classical dynamic programming tables, each appearance of Y in a source string would require the computation of all the values in a dynamic programming table of size O(nℓ) where ℓ is the size of Y. Here we describe an algorithm which is composed of an encoding stage and an alignment stage. During the first stage, a data structure is constructed which encodes the comparison of Y with T. Then, during the alignment stage, for each comparison of a source S_i with T, the pre-compiled data structure is used to speed up the part of Y. We show how to reduce the O(nℓ) alignment work, for each appearance of the common substring Y in a source string, to O(n)-at the cost of O(nℓ) encoding work, which is executed only once.     

Complexity analysis and optimization of the shortest path tour problem

The shortest path tour problem (SPTP) consists in finding a shortest path from a given origination node s to a given destination node d in a directed graph with nonnegative arc lengths with the constraint that the optimal path P should successively and sequentially pass through at least one node from given node subsets T ₁, T ₂, . . . , T _N , where T_i ?T_j = ?, " i, j=1,?,N, i 1 j{T_i \cap T_j = \emptyset, \forall\ i, j=1,\ldots,N,\ i \neq j}. In this paper, it will proved that the SPTP belongs to the complexity class P and several alternative techniques will be presented to solve it.     

A constructive method for the solution of the stability problem

Summary In this paper it is shown that the problem of solving the Liapounov matrix equationSM +M ^T S = –I is greatly simplified when the given real matrixM is in upper Hessenberg form. The solution is obtained as a linear combinationS = p _i S _i ofn linearly independent symmetric matricesS _i , whereS _i M +M ^T S _i =2D _i and p _i D _i = –1/2I. Explicit formulae are given for the elements of theS _i , andD _i while determination of thep _i requires the solution of ann ×n linear system.     

Topological realizations of families of ergodic automorphisms, multitowers and orbit equivalence

We study minimal topological realizations of families of ergodic measure preserving automorphisms (e.m.p.a.'s). Our main result is the following theorem. Theorem: Let {T_p:p∈I} be an arbitrary finite or countable collection of e.m.p.a.'s on nonatomic Lebesgue probability spaces (Y _p v _p ). Let S be a Cantor minimal system such that the cardinality of the set ε _S of all ergodic S-invariant Borel probability measures is at least the cardinality of I. Then for any collection {μ _p :pεI} of distinct measures from ε _S there is a Cantor minimal system S′ in the topological orbit equivalence class of S such that, as a measure preserving system, (S ¹,μ _p ) is isomorphic to T_p for every p∈I. Moreover, S′ can be chosen strongly orbit equivalent to S if and only if all finite topological factors of S are measure-theoretic factors of T_p for all p∈I. This result shows, in particular, that there are no restrictions at all for the topological realizations of countable families of e.m.p.a.'s in Cantor minimal systems. Namely, for any finite or countable collection {T ₁,T₂,…} of e.m.p.a.'s of nonatomic Lebesgue probability spaces, there is a Cantor minimal systemS, whose collection {μ1,μ2…} of ergodic Borel probability measures is in one-to-one correspondence with {T ₁,T₂,…}, and such that (S,μ _i ) is isomorphic toT _i for alli. Furthermore, since realizations are taking place within orbit equivalence classes of a given Cantor minimal system, our results generalize the strong orbit realization theorem and the orbit realization theorem of [18]. Those theorems are now special cases of our result where the collections {T _p}, {T _p }{μ _p } consist of just one element each. Research of I.K. was supported by NSF grant DMS 0140068.     

Differential equations related to the Williams-Bjerknes tumour model

We investigate an initial value problem which is closely related to the Williams-Bjerknes tumour model for a cancer which spreads through an epithelial basal layer modeled onI ⊂ Z ². The solution of this problem is a familyp = (p _i(t)), where eachp _i(t)could be considered as an approximation to the probability that the cell situated ati is cancerous at timet. We prove that this problem has a unique solution, it is defined on [0, +∞[, and, for some relevant situations, lim_t→∞ P _i(t) = 1 for alli ∈ I. Moreover, we study the expected number of cancerous cells at timet.     

Perfect Partitions of Convex Sets in the Plane

Abstract. For a region X in the plane, we denote by area(X) the area of X and by ℓ (∂ (X)) the length of the boundary of X . Let S be a convex set in the plane, let n ≥ 2 be an integer, and let α ₁ , α ₂ , . . . ,α _n be positive real numbers such that α ₁ +α ₂ + ⋅ ⋅ ⋅ +α _n =1 and 0< α _i ≤ 1/2 for all 1 ≤ i ≤ n . Then we shall show that S can be partitioned into n disjoint convex subsets T ₁ , T ₂ , . . . ,T _n so that each T _i satisfies the following three conditions: (i) area(T _i )=α _i × area(S) ; (ii) ℓ (T _i ∩ ∂ (S))= α _i × ℓ (∂ (S)) ; and (iii) T _i ∩ ∂ (S) consists of exactly one continuous curve.     

Perfect Partitions of Convex Sets in the Plane

   Abstract. For a region X in the plane, we denote by area(X) the area of X and by ℓ (∂ (X)) the length of the boundary of X . Let S be a convex set in the plane, let n ≥ 2 be an integer, and let α ₁ , α ₂ , . . . ,α _n be positive real numbers such that α ₁ +α ₂ + ⋅ ⋅ ⋅ +α _n =1 and 0< α _i ≤ 1/2 for all 1 ≤ i ≤ n . Then we shall show that S can be partitioned into n disjoint convex subsets T ₁ , T ₂ , . . . ,T _n so that each T _i satisfies the following three conditions: (i) area(T _i )=α _i × area(S) ; (ii) ℓ (T _i ∩ ∂ (S))= α _i × ℓ (∂ (S)) ; and (iii) T _i ∩ ∂ (S) consists of exactly one continuous curve.     

Diperfect graphs

Gallai and Milgram have shown that the vertices of a directed graph, with stability number α(G), can be covered by exactly α(G) disjoint paths. However, the various proofs of this result do not imply the existence of a maximum stable setS and of a partition of the vertex-set into paths μ₁, μ₂, ..., μ_k such tht |μ_i ∩S|=1 for alli. Later, Gallai proved that in a directed graph, the maximum number of vertices in a path is at least equal to the chromatic number; here again, we do not know if there exists an optimal coloring (S ₁,S ₂, ...,S _k) and a path μ such that |μ ∩S _i|=1 for alli. In this paper we show that many directed graphs, like the perfect graphs, have stronger properties: for every maximal stable setS there exists a partition of the vertex set into paths which meet the stable set in only one point. Also: for every optimal coloring there exists a path which meets each color class in only one point. This suggests several conjecties similar to the perfect graph conjecture. Dedicated to Tibor Gallai on his seventieth birthday     

Non-induced isomorphisms of matrix rings

We give examples of distinct integersi, j, and ringsT for which the matrix ringsM _i (T) andM _j (T) are isomorphic as rings, but for which the free modules _T T ⁽ⁱ⁾ and _T T ⁽ⁱ⁾ are non-isomorphic asT-modules.     

Complexity of the pipeline computation of a family of inner products

We are interested in the minimum time T(S) necessary for computing a family S = { < S_i, S_j >: ? S_i, S_j?R^p, (i, j) ?E } of inner products of order p, on a systolic array of order p × 2. We first prove that the determination of T(S) is equivalent to the partition problem and is thus NP-complete. Then we show that the designing of an algorithm which runs in time T(S) + 1 is equivalent to the problem of finding an undirected bipartite eulerian multigraph with the smallest number of edges, which contains a given undirected bipartite graph, and can therefore be solved in polynomial time.     

Cyclic Just-In-Time Sequences Are Optimal

Consider the Product Rate Variation problem. Given n products 1,...,i,...,n, and n positive integer demands d ₁,..., d_i,...,d_n. Find a sequence =₁,...,_T, T = _i=1 ⁿ d _i, of the products, where product i occurs exactly d _i times that always keeps the actual production level, equal the number of product i occurrences in the prefix ₁,..., _t, t=1,...,T, and the desired production level, equal r _i t, where r _i=d_i/T, of each product i as close to each other as possible. The problem is one of the most fundamental problems in sequencing flexible just-in-time production systems. We show that if is an optimal sequence for d ₁,...,d_i,...,d_n, then concatenation ^m of m copies of is an optimal sequence for md ₁,..., md_i,...,md_n.