Lower Bounds for Scheduling on Identical Parallel Machines with Heads and Tails

In this paper, we investigate new lower bounds for the P|r _j ,q _j |C _max scheduling problem. A new bin packing based lower bound, as well as several new lifting procedures are derived for this strongly NP -hard problem. Extensive numerical experiments show that the proposed lower bounds consistently outperform the best existing ones.     

Pareto optima for total weighted completion time and maximum lateness on a single machine

We consider the single-machine bicriterion scheduling problem of enumerating the Pareto-optimal sequences with respect to the total weighted completion time and the maximum lateness objectives. We show that the master sequence concept originally introduced for 1|r_j|∑w_jU_j by Dauzère-Pérès and Sevaux is also applicable to our problem and a large number of other sequencing problems. Our unified development is based on exploiting common order-theoretic structures present in all these problems. We also show that the master sequence implies the existence of global dominance orders for these scheduling problems. These dominance results were incorporated into a new branch and bound algorithm, which was able to enumerate all the Pareto optima for over 90% of the 1440 randomly generated problems with up to n=50 jobs. The identification of each Pareto optimum implicitly requires the optimal solution of a strongly NP-hard problem. The instances solved had hundreds of these Pareto solutions and to the best of our knowledge, this is the first algorithm capable of completely enumerating all Pareto sequences within reasonable time and space for a scheduling problem with such a large number of Pareto optima.     

All spectral dominant norms are stable

A vector norm |·|on the space of n×n complex valued matrices is called stable if for some constant K&>0, not depending upon A or m, we have |A^m|?K|A|^m We show that such a norm is stable if and only if it dominates the spectralradius.     

Improving the preemptive bound for the single machine dynamic maximum lateness problem

The preemptive lower bound is known to be the main available bound for the single machine dynamic maximum lateness problem. We propose an O(nlogn) time improvement to this bound which reduces by more than 80% the average the gap between the preemptive solution value and the optimal solution value.     

Lp-bounds on curvature,elliptic estimates and rectifiability of singular setsBornes Lp sur la courbure,estimées elliptiques et rectifiabilité d'ensembles singuliers

We announce results on rectifiability of singular sets of pointed metric spaces which are pointed Gromov–Hausdorff limits on sequences of Riemannian manifolds, satisfying uniform lower bounds on Ricci curvature and volume, and uniform L_p-bounds on curvature. The rectifiability theorems depend on estimates for |Hess_h|_L2p, (|?Hess_h·|Hess_h|^p?2)_L2, where Δh=c, for some constant c. We also observe that (absent any integral bound on curvature) in the Kähler case, given a uniform 2-sided bound on Ricci curvature, the singular set has complex codimension 2. To cite this article: J. Cheeger, C. R. Acad. Sci. Paris, Ser. I 334 (2002) 195–198.     

A branch-and-check algorithm for minimizing the weighted number of late jobs on a single machine with release dates

In this paper we consider the scheduling problem of minimizing the weighted number of late jobs on a single machine (1|_rj|∑_wjUj)$\left(1|r_j|\sum w_j{U}_j\right)$. A branch-and-check algorithm is proposed, where a relaxed integer programming formulation is solved by branch-and-bound and infeasible solutions are cut off using infeasibility cuts. We suggest two ways to generate cuts. First, tightened “no-good” cuts are derived using a modification of the algorithm by Carlier (1982, EJOR, v.11, 42–47) which was developed for the problem of minimizing maximum lateness on a single machine. Secondly we show how to create cuts by using constraint propagation. The proposed algorithm is implemented in the Mosel modelling and optimization language. Computational experiments on instances with up to 140 jobs are reported. A comparison is presented with the exact approach of Péridy at al. (2003, EJOR, v.148, 591–603).     

On the existence of the N-body Efimov effect

In this paper, we prove the existence of the Efimov effect for N-body quantum systems with N?4. Under the conditions that the bottom of the essential spectrum, E₀, of the N-body operator is attained by the spectra of a unique three-cluster Subhamiltonian and its three associated two-cluster Subhamiltonians, and that at least two of these two-cluster Subhamiltonians have a resonance at the threshold E₀, we give a lower bound of the form C₀|log(E₀−λ)| for the number of eigenvalues on the left of , where C₀ is a positive constant depending only on the reduced masses in the three-cluster decomposition. We also obtain a lower bound on the number of discrete eigenvalues in coupling constant perturbation.     

Covering times of random walks on bounded degree trees and other graphs

The motivating problem for this paper is to find the expected covering time of a random walk on a balanced binary tree withn vertices. Previous upper bounds for general graphs ofO(|V| |E|)⁽¹⁾ andO(|V| |E|/d _min)⁽²⁾ imply an upper bound ofO(n ²). We show an upper bound on general graphs ofO( |E| log |V|), which implies an upper bound ofO(n log² n). The previous lower bound was (|V| log |V|) for trees.⁽²⁾ In our main result, we show a lower bound of (|V| (log _{d max} |V|)²) for trees, which yields a lower bound of (n log² n). We also extend our techniques to show an upper bound for general graphs ofO(max{E T_i} log |V|).     

Non-separating cocircuits in matroids

In this note, we obtain a lower bound for the number of connected hyperplanes of a 3-connected binary matroid M containing a fixed set A provided M|A is coloopless.     

Cesàro sums and algebra homomorphisms of bounded operators

Let g:= gl_m|_n be a general linear Lie superalgebra over an algebraically closed field k:= \({\bar F_p}\) of characteristic p > 2. A module of g is said to be of Kac–Weisfeiler type if its dimension coincides with the dimensional lower bound in the super Kac–Weisfeiler property presented by Wang–Zhao in [9]. In this paper, we verify the existence of the Kac–Weisfeiler modules for gl_m|_n. We also establish the corresponding consequence for the special linear Lie superalgebra sl_m|_n with the restrictions that p > 2 and p ? (m - n).     

On the topological lower bound for the multichromatic number

In 1976, Stahl [14] defined the m-tuple coloring of a graph G and formulated a conjecture on the multichromatic number of Kneser graphs. For m=1 this conjecture is Kneser’s conjecture, which was proved by Lovász in 1978 [10]. Here we show that Lovász’s topological lower bound given in this way cannot be used to prove Stahl’s conjecture. We obtain that the strongest index bound only gives the trivial m⋅ω(G) lower bound if m≥|V(G)|. On the other hand, the connectivity bound for Kneser graphs is constant if m is sufficiently large. These findings provide new examples of graphs showing that the gaps between the chromatic number, the index bound and the connectivity bound can be arbitrarily large.     

Preemptive multiprocessor order scheduling to minimize total weighted flowtime

Consider m identical machines in parallel, each of which can produce k different product types. There is no setup cost when the machines switch from producing one product type to another. There are n orders each of which requests various quantities of the different product types. All orders are available for processing at time t = 0, and preemption is allowed. Order i has a weight w_i and its completion time is the time when its last requested product type finishes. Our goal is to find a preemptive schedule such that the total weighted completion time ∑_wiCi$\sum w_i{C}_i$ is minimized. We show that this problem is NP-hard even when all jobs have identical weights and there are only two machines. Motivated by the computational complexity of the problem, we propose a simple heuristic and show that it obeys a worst-case bound of 2 − 1/m. Finally, empirical studies show that our heuristic performs very well when compared with a lower bound of the optimal cost.     

Vertex-edge domination in graphs

In this paper we study graph parameters related to vertex-edge domination, where a vertex dominates the edges incident to it as well as the edges adjacent to these incident edges. First, we present new relationships relating the ve-domination to some other domination parameters, answering in the affirmative four open questions posed in the 2007 PhD thesis by Lewis. Then we provide an upper bound for the independent ve-domination number in terms of the ve-domination number for every nontrivial connected K_1,k-free graph, with k ≥ 3, and we show that the independent ve-domination number is bounded above by the domination number for every nontrivial tree. Finally, we establish an upper bound on the ve-domination number for connected C₅-free graphs, improving a recent bound given for trees.     

Approximability results for the resource-constrained project scheduling problem with a single type of resources

In this paper, we consider the well-known resource-constrained project scheduling problem. We give some arguments that already a special case of this problem with a single type of resources is not approximable in polynomial time with an approximation ratio bounded by a constant. We prove that there exist instances for which the optimal makespan values for the non-preemptive and the preemptive problems have a ratio of O(logn), where n is the number of jobs. This means that there exist instances for which the lower bound of Mingozzi et al. has a bad relative error of O(logn), and the calculation of this bound is an NP-hard problem. In addition, we give a proof that there exists a type of instances for which known approximation algorithms with polynomial time complexity have an approximation ratio of at least equal to $O(\sqrt{n})$ , and known lower bounds have a relative error of at least equal to O(logn). This type of instances corresponds to the single machine parallel-batch scheduling problem 1|p?batch,b=∞|C _max.     

Counting maximal topologies on countable groups and rings

Two non-discrete Hausdorff group topologies τ₁, τ₂ on a group G are called transversal if the least upper bound τ₁∨τ₂ of τ₁ and τ₂ is the discrete topology. We show that a countable group G admitting non-discrete Hausdorff group topologies admits c² pairwise transversal complete group topologies on G (so c² maximal group topologies). Moreover, every abelian group G admits ²|G|² pairwise transversal complete group topologies.     

On the coefficients of a bounded univalent analytic function

LetF _M denote the class of univalent analytic functionsf in |z|<1 with the expansionf (z)=z+a ₂ z ²+a ₃ z ³+... and |f(z)|?M in |z|<1. In this note I derive a rough bound for alln-th coefficients and a more accurate bound for all the third coefficients of functionsf belonging toF _M.     

Upper bounds for permanents of (1, − 1)-matrices

Let Ω _n denote the set of alln×n (1, ? 1)-matrices. In 1974 E. T. H. Wang posed the following problems: Is there a decent upper bound for |perA| whenAσΩ _n is nonsingular? We recently conjectured that the best possible bound is the permanent of the matrix with exactlyn?1 negative entries in the main diagonal, and affirmed that conjecture by the study of a large class of matrices in Ω _n . Here we prove that this conjecture also holds for another large class of (1, ?1)-matrices which are all nonsingular. We also give an upper bound for the permanents of a class of matrices in Ω _n which are not all regular.     

Erlang loss bounds for OT–ICU systems

In hospitals, patients can be rejected at both the operating theater (OT) and the intensive care unit (ICU) due to limited ICU capacity. The corresponding ICU rejection probability is an important service factor for hospitals. Rejection of an ICU request may lead to health deterioration for patients, and for hospitals to costly actions and a loss of precious capacity when an operation is canceled. There is no simple expression available for this ICU rejection probability that takes the interaction with the OT into account. With c the ICU capacity (number of ICU beds), this paper proves and numerically illustrates a lower bound by an M|G|c|c system and an upper bound by an M|G|c-1|c-1 system, hence by simple Erlang loss expressions. The result is based on a product form modification for a special OT–ICU tandem formulation and proved by a technically complicated Markov reward comparison approach. The upper bound result is of particular practical interest for dimensioning an ICU to secure a prespecified service quality. The numerical results include a case study.     

On the sup-norm of Maass cusp forms of large level

We establish upper bounds for the sup-norm of Hecke-Maass eigenforms on arithmetic surfaces. In a first part, the case of open modular surfaces is studied. Let f{f} be an Hecke–Maass cuspidal newform of square-free level N{N} and bounded Laplace eigenvalue. Recently, V. Blomer and R. Holowinsky [Invent. Math., 179 (3)] provide a non-trivial bound when f{f} is non-exceptional. Our approach is different in that we rely on the geometric side of the trace formula. The improved bound ||f||_￥ << N^-1/23 ||f||₂{||f||_\infty \ll N^{-1/23} ||f||_2} is established. In a second part, we show that a corresponding result holds true for compact arithmetic surfaces and with a better exponent 1/12. The proof requires an estimate for the number of lattice points in a certain annulus domain. A key input is that a congruence subgroup (multiplicative group) is included in an order (ring). This structure enables us to introduce a diophantine argument.     

Sharp bounds for integral means

We introduce a bound M of f, ‖f‖_∞?M?2‖f‖_∞, which allows us to give for 0?p<∞ sharp upper bounds, and for −∞<p<0 sharp lower bounds for the average of |f|^p over E if the average of f over E is zero. As an application we give a new proof of Grüss's inequality estimating the covariance of two random variables. We also give a new estimate for the error term in the trapezoidal rule.