INTERPOLATION WITH LAGRANGE POLYNOMIALS A SIMPLE PROOF OF MARKOV INEQUALITY AND SOME OF ITS GENERALIZATIONS

The following theorem is proved Theorem 1.Let q be a polynomial of degree n(qP_n)with n distinct zeroes lying in the interval[-1,1] and △'_q={-1}∪{τ_i:q'(τ_i)=0,i=1,n-1}∪{1}. If polynomial pP_n satisfies the inequality then for each k=1,n and any x[-1,1]its k-th derivative satisfies the inequality 丨p^(k)(x)丨≤max{丨q^((k))(x)丨,丨1/k(x^2-1)q^(k+1)(x)+xq^((k))(x)丨}. This estimate leads to the Markov inequality for the higher order derivatives of polynomials if we set q=T_n,where Tn is Chebyshev polynomial least deviated from zero. Some other results are established which gives evidence to the conjecture that under the conditions of Theorem 1 the inequality ‖p^((k))‖≤‖q^(k)‖holds.

A SIMPLE PROOF OF THE INEQUALITY FFD (L)≤11/9 OPT(L)+1, ■L FOR THE FFD BIN-PACKING ALGORITHM

The first fit decreasing (FFD) heuristic algorithm is one of the most famous and moststudied methods for an approximative solution of the bin-packing problem. For a list L, letOPT(L) denote the minimal number of bins into which L can be packed, and let FFD(L)denote the number of bins used by FFD. Johnson showed that for every list L, FFD(L)≤11/9OPT(L)+4. His proof required more than 100 pages. Later, Baker gave a much shorterand simpler proof for FFD(L)≤11/9OPT(L)+3. His proof required 22 pages. In this paper,we give a proof for FFD(L)≤11/9 OPT(L)+1. The proof is much simpler than the previousones.

A SIMPLE PROOF OF THE INEQUALITY R_M(MF(κ))≤1.2+(1/2~κ) IN MULTIPROCESSOR SCHEDULING

We consider the well-known problem of scheduling n independent tasks nonpreemptivelyon m identical processors with the objective of minimizing the makespan. Coffman, Garey andJohnson described an algorithm MULTIFIT, based on bin-packing, with a worst case performancebetter than the LPT-algorithm. The bound 1.22 obtained by them was claimed by Friesen in1984 that it can be improved to 1.2. In this paper we give a simp1e proof for this bound.

A Simple Security Proof for Entanglement-Based Quantum Key Distribution

Quantum cryptography exploits the quantum mechanical properties of communication lines to enhance the security of the so-called key distribution. In this work, we explain the role played by quantum mechanics in cryptographic tasks and also investigate how secure is quantum cryptography. More importantly, we show by a simple security proof that for any state sent by the sender, the eavesdropper can only guess the output state with a probability that will allow her not to learn more than half of the classical Shannon information shared between the legitimate parties. This implies that with high probability, the shared key is secure.

An Simple Elementary Proof for the Inequality dn〈3^n

In this paper, by using a variation of the Chebyshev＇s method, we present a very simple, elementary proof of an inequality which has applications in number theory.