Resource augmented semi-online bounded space bin packing

We study on-line bounded space bin-packing in the resource augmentation model of competitive analysis. In this model, the on-line bounded space packing algorithm has to pack a list L of items with sizes in (0, 1], into a minimum number of bins of size b, b≥1. A bounded space algorithm has the property that it only has a constant number of active bins available to accept items at any point during processing. The performance of the algorithm is measured by comparing the produced packing with an optimal offline packing of the list L into bins of size 1. The competitive ratio then becomes a function of the on-line bin size b. Csirik and Woeginger studied this problem in [J. Csirik, G.J. Woeginger, Resource augmentation for online bounded space bin packing, Journal of Algorithms 44(2) (2002) 308-320] and proved that no on-line bounded space algorithm can perform better than a certain bound ρ(b) in the worst case. We relax the on-line condition by allowing a complete repacking within the active bins, and show that the same lower bound holds for this problem as well, and repacking may only allow one to obtain the exact best possible competitive ratio of ρ(b) having a constant number of active bins, instead of achieving this bound in the limit. We design a polynomial time on-line algorithm that uses three active bins and achieves the exact best possible competitive ratio ρ(b) for the given problem.     

Some Schroeder-Bernstein type theorems for Banach spaces

We first introduce the notion of (p,q,r)-complemented subspaces in Banach spaces, where p,q,r∈N. Then, given a couple of triples {(p,q,r),(s,t,u)} in N and putting Λ=(q+r−p)(t+u−s)−ru, we prove partially the following conjecture: For every pair of Banach spaces X and Y such that X is (p,q,r)-complemented in Y and Y is (s,t,u)-complemented in X, we have that X is isomorphic Y if and only if one of the following conditions holds:

(a)

Λ≠0, Λ divides p−q and s−t, p=1 or q=1 or s=1 or t=1.

(b)

p=q=s=t=1 and gcd(r,u)=1.

The case {(2,1,1),(2,1,1)} is the well-known Pe?czyński's decomposition method. Our result leads naturally to some generalizations of the Schroeder-Bernstein problem for Banach spaces solved by W.T. Gowers in 1996.     

Mappings between Banach spaces that send mixed summable sequences into absolutely summable sequences

In this work we study mappings f from an open subset A of a Banach space E into another Banach space F such that, once a∈A is fixed, for mixed (s;q)-summable sequences of elements of a fixed neighborhood of 0 in E, the sequence is absolutely p-summable in F. In this case we say that f is (p;m(s;q))-summing at a. Since for s=q the mixed (s;q)-summable sequences are the weakly absolutely q-summable sequences, the (p;m(q;q))-summing mappings at a are absolutely (p;q)-summing mappings at a. The nonlinear absolutely summing mappings were studied by Matos (see [Math. Nachr. 258 (2003) 71-89]) in a recent paper, where one can also find the historical background for the theory of these mappings. When s=+∞, the mixed (∞,q)-summable sequences are the absolutely q-summable sequences. Hence the (p;m(∞;q))-summing mappings at a are the regularly (p;q)-summing mappings at a. These mappings were also studied in [Math. Nachr. 258 (2003) 71-89] and they were important to give a nice characterization of the absolutely (p;q)-summing mappings at a. We show that for q<s<+∞ the space of the (p;m(s;q))-summing mappings at a are different from the spaces of the absolutely (p;q)-summing mappings at a and different from the spaces of regularly (p;q)-summing mappings at a. We prove a version of the Dvoretzky-Rogers theorem for n-homogeneous polynomials that are (p;m(s;q))-summing at each point of E. We also show that the sequence of the spaces of such n-homogeneous polynomials, n∈N, gives a holomorphy type in the sense of Nachbin. For linear mappings we prove a theorem that gives another characterization of (s;q)-mixing operators in terms of quotients of certain operators ideals.     

Newtonian and Schinzel sequences in a domain

A Schinzel or F sequence in a domain is such that, for every ideal I with norm q, its first q terms form a system of representatives modulo I, and a Newton or N sequence such that the first q terms serve as a test set for integer-valued polynomials of degree less than q. Strong F and strong N sequences are such that one can use any set of q consecutive terms, not only the first ones, finally a very well F ordered sequence, for short, a V.W.F sequence, is such that, for each ideal I with norm q, and each integer s,{u_sq,…,u_(s+1)q−1} is a complete set of representatives modulo I. In a quasilocal domain, V.W.F sequences and N sequences are the same, so are strong F and strong N sequences. Our main result is that a strong N sequence is a sequence which is locally a strong F sequence, and an N sequence a sequence which is locally a V.W.F. sequence. We show that, for F sequences there is a bound on the number of ideals of a given norm. In particular, a sequence is a strong F sequence if and only if it is a strong N sequence and for each prime p, there is at most one prime ideal with finite residue field of characteristic p. All results are refined to sequences of finite length.     

Blow-up behavior for a nonlinear heat equation with a localized source in a ball

In this paper, we consider the initial-boundary value problem of a semilinear parabolic equation with local and non-local (localized) reactions in a ball: u_t=Δu+u^p+u^q(x^*,t) in B(R) where p,q>0,B(R)={x∈R^N:|x|<R} and x^*≠0. If max(p,q)>1, there exist blow-up solutions of this problem for large initial data. We treat the radially symmetric and one peak non-negative solution of this problem. We give the complete classification of total blow-up phenomena and single point blow-up phenomena according to p and q.

(i)

If or p=q>2, then single point blow-up occurs whenever solutions blow up.

(ii)

If 1<p<q, both phenomena, total blow-up and single point blow-up, occur depending on the initial data.

(iii)

If p?1<q, total blow-up occurs whenever solutions blow up.

(iv)

If max(p,q)?1, every solution exists globally in time.

     

A 17/10-approximation algorithm fork-bounded space on-line variable-sized bin packing

A version of thek-bounded space on-line bin packing problem, where a fixed collection of bin sizes is allowed, is considered. By packing large items into appropriate bins and closing appropriate bins, we can derive an algorithm with worst-case performance bound 1.7 fork≥3. This research is supported by the Science Foundation under State Education Committee of China. The earlier version was done in Institute of Applied Mathematics, Academia Sinica.     

Improved Dynamic Text Indexing

In the dynamic text indexing problem, a text string has to be maintained under string insertions and deletions in order to answer on-line queries about arbitrary pattern occurrences. By means of some new techniques and data structures, we achieve improved worst-case bounds. We show that finding allpoccoccurrences of a pattern of lengthpin the current text of lengthntakesO(p + pocc + updlog p + log n) time, whereupdis the number of text uptakes performed so far; inserting or deleting a string of lengthsfrom the current text takesO(s log(s + n)) time.     

A linear time approximation algorithm for movement minimization in conveyor flow shop processing

We consider the movement minimization problem in a conveyor flow shop processing controlled by one worker for all machines. A machine can only execute tasks if the worker is present. Each machine can serve as a buffer. The worker has to cover a certain distance to move from one machine to the other. The distance between two machines P_p and P_q is |p−q|. The objective is to minimize the total distance the worker has to cover for the processing of all jobs. We introduce a linear time approximation algorithm for the conveyor flow shop problem with performance 3. Such minimization problems usually appear in conveyor controlled manufacturing systems.     

On the distribution properties of Niederreiter-Halton sequences

We study the distribution properties of sequences which are a generalization of the well-known van der Corput-Halton sequence on the one hand, and digital (T,s)-sequences in the sense of Niederreiter on the other. In this paper we completely answer the question under which conditions such a sequence is uniformly distributed in the s-dimensional unit cube, by using methods based on the q-additive property of the weighted q-ary sum-of-digits function.     

On the depth of a planar graph

In this paper, we have defined the concept of the depth of a planar graph. We show that, if G is a simple finite planar graph with p vertices and q edges and q > 3(p ? 1) ? p/2^s?1, then the depth of G is at least equal to s.     

On-line scheduling on a batch processing machine with unbounded batch size to minimize the makespan

We present on-line algorithms to minimize the makespan on a single batch processing machine. We consider a parallel batching machine that can process up to b jobs simultaneously. Jobs in the same batch complete at the same time. Such a model of a batch processing machine has been motivated by burn-in ovens in final testing stage of semiconductor manufacturing. We deal with the on-line scheduling problem when jobs arrive over time. We consider a set of independent jobs. Their number is not known in advance. Each job is available at its release date and its processing requirement is not known in advance. This general problem with infinite machine capacity is noted 1∣p − batch, r_j, b = ∞∣C_max. Deterministic algorithms that do not insert idle-times in the schedule cannot be better than 2-competitive and a simple rule based on LPT achieved this bound [Z. Liu, W. Yu, Scheduling one batch processor subject to job release dates, Discrete Applied Mathematics 105 (2000) 129–136]. If we are allowed to postpone start of jobs, the performance guarantee can be improved to 1.618. We provide a simpler proof of this best known lower bound for bounded and unbounded batch sizes. We then present deterministic algorithms that are best possible for the problem with unbounded batch size (i.e., b = ∞) and agreeable processing times (i.e., there cannot exist an on-line algorithm with a better performance guarantee). We then propose another algorithm that leads to a best possible algorithm for the general problem with unbounded batch size. This algorithm improves the best known on-line algorithm (i.e. [G. Zhang, X. Cai, C.K. Wong, On-line algorithms for minimizing makespan on batch processing machines, Naval Research Logistics 48 (2001) 241–258]) in the sense that it produces a shortest makespan while ensuring the same worst-case performance guarantee.     

Flat cyclotomic polynomials of order three

We say that a cyclotomic polynomial Φn has order three if n is the product of three distinct primes, p<q<r. Let A(n) be the largest absolute value of a coefficient of Φn. For each pair of primes p<q, we give an infinite family of r such that A(pqr)=1. We also prove that A(pqr)=A(pqs) whenever s>q is a prime congruent to .     

Minimum product set sizes in nonabelian groups of order pq

Let G be a nonabelian group of order pq, where p and q are distinct odd primes. We analyze the minimum product set cardinality μG(r,s)=min|AB|, where A and B range over all subsets of G of cardinalities r and s, respectively. In this paper, we completely determine μG(r,s) in the case where G has order 3p and conjecture that this result can be extended to all nonabelian groups of order pq. We also prove that for every nonabelian group of order pq there exist 1?r,s?pq such that μG(r,s)>μZ/pqZ(r,s).     

Integral trees of diameter 6

A graph G is called integral if all eigenvalues of its adjacency matrix A(G) are integers. In this paper, the trees T(p,q)•T(r,m,t) and K_1,s•T(p,q)•T(r,m,t) of diameter 6 are defined. We determine their characteristic polynomials. We also obtain for the first time sufficient and conditions for them to be integral. To do so, we use number theory and apply a computer search. New families of integral trees of diameter 6 are presented. Some of these classes are infinite. They are different from those in the existing literature. We also prove that the problem of finding integral trees of diameter 6 is equivalent to the problem of solving some Diophantine equations. We give a positive answer to a question of Wang et al. [Families of integral trees with diameters 4, 6 and 8, Discrete Appl. Math. 136 (2004) 349-362].     

Labeling bipartite permutation graphs with a condition at distance two

An L(p,q)-labeling of a graph G is an assignment f from vertices of G to the set of non-negative integers {0,1,…,λ} such that |f(u)−f(v)|≥p if u and v are adjacent, and |f(u)−f(v)|≥q if u and v are at distance 2 apart. The minimum value of λ for which G has L(p,q)-labeling is denoted by λ_p,q(G). The L(p,q)-labeling problem is related to the channel assignment problem for wireless networks.In this paper, we present a polynomial time algorithm for computing L(p,q)-labeling of a bipartite permutation graph G such that the largest label is at most (2p−1)+q(bc(G)−2), where bc(G) is the biclique number of G. Since λ_p,q(G)≥p+q(bc(G)−2) for any bipartite graph G, the upper bound is at most p−1 far from optimal.     

Enumeration of labelled multigraphs by degree parities

Counting formulae are obtained for the numbers of labelled (p,q)-multigraphs with any even number n of points of odd degree and p-n points of even degree. Similar results are obtained for multigraphs of strength s, and in this case for the sum over the number q of lines. These sums are much less simple if s is even than if s is odd. However, it is shown that for s fixed, and p → ∞, the asymptotic value does not depend on the parity of s.     

The existence of (p,q)-extended Rosa sequences

A (p,q)-extended Rosa sequence is a sequence of length 2n+2 containing each of the symbols 0,1,…,n exactly twice, and such that two occurrences of the integer j>0 are separated by exactly j-1 symbols. We prove that, with two exceptions, the conditions necessary for the existence of a (p,q)-extended Rosa sequence with prescribed positions of the symbols 0 are sufficient. We also extend the result to λ-fold (p,q)-extended Rosa sequences; i.e., the sequences where every pair of numbers is repeated exactly λ times.     

A method for finding coefficients of a quasilinear hyperbolic equation

The inverse problem of finding the coefficients q(s) and p(s) in the equation u _tt = a ² u _xx + q(u)u _t ? p(u)u _x is investigated. As overdetermination required in the inverse setting, two additional conditions are set: a boundary condition and a condition with a fixed value of the timelike variable. An iteration method for solving the inverse problem is proposed based on an equivalent system of integral equations of the second kind. A uniqueness theorem and an existence theorem in a small domain are proved for the inverse problem to substantiate the convergence of the algorithm.     

Linear feedback systems and the groups of Galois and Lie

Our purpose in this paper is to delineate precisely the extent to which one can make explicit calculations involving the most basic linear feedback systems. Our results center around the Galois theory of the “root-locus” equation p(s) + kq(s) = 0 and the Lie symmetries associated with the related differential equation p(D)x + k(t)q(D)x = 0, D = d/dt. We show that the Galois theory leads to a more refined classification, but that these theories are related in a substantial way. Considerable insight into this is obtained through the study of the monodromy group associated with algebraic curve defined by p(s) + kq(s) = 0.