Utilizing Shelve Slots: Sufficiency Conditions for Some Easy Instances of Hard Problems

In this paper we present a minimal set of conditions sufficient to assure the existence of a solution to a system of nonnegative linear diophantine equations. More specifically, suppose we are given a finite item set U = {u₁, u₂, . . . , u_k} together with a "size" v_i ≡ v(u_i) ∈ Z⁺, such that v_i ≠ v_j for i ≠ j, a "frequency" a_i ≡ a(u_i) ∈ Z⁺, and a positive integer (shelf length) L ∈ Z⁺ with the following conditions: (i) L = ∏ⁿ_j=1p_j(p_j ∈ Z⁺ ∀j, p_j ≠ p_l for j ≠ l) and v_i = ∏ _j∈Aip_j, A_i ⊆ {l, 2, . . . , n} for i = 1, . . . , n; (ii) (A_i\{⋂^k_j=1A_j}) ∩ (A_l\{⋂^k_j=1A_j}) = ⊘∀i ≠ l. Note that v_i|L (divides L) for each i. If for a given m ∈ Z⁺, ∑ⁿ_i=1a_iv_i = mL (i.e., the total size of all the items equals the total length of the shelf space), we prove that conditions (i) and (ii) are sufficient conditions for the existence of a set of integers {b₁₁, b₁₂, . . . , b_1m, b₂₁, . . . , b_n1, . . . , b_nm}⊆ N such that ∑^m_j=1b_ij = a_i, i = 1, . . . , k, and ∑^k_i=1b_ijv_i = L, j =1, . . . , m (i.e., m shelves of length L can be fully utilized). We indicate a number of special cases of well known NP-complete problems which are subsequently decided in polynomial time.     

On ARX(∞) approximation

Given data, u_j,y_j,j=1,…,n, with u_j an input sequence to a system while output is y_j, an approximation to the structure of the system generating y_j is to be obtained by regressing y_j on u_j−i,y_j−ii=1,…,p_n, where p_n increases with n. In this paper the rate of convergence of the coefficient matrices to their asymptotic values is discussed. The context is kept general so that, in particular, u_j is allowed to depend on y_i, i≤j, and no assumption of stationarity for the y_j or u_j sequences is made.     

Singular perturbation problems for systems of partial differential equations of elliptic type

Elliptic boundary value problems for systems of nonlinear partial differential equations of the form $\text{F}{}_{\mathrm{i}}\text{(x, u}{}_1\text{, u}{}_2\text{,…, u}{}_{\mathrm{N}}\text{,}\text{?u}{}_{\mathrm{i}}\text{?x}{}_{\mathrm{j}}\text{, ?}{}^{\mathrm{p}}{}_{\mathrm{i}}\text{?}{}^2\text{u}{}_{\mathrm{i}}\text{?x}{}_{\mathrm{j}}\text{?x}{}_{\mathrm{k}}\text{) = ?}{}_{\mathrm{i}}\text{(x), x ? R}{}^{\mathrm{n}}$, i = 1(1)N, j, k = 1(1)n, p_i ? 0, ? being a small parameter, with Dirichlet boundary conditions are considered. It is supposed that a formal approximation Z is given which satisfies the boundary conditions and the differential equations upto the order χ(?) = o(1) in some norm. Then, using the theory of differential inequalities, it is shown that under certain conditions the difference between the exact solution u of the boundary value problem and the formal approximation Z, taken in the sense of a suitable norm, can be made small.     

Discrete Toda lattices and the Laplace method

We apply the Laplace cascade method to systems of discrete equations of the form u _i+1,j+1 = f(u _i+1,j , u _i,j+1, u _i,j , u _i,j?1), where u _ij , i, j ∈ ?, is an element of a sequence of unknown vectors. We introduce the concept of a generalized Laplace invariant and the related property that the systems is “of the Liouville type.” We prove a series of statements about the correctness of the definition of the generalized invariant and its applicability for seeking solutions and integrals of the system. We give some examples of systems of the Liouville type.     

The almost split triangles for perfect complexes over gentle algebras

Throughout the paper k denotes a fixed field. All vector spaces and linear maps are k-vector spaces and k-linear maps, respectively. By Z, N, and N₊, we denote the sets of integers, nonnegative integers, and positive integers, respectively. For i,j∈Z, [i,j]:={l∈Z∣i≤l≤j} (in particular, [i,j]=∅ if i>j).     

Nash-solvable two-person symmetric cycle game forms

A two-person positional game form g (with perfect information and without moves of chance) is modeled by a finite directed graph (digraph) whose vertices and arcs are interpreted as positions and moves, respectively. All simple directed cycles of this digraph together with its terminal positions form the set A of the outcomes. Each non-terminal position j is controlled by one of two players i∈I={1,2}. A strategy x_i of a player i∈I involves selecting a move (j,j^′) in each position j controlled by i. We restrict both players to their pure positional strategies; in other words, a move (j,j^′) in a position j is deterministic (not random) and it can depend only on j (not on preceding positions or moves or on their numbers). For every pair of strategies (x₁,x₂), the selected moves uniquely define a play, that is, a directed path form a given initial position j₀ to an outcome (a directed cycle or terminal vertex). This outcome a∈A is the result of the game corresponding to the chosen strategies, a=a(x₁,x₂). Furthermore, each player i∈I={1,2} has a real-valued utility function u_i over A. Standardly, a game form g is called Nash-solvable if for every u=(u₁,u₂) the obtained game (g,u) has a Nash equilibrium (in pure positional strategies).A digraph (and the corresponding game form) is called symmetric if (j,j^′) is its arc whenever (j^′,j) is. In this paper we obtain necessary and sufficient conditions for Nash-solvability of symmetric cycle two-person game forms and show that these conditions can be verified in linear time in the size of the digraph.     

Netlike partial cubes III. The median cycle property

A graph G has the Median Cycle Property (MCP) if every triple (u₀,u₁,u₂) of vertices of G admits a unique median or a unique median cycle, that is a gated cycle C of G such that for all i,j,k∈{0,1,2}, if x_i is the gate of u_i in C, then: {x_i,x_j}⊆I_G(u_i,u_j) if i≠j, and d_G(x_i,x_j)<d_G(x_i,x_k)+d_G(x_k,x_j). We prove that a netlike partial cube has the MCP if and only if it contains no triple of convex cycles pairwise having an edge in common and intersecting in a single vertex. Moreover a finite netlike partial cube G has the MCP if and only if G can be obtained from a set of even cycles and hypercubes by successive gated amalgamations, and equivalently, if and only if G can be obtained from K₁ by a sequence of special expansions. We also show that the geodesic interval space of a netlike partial cube having the MCP is a Pash-Peano space (i.e. a closed join space).     

Constant‐sign solutions for singular systems of Fredholm integral equations

We consider the system of Fredholm integral equations where T>0 is fixed and the nonlinearities H_i(t, u₁, u₂, …, u_n) can be singular at t=0 and u_j=0 where j∈{1, 2, …, n}. Criteria are offered for the existence of constant‐sign solutions, i.e. θ_iu_i(t)≥0 for t∈[0, 1] and 1≤i≤n, where θ_i∈{1,?1} is fixed. We also include an example to illustrate the usefulness of the results obtained. Copyright © 2010 John Wiley & Sons, Ltd.     

Job shop scheduling with unit time operations under resource constraints and release dates

We consider the problem of job shop scheduling with m machines and n jobs J_i, each consisting of l_i unit time operations. There are s distinct resources R_h and a quantity q_h available of each one. The execution of the j-th operation of J_i requires the presence of u_ijh units of R_h, 1 ≤i≤n, 1 ≤j≤l_i, and 1 ≤h≤s. In addition, each J_i has a release date r_i, that is J_i cannot start before time r_i. We describe algorithms for finding schedules having minimum length or sum of completion times of the jobs. Let l=max{l_i} and u=|{u_ijh}|. If m, u and l are fixed, then both algorithms terminate within polynomial time.     

Two equivalent measures on weighted hypergraphs

Let H=(N,E,w) be a hypergraph with a node set N={0,1,…,n-1}, a hyperedge set E⊆2^N, and real edge-weights w(e) for e∈E. Given a convex n-gon P in the plane with vertices x₀,x₁,…,x_n-1 which are arranged in this order clockwisely, let each node i∈N correspond to the vertex x_i and define the area A_P(H) of H on P by the sum of the weighted areas of convex hulls for all hyperedges in H. For 0?i<j<k?n-1, a convex three-cut C(i,j,k) of N is {{i,…,j-1}, {j,…,k-1}, {k,…,n-1,0,…,i-1}} and its size c_H(i,j,k) in H is defined as the sum of weights of edges e∈E such that e contains at least one node from each of {i,…,j-1}, {j,…,k-1} and {k,…,n-1,0,…,i-1}. We show that the following two conditions are equivalent:

•

A_P(H)?A_P(H^′) for all convex n-gons P.

•

c_H(i,j,k)?c_H^′(i,j,k) for all convex three-cuts C(i,j,k).

From this property, a polynomial time algorithm for determining whether or not given weighted hypergraphs H and H^′ satisfy “A_P(H)?A_P(H^′) for all convex n-gons P” is immediately obtained.     

Identification of parameters by the distribution of the maximum random variable: The general multivariate normal case

Summary LetX ₁,X ₂, ...,X _r ber independentn-dimensional random vectors each with a non-singular normal distribution with zero means and positive partial correlations. Suppose thatX _i =(X _i1 , ...,X _in ) and the random vectorY=(Y ₁, ...,Y _n ), their maximum, is defined byY _j =max{X _ij :1ir}. LetW be another randomn-vector which is the maximum of another such family of independentn-vectorsZ ₁,Z ₂, ...,Z _s . It is then shown in this paper that the distributions of theZ _i 's are simply a rearrangement of those of theZ _j 's (and of course,r=s), whenever their maximaY andW have the same distribution. This problem was initially studied by Anderson and Ghurye [2] in the univariate and bivariate cases and motivated by a supply-demand problem in econometrics.     

Characterization of the absence of a spectral gapfor a class of periodic Jacobi operators

Let q ∈ {2, 3} and let 0 = s₀ < s₁ < … < s_q = T be integers. For m, n ∈ Z, we put ¯m,n = {j ∈ Z| m? j ? n}. We set l_j = s_j − s_j−1 for j ∈ 1, q. Given (p₁,, p_q) ∈ R^q, let b: Z → R be a periodic function of period T such that b(·) = p_j on s_j−1 + 1, s_j for each j ∈ 1, q. We study the spectral gaps of the Jacobi operator (Ju)(n) = u(n + 1) + u(n − 1) + b(n)u(n) acting on l²(Z). By [λ_2j , λ_2j−1] we denote the jth band of the spectrum of J counted from above for j ∈ 1, T. Suppose that p_m ≠ p_n for m ≠ n. We prove that the statements (i) and (ii) below are equivalent for λ ∈ R and i ∈ 1, T − 1.     

On Ochoa's special matrices in matrix classes

It is well known that the ideal classes of an order Z[μ], generated over Z by the integral algebraic number μ, are in a bijective correspondence with certain matrix classes, that is, classes of unimodularly equivalent matrices with rational integer coefficients. If the degree of μ is ?3, we construct explicitly a particularly simple ideal matrix for an ideal which is a product of different prime ideals of degree 1. We obtain the following special n×n matrix (c_ij) in the matrix class corresponding to the ideal class of our ideal: c_i+1,_i=1(i=1,…,n?2); c_ij=0(?i?n, 1?j?n? 2, and i≠j+1); c_nj=0(j)=2,…,n?1). The remaining coefficients are given as explicit polynomials in an integer z which depends on the ideal. It is shown that the matrix class of every regular ideal class of Z[μ] contains a special matrix of this kind.     

Hardy’s theorem for zeta-functions of quadratic forms

LetQ(u ₁,…,u ₁) =Σd _ij u _i u _j (i,j = 1 tol) be a positive definite quadratic form inl(≥3) variables with integer coefficientsd _ij (=d _ji ). Puts=σ+it and for σ>(l/2) write $$Z_Q (s) = \Sigma '(Q(u_1 ,...,u_l ))^{ - s} ,$$ where the accent indicates that the sum is over alll-tuples of integer (u ₁,…,u _l ) with the exception of (0,…, 0). It is well-known that this series converges for σ>(l/2) and that (s-(l/2))Z _Q (s) can be continued to an entire function ofs. Let σ be any constant with 0<σ<1/100. Then it is proved thatZ _Q (s)has ?_δTlogT zeros in the rectangle(|σ-1/2|≤δ, T≤t≤2T).     

The asymptotic ruin problem when the healthy and sick periods form an alternating renewal process

Let {T₁, Y₁}^∞_i=1 be a sequence of positive independent random variables. Let, also, Z₁ = βY′₁ ? πT_i, i = 1, 2, …, where Y′₁ = Max(0, Y_i ? w), w ? 0, and where β < 0 and π is such that E(Z₁) < 0. We consider the random walk of partial sums S_n = ?ⁿ_i=1Z_i in the presence of an absorbing region (u, ∞), u ? 0, and S₀ ≡ 0. Of interest is $\text{ψ(u) = Pr(}\text{S}\text{?}\text{≤ u)}$ where S? = Sup(0, S₁, S₂, …, S_n, …).     

Outsourcing and scheduling for two-machine ordered flow shop scheduling problems

This paper considers a two-machine ordered flow shop problem, where each job is processed through the in-house system or outsourced to a subcontractor. For in-house jobs, a schedule is constructed and its performance is measured by the makespan. Jobs processed by subcontractors require paying an outsourcing cost. The objective is to minimize the sum of the makespan and the total outsourcing cost. Since this problem is NP-hard, we present an approximation algorithm. Furthermore, we consider three special cases in which job j has a processing time requirement p_j, and machine i a characteristic q_i. The first case assumes the time job j occupies machine i is equal to the processing requirement divided by a characteristic value of machine i, that is, p_j/q_i. The second (third) case assumes that the time job j occupies machine i is equal to the maximum (minimum) of its processing requirement and a characteristic value of the machine, that is, max{p_j, q_i} (min{p_j, q_i}). We show that the first and the second cases are NP-hard and the third case is polynomially solvable.     

Global Hölder continuity of weak solutions to quasilinear divergence form elliptic equations

We derive global Hölder regularity for the -weak solutions to the quasilinear, uniformly elliptic equation

div(aij(x,u)Dju+ai(x,u))+a(x,u,Du)=0     

Monotonicity of quotients of theta functions related to an extremal problem on harmonic measure

We prove that for fixed u and v such that u,v∈[0,1/2), the quotients θj(u|iπt)/θj(v|iπt), j=1,2,3,4, of the theta functions are monotone on 0<t<∞. The case v=0 has been used by the second author to study a generalization of Gonchar's problem on harmonic measure of radial slits.     

Hamiltonian cycles in 2-connected claw-free-graphs

M. Matthews and D. Sumner have proved that of G is a 2-connected claw-free graph of order n such that δ ≧ (n ? 2)/3, then G is hamiltonian. We prove that the bound for the minimum degree δ can be reduced to n/4 under the additional condition that G is not in F, where F is the set of all graphs defined as follows: any graph H in F can be decomposed into three vertex disjoint subgraphs H₁, H₂, H₃ such that , where u_i, v_i ? V(H_i), u_j v_j ? V(H_j) 1 ? i ≦ j ≦ 3. Examples are given to show that the bound n/4 is sharp. © 1995 John Wiley & Sons, Inc.     

On the average genus of the random graph

The generalized Petersen graph GP (n, k), n ≤ 3, 1 ≥ k < n/2 is a cubic graph with vertex-set {u_j; i ? Z_n} ∪ {v_j; i ? Z_n}, and edge-set {u_iu_i, u_iv_i, v_iv_{i+k, i?}Z_n}. In the paper we prove that (i) GP(n, k) is a Cayley graph if and only if k² ? 1 (mod n); and (ii) GP(n, k) is a vertex-transitive graph that is not a Cayley graph if and only if k² ? -1 (mod n) or (n, k) = (10, 2), the exceptional graph being isomorphic to the 1-skeleton of the dodecahedon. The proof of (i) is based on the classification of orientable regular embeddings of the n-dipole, the graph consisting of two vertices and n parallel edges, while (ii) follows immediately from (i) and a result of R. Frucht, J.E. Graver, and M.E. Watkins [“The Groups of the Generalized Petersen Graphs,” Proceedings of the Cambridge Philosophical Society, Vol. 70 (1971), pp. 211-218]. © 1995 John Wiley & Sons, Inc.