Comments on “Scheduling jobs on a k-stage flexible flow-shop” [Annals of Operations Research (2008) 164: 29–40]

The problem of makespan minimization on a flexible flow shop with k stages and m _s machines at any stage proposed by Paternina-Arboleda et al. [Ann. Oper. Res. 164:29–40, 2008] was recently published in Annals of Operations Research journal to solve the flexible flow-shop scheduling problems. In this work, some comments and suggestions are given to the paper. The comment is about the proposed mathematical formulation and the modification of it is suggested.     

Entire Functions on Infinite Dimensional Spaces

In this work we study partial differential operators of infinite order on spaces of entire functions, generalizing some of the results presented in [2] and [5] to the new spaces introduced in [3].     

Combinatorial Sublinear-Time Fourier Algorithms

We study the problem of estimating the best k term Fourier representation for a given frequency sparse signal (i.e., vector) A of length N≫k. More explicitly, we investigate how to deterministically identify k of the largest magnitude frequencies of [^(A)]\hat{\mathbf{A}} , and estimate their coefficients, in polynomial(k,log N) time. Randomized sublinear-time algorithms which have a small (controllable) probability of failure for each processed signal exist for solving this problem (Gilbert et al. in ACM STOC, pp. 152–161, 2002; Proceedings of SPIE Wavelets XI, 2005). In this paper we develop the first known deterministic sublinear-time sparse Fourier Transform algorithm which is guaranteed to produce accurate results. As an added bonus, a simple relaxation of our deterministic Fourier result leads to a new Monte Carlo Fourier algorithm with similar runtime/sampling bounds to the current best randomized Fourier method (Gilbert et al. in Proceedings of SPIE Wavelets XI, 2005). Finally, the Fourier algorithm we develop here implies a simpler optimized version of the deterministic compressed sensing method previously developed in (Iwen in Proc. of ACM-SIAM Symposium on Discrete Algorithms (SODA’08), 2008).     

On the Perfect Matchings of Near Regular Graphs

Let k, h be positive integers with k ≤ h. A graph G is called a [k, h]-graph if k ≤ d(v) ≤ h for any v ? V(G){v \in V(G)}. Let G be a [k, h]-graph of order 2n such that k ≥ n. Hilton (J. Graph Theory 9:193–196, 1985) proved that G contains at least ?k/3?{\lfloor k/3\rfloor} disjoint perfect matchings if h = k. Hilton’s result had been improved by Zhang and Zhu (J. Combin. Theory, Series B, 56:74–89, 1992), they proved that G contains at least ?k/2?{\lfloor k/2\rfloor} disjoint perfect matchings if k = h. In this paper, we improve Hilton’s result from another direction, we prove that Hilton’s result is true for [k, k + 1]-graphs. Specifically, we prove that G contains at least ?\fracn3?+1+(k-n){\lfloor\frac{n}3\rfloor+1+(k-n)} disjoint perfect matchings if h = k + 1.     

Equivalence of Equilibrium Problems and Least Element Problems

In this paper, we introduce the concept of feasible set for an equilibrium problem with a convex cone and generalize the notion of a Z-function for bifunctions. Under suitable assumptions, we derive some equivalence results of equilibrium problems, least element problems, and nonlinear programming problems. The results presented extend some results of [Riddell, R.C.: Equivalence of nonlinear complementarity problems and least element problems in Banach lattices. Math. Oper. Res. 6, 462–474 (1981)] to equilibrium problems. This work was supported by the National Natural Science Foundation of China (10671135) and Specialized Research Fund for the Doctoral Program of Higher Education (20060610005) and the Educational Science Foundation of Chongqing (KJ051307).     

Stronger linear programming relaxations of max-cut

We consider linear programming relaxations for the max cut problem in graphs, based on k-gonal inequalities. We show that the integrality ratio for random dense graphs is asymptotically 1+1/k and for random sparse graphs is at least 1+3/k. There are O(n^k)k-gonal inequalities. These results generalize work by Poljak and Tuza, who gave similar results for k=3.     

On the representation of integers as sums of an odd number of squares

In a recent work, S. Cooper (J. Number Theory 103:135–162, [1988]) conjectured a formula for r _2k+1(p ²), the number of ways p ² can be expressed as a sum of 2k+1 squares. Inspired by this conjecture, we obtain an explicit formula for r _2k+1(n ²),n≥1. Dedicated to Srinivasa Ramanujan.     

Superconvergence of the direct discontinuous Galerkin method for a time‐fractional initial‐boundary value problem

A time‐fractional reaction–diffusion initial‐boundary value problem with periodic boundary condition is considered on Q ? Ω × [0, T] , where Ω is the interval [0, l] . Typical solutions of such problem have a weak singularity at the initial time t = 0. The numerical method of the paper uses a direct discontinuous Galerkin (DDG) finite element method in space on a uniform mesh, with piecewise polynomials of degree k ≥ 2 . In the temporal direction we use the L1 approximation of the Caputo derivative on a suitably graded mesh. We prove that at each time level of the mesh, our L1‐DDG solution is superconvergent of order k + 2 in L²(Ω) to a particular projection of the exact solution. Moreover, the L1‐DDG solution achieves superconvergence of order (k + 2) in a discrete L²(Q) norm computed at the Lobatto points, and order (k + 1) superconvergence in a discrete H¹(Q) seminorm at the Gauss points; numerical results show that these estimates are sharp.     

An equational theory for a nilpotent <Emphasis Type="Italic">A</Emphasis>-loop

It is shown that a variety generated by a nilpotent A-loop has a decidable equational (quasiequational ) theory. Thereby the question posed by A. I. Mal’tsev in [6] is answered in the negative, and moreover, a finitely presented nilpotent A-loop has a decidable word problem.     

Delay moments for FIFO GI/GI/s queues

For stable FIFO GI/GI/s queues, s ≥ 2, we show that finite (k+1)st moment of service time, S, is not in general necessary for finite kth moment of steady-state customer delay, D, thus weakening some classical conditions of Kiefer and Wolfowitz (1956). Further, we demonstrate that the conditions required for E[D ^k]<∞ are closely related to the magnitude of traffic intensity ρ (defined to be the ratio of the expected service time to the expected interarrival time). In particular, if ρ is less than the integer part of s/2, then E[D] < ∞ if E[S^3/2]<∞, and E[D^k]<∞ if E[S^k]<∞, ^k≥ 2. On the other hand, if s-1 < ρ < s, then E[D^k]<∞ if and only if E[S^k+1]<∞, k ≥ 1. Our method of proof involves three key elements: a novel recursion for delay which reduces the problem to that of a reflected random walk with dependent increments, a new theorem for proving the existence of finite moments of the steady-state distribution of reflected random walks with stationary increments, and use of the classic Kiefer and Wolfowitz conditions. This revised version was published online in June 2006 with corrections to the Cover Date.     

Interpolation with circular basis functions

In this paper we consider basis function methods for solving the problem of interpolating data over distinct points on the unit circle. In the special case where the points are equally spaced we can appeal to the theory of circulant matrices which enables an investigation into the stability and accuracy of the method. This work is a further extension and application of the research of Cheney, Light and Xu ([W.A. Light and E.W. Cheney, J. Math. Anal. Appl., 168:110–130, 1992] and [Y. Xu and E.W. Cheney, Computers Math. Applic., 24:201–215, 1992]) from the early nineties.     

Restricted 2-factor polytopes

The optimal k-restricted 2-factor problem consists of finding, in a complete undirected graph K _n , a minimum cost 2-factor (subgraph having degree 2 at every node) with all components having more than k nodes. The problem is a relaxation of the well-known symmetric travelling salesman problem, and is equivalent to it when ≤k≤n−1. We study the k-restricted 2-factor polytope. We present a large class of valid inequalities, called bipartition inequalities, and describe some of their properties; some of these results are new even for the travelling salesman polytope. For the case k=3, the triangle-free 2-factor polytope, we derive a necessary and sufficient condition for such inequalities to be facet inducing. Received March 4, 1997 / Revised version received September 7, 1998?Published online November 9, 1999     

The Rényi–Ulam pathological liar game with a fixed number of lies

The q-round Rényi–Ulam pathological liar game with k lies on the set [n]{1,…,n} is a 2-player perfect information zero sum game. In each round Paul chooses a subset A[n] and Carole either assigns 1 lie to each element of A or to each element of [n]A. Paul wins if after q rounds there is at least one element with k or fewer lies. The game is dual to the original Rényi–Ulam liar game for which the winning condition is that at most one element has k or fewer lies. Define to be the minimum n such that Paul can win the q-round pathological liar game with k lies and initial set [n]. For fixed k we prove that is within an absolute constant (depending only on k) of the sphere bound, ; this is already known to hold for the original Rényi–Ulam liar game due to a result of J. Spencer.     

Extended equivariant Picard complexes and homogeneous spaces

Let k be a field of characteristic 0 and let [`(k)] \bar{k} be a fixed algebraic closure of k. Let X be a smooth geometrically integral k-variety; we set [`(X)] = X ×_k[`(k)] \bar{X} = X{ \times_k}\bar{k} and denote by [`(X)] \bar{X} . In [BvH2] we defined the extended Picard complex of X as the complex of Gal( [`(k)]

Estimates for weighted eigenvalues of a fourth-order elliptic operator with variable coefficients

We investigate the Dirichlet weighted eigenvalue problem for a fourth-order elliptic operator with variable coefficients in a bounded domain in \mathbbRⁿ {\mathbb{R}^n} . We establish a sharp inequality for its eigenvalues. It yields an estimate for the upper bound of the (k + 1)th eigenvalue in terms of the first k eigenvalues. Moreover, we also obtain estimates for some special cases of this problem. In particular, our results generalize the Wang–Xia inequality (J. Funct. Anal., 245, No. 1, 334–352 (2007)) for the clamped-plate problem to a fourth-order elliptic operator with variable coefficients.     

Stable Subconstructs: A Correction and New Results

In Lowen and Wuyts (Appl Categ Struct 8:235–245, 2000) the authors studied the simultaneously concretely reflective and concretely coreflective subconstructs of the category Ap of approach spaces. For the sake of shortness we call such subconstructs stable. Using a technique introduced in Herrlich and Lowen (1999) it was possible to explicitly describe such stable subconstructs by a condition on the objects which used certain subsets of [0, ∞ ]. Thus each stable subconstruct Ap _m described in [9] corresponds to the subset {0} ∪ [m, ∞ ] ⊂ [0, ∞ ] for m ∈ [0, ∞ ]. Although this characterization is correct, Theorem 4.7 in [9] stating that the subconstructs Ap _m were the only stable subconstructs of Ap is not. The main results, which together prove that the only stable subconstructs are those where a restriction is put on the range of the distances of the objects, are upheld, but it turns out that not only the sets {0} ∪ [m, ∞ ], but actually each closed subsemigroup of [0, ∞ ] determines a stable subconstruct (albeit again in exactly the same way as characterized in [9]). In the first part of our paper, Sections 1 and 2, we develop the general technique, which is totally different to the one from [3], and in Theorem 2.13 we prove the main result for the case of approach spaces. The technique which we develop is also applicable to other cases. Thus, in Section 3, more precisely in Theorems 3.9 and 3.11, we give the complete solution to the corresponding characterization problem for the constructs pq Met ^∞ of pseudo-quasi-metric spaces and p Met ^∞ of pseudometric spaces and in Section 4 we briefly sketch how the technique can be adapted and used to also completely solve the problem in the case of more general types of approach spaces and metric spaces. At the same time, in all cases, we are able to give necessary and sufficient conditions under which two stable subconstructs of one of these topological constructs are concretely isomorphic. It turns out that in all cases there are 2^à₀2^{\aleph_0} non-concretely isomorphic stable subconstructs.     

Asymptotic expansions for the conditional sojourn time distribution in the <Emphasis Type="Italic">M</Emphasis>/<Emphasis Type="Italic">M</Emphasis>/1-PS queue

We consider the M/M/1 queue with processor sharing. We study the conditional sojourn time distribution, conditioned on the customer’s service requirement, in various asymptotic limits. These include large time and/or large service request, and heavy traffic, where the arrival rate is only slightly less than the service rate. The asymptotic formulas relate to, and extend, some results of Morrison (SIAM J. Appl. Math. 45:152–167, [1985]) and Flatto (Ann. Appl. Probab. 7:382–409, [1997]). This work was partly supported by NSF grant DMS 05-03745.     

Computational experiments with a lazy version of a <Emphasis Type="Italic">K</Emphasis> quickest simple path ranking algorithm

The quickest path problem is related to the classical shortest path problem, but its objective function concerns the transmission time of a given amount of data throughout a path, which involves both cost and capacity. The K-quickest simple paths problem generalises the latter, by looking for a given number K of simple paths in non-decreasing order of transmission time. Two categories of algorithms are known for ranking simple paths according to the transmission time. One is the adaptation of deviation algorithms for ranking shortest simple paths (Pascoal et al. in Comput. Oper. Res. 32(3):509–520, 2005; Rosen et al. in Comput. Oper. Res. 18(6):571–584, 1991), and another is based on ranking shortest simple paths in a sequence of networks with fixed capacity lower bounds (Chen in Inf. Process. Lett. 50:89–92, 1994), and afterwards selecting the K quickest ones. After reviewing the quickest path and the K-quickest simple paths problems we describe a recent algorithm for ranking quickest simple paths (Pascoal et al. in Ann. Oper. Res. 147(1):5–21, 2006). This is a lazy version of Chen’s algorithm, able to interchange the calculation of new simple paths and the output of each k-quickest simple path. Finally, the described algorithm is computationally compared to its former version, as well as to deviation algorithms.      

Routing in grid graphs by cutting planes

In this paper we study the following problem, which we call the weighted routing problem. Let be given a graphG = (V, E) with non-negative edge weightsw _{e +} and letN,N 1, be a list of node sets. The weighted routing problem consists in finding mutually disjoint edge setsS ₁,...,S _N such that, for eachk {1, ...,N}, the subgraph (V(S _k),S _k) contains an [s, t]-path for alls, t T _k and the sum of the weights of the edge sets is minimal. Our motivation for studying this problem arises from the routing problem in VLSI-design, where given sets of points have to be connected by wires. We consider the weighted routing problem from a polyhedral point of view. We define an appropriate polyhedron and try to (partially) describe this polyhedron by means of inequalities. We describe our separation algorithms for some of the presented classes of inequalities. Based on these separation routines we have implemented a branch and cut algorithm. Our algorithm is applicable to an important subclass of routing problems arising in VLSI-design, namely to switchbox routing problems where the underlying graph is a grid graph and the list of node sets is located on the outer face of the grid. We report on our computational experience with this class of problem instances.     

Nonvanishing of Hecke L-Functions for CM Fields and Ranks of Abelian Varieties

In this paper we prove a nonvanishing theorem for central values of L-functions associated to a large class of algebraic Hecke characters of CM number fields. A key ingredient in the proof is an asymptotic formula for the average of these central values. We combine the nonvanishing theorem with work of Tian and Zhang [TiZ] to deduce that infinitely many of the CM abelian varieties associated to these Hecke characters have Mordell–Weil rank zero. Included among these abelian varieties are higher-dimensional analogues of the elliptic \mathbb Q{{\mathbb Q}} -curves A(D) of B. Gross [Gr].