A tighter bound for FFd algorithm

1. IntroductionIn bin packing, a list L of items, i.e. numbers in the range (0, 1], are to be packed illtobins, each of which has a capacity 1, and the goal is to minimize the number of bins used.The minimal number of bins into which L can be packed is denoted by OPT (L) for the listL. The first~fit-decreasing (FFD) algorithm first sorts the list into a non-increasing orderand then processes the pieces in that order by placing each item into the first bin icao whiChit fits. For tlist L, l…     

ACTA MATHEMATICAE APPLICATAE SINICA (English Series)2000年第16卷第4期摘要

A TIGHTER BOUND FOR FFd ALGORITHM- LI RONGHENG, YUE MINYIFor the bin-packing FFD algorithm we give a proof of FFD(L)≤(_9~11) OPT(L) _(9~7). Thebest bound before was FFD(L)≤_(9~11) OPT(L) 1 given by Yue Minyi.NUMERICAL ANAWSIS OF BIFUACMION PROBLEM WITH CORANK-n- WANG HEYUANIn this paper, numerical approximation of solution branches of bifurcation problem withcorank-n is studied.CONVERGENCE OF ALGORITHMS FOR FINDING EIGENVECT…     

ON 3-CHOOSABILITY OF PLANE GRAPHS WITHOUT 6-,7- AND 9-CYCLES

The choice number of a graph G,denoted by X1(G),is the minimum number k such that if a list of k colors is given to each vertex of G,there is a vertex coloring of G where each vertex receives a color from its own list no matter what the lists are. In this paper,it is showed that X1 (G)≤3 for each plane graph of girth not less than 4 which contains no 6-, 7- and 9-cycles.     

On Conway’s potential function for colored links

The Conway potential function(CPF) for colored links is a convenient version of the multivariable Alexander–Conway polynomial. We give a skein characterization of CPF, much simpler than the one by Murakami. In particular, Conway's "smoothing of crossings" is not in the axioms. The proof uses a reduction scheme in a twisted group-algebra P_nB_n, where B_n is a braid group and P_n is a domain of multi-variable rational fractions. The proof does not use computer algebra tools. An interesting by-product is a characterization of the Alexander–Conway polynomial of knots.     

List Vertex-arboricity of Planar Graphs without Intersecting 5-cycles

The vertex-arboricity a(G)of a graph G is the minimum number of colors required for a vertex coloring of G such that no cycle is monochromatic.The list vertex-arboricity al(G)is the list-coloring version of this concept.In this paper,we prove that every planar graph G without intersecting 5-cycles has al(G)≤2.This extends a result by Raspaud and Wang[On the vertex-arboricity of planar graphs,European J.Combin.29(2008),1064-1075]that every planar graph G without 5-cycles has a(G)≤2.     

THE POISSON FORMULA FOR HARMONIC (1, 0)-FORMS BALL OF C~(n*)

More than thirty five years ago I learned the eoncept of manifolds and the proof of de Rham theorem from a series of lectures given by Prof. Wen-tsün Wu.Prof. Wu' s lectures are duo to the original paper of de Rham. Though nowadays the proof of de Rham theorem is much shorter by using the abstract sheaf theory, but the constructive proof I learned gave mo much stronger impression. This made me     

关于Robinson序列引理的注记

The Infintesimal Prolongation Theorem is extended from sequences to nets in k-saturated nonstandard model. As its application, a main property about the topology of uniform convergence is proved. The proof is much simpler than it was; meanwhile, the nonstandard characteristics of convergence with respect to u.c. topology are given.     

三正则图的至多单折纵横嵌入

This paper provides the complete proof of the fact that any planar cubic graph isat most slngle-bend embeddable except for the tetrabedrou. An O(n) amortized time algorithm for drawing an at most single-bend embedding of a cubic graph‘.is also presented, where n is the number of vertices of the graph. Furthermore, it is proved that the minimum of the total number of bends in an at most slngle-bend embedding of a cubic graph of order n is less than or equal to 0.5n 1. This result is the best possible.     

A comparison between the metric dimension and zero forcing number of trees and unicyclic graphs

The metric dimension dim(G)of a graph G is the minimum number of vertices such that every vertex of G is uniquely determined by its vector of distances to the chosen vertices.The zero forcing number Z(G)of a graph G is the minimum cardinality of a set S of black vertices(whereas vertices in V(G)\S are colored white)such that V(G)is turned black after finitely many applications of"the color-change rule":a white vertex is converted black if it is the only white neighbor of a black vertex.We show that dim(T)≤Z(T)for a tree T,and that dim(G)≤Z(G)+1 if G is a unicyclic graph;along the way,we characterize trees T attaining dim(T)=Z(T).For a general graph G,we introduce the"cycle rank conjecture".We conclude with a proof of dim(T)-2≤dim(T+e)≤dim(T)+1 for e∈E(T).     

THE FFD ALGORITHM FOR THE BIN PACKING PROBLEM WITH KERNEL ITEMS

The FFD algorithm is one of the most famous algorithms for the classical bin packing problem. In this paper,some versions of the FFD algorithm are considered in several bin packing problems. Especially,two of them applied to the bin packing problem with kernel items are analyzed. Tight worst-case performance ratios are obtained.     

A Note on Integral Structures in Some Locally Algebraic Representations of GL2

In the p-adic local Langlands correspondence for GL_2(Q_p), the following theorem of Berger and Breuil has played an important role: the locally algebraic representations of GL_2(Q_p) associated to crystabelline Galois representations admit a unique unitary completion. In this note, we give a new proof of the weaker statement that the locally algebraic representations admit at most one unitary completion and such a completion is automatically admissible. Our proof is purely representation theoretic, involving neither(ψ, Γ)-module techniques nor global methods. When F is a finite extension of Q_p, we also get a simpler proof of a theorem of Vignéras for the existence of integral structures for(locally algebraic) special series and for(smooth) tamely ramified principal series.     

Vertex-distinguishing E-total Coloring of Complete Bipartite Graph K_(7,n) when 7≤n≤95

Let G be a simple graph. A total coloring f of G is called an E-total coloring if no two adjacent vertices of G receive the same color, and no edge of G receives the same color as one of its endpoints. For an E-total coloring f of a graph G and any vertex x of G, let C(x) denote the set of colors of vertex x and of the edges incident with x, we call C(x) the color set of x. If C(u)≠ C(v) for any two different vertices u and v of V(G), then we say that f is a vertex-distinguishing E-total coloring of G or a VDET coloring of G for short. The minimum number of colors required for a VDET coloring of G is denoted by χ_(vt)~e(G) and is called the VDET chromatic number of G. The VDET coloring of complete bipartite graph K_(7,n)(7 ≤ n ≤ 95) is discussed in this paper and the VDET chromatic number of K_(7,n)(7 ≤ n ≤ 95) has been obtained.     

ON THE ERROR FUNCTION OF THE SQUARE-FULL INTEGERS

Let L(x) denote the number of square-full integers not exceeding x. It is proved in [1] thatL(x)～(ζ(3/2)/ζ(3))x~(1/2) (ζ(2/3)/ζ(2))x~(1/3) as x→∞,where ζ(s) denotes the Riemann zeta function. Let △(x) denote the error function in the asymptotic formula for L(x). It was shown by D. Suryanaryana~([2]) on the Riemann hypothesis (RH) that1/x integral from n=1 to x |△(t)|dt=O(x~(1/10 s))for every ε>0. In this paper the author proves the following asymptotic formula for the mean-value of △(x) under the assumption of R. H.integral from n=1 to T (△~2(t/t~(6/5))) dt～c log T,where c>0 is a constant.     

Schwarz’s lemma for the circle packings with the general combinatorics

Rodin (1987) proved the Schwarz’s lemma analog for the circle packings based on the hexagonal combinatorics. In this paper, we prove the Schwarz’s lemma for the circle packings with the general combinatorics and our proof is more simpler than Rodin’s proof. At the same time, we obtain a rigidity property for those packings with the general combinatorics.     

A LAW OF THE ITERATED LOGARITHM FOR NEIGHBOR-TYPE REGRESSION FUNCTION ESTIMATOR

Let (X, Y) be a two-dimensional random variable. A law of the iterated logarithm is established for a smoothed neighbor-typo estimator of the regression function m(x)=E(Y|X=x) under conditions much weaker than needed for the Nadaraya-Watson estimator. Also the sharp pointwise rates of strong consistency of this estimator is discussed in detail.     

A COMPREHENSIVE PROOF OF THE GREENBERGER-HORNE-ZEILINGER THEOREM FOR THE FOUR-QUBIT SYSTEM

Greenberger-Horne-Zeilinger(GHZ)theorem asserts that there is a set of mutually commuting nonlocal observables with a common eigenstate on which those ob- servables assume values that refute the attempt to assign values only required to have them by the local realism of Einstein,Podolsky,and Rosen(EPR).It is known that for a three-qubit system.there is only one form of the GHZ-Mermin-like argument with equiva- lence up to a local unitary transformation,which is exactly Mermin's version of the GHZ theorem.This article for a four-qubit system,which was originally studied by GHZ,the authors show that there are nine distinct forms of the GHZ-Mermin-like argument.The proof is obtained using certain geometric invariants to characterize the sets of mutually commuting nonlocal spin observables on the four-qubit system.It is proved that there are at most nine elements(except for a different sign)in a set of mutually commuting nonlocal spin observables in the four-qubit system,and each GHZ-Mermin-like argument involves a set of at least five mutually commuting four-qubit nonlocal spin observables with a GHZ state as a common eigenstate in GHZ's theorem.Therefore,we present a complete construction of the GHZ theorem for the four-qubit system.     

The geodetic numbers of graphs and digraphs

For every two vertices u and v in a graph G,a u-v geodesic is a shortest path between u and v.Let I(u,v)denote the set of all vertices lying on a u-v geodesic.For a vertex subset S,let I(S) denote the union of all I(u,v)for u,v∈S.The geodetic number g(G)of a graph G is the minimum cardinality of a set S with I(S)=V(G).For a digraph D,there is analogous terminology for the geodetic number g(D).The geodetic spectrum of a graph G,denoted by S(G),is the set of geodetic numbers of all orientations of graph G.The lower geodetic number is g~-(G)=minS(G)and the upper geodetic number is g~ (G)=maxS(G).The main purpose of this paper is to study the relations among g(G),g~-(G)and g~ (G)for connected graphs G.In addition,a sufficient and necessary condition for the equality of g(G)and g(G×K_2)is presented,which improves a result of Chartrand,Harary and Zhang.     

ON THE CROSSING NUMBER OF THE COMPLETE TRIPARTITE GRAPH K_(1,8,n)

The well known Zarankiewicz' conjecture is said that the crossing number of the complete bipartite graph Km,n (m≤n) is Z(m,n). where Z(m,n) = [m/2] [(m-1)/2] [n/2] [(n-1)/2](for and real number x, [x] denotes the maximal integer no more than x). Presently, Zarankiewicz' conjecture is proved true only for the case m≤G. In this article, the authors prove that if Zarankiewicz' conjecture holds for m≤9, then the crossing number of the complete tripartite graph K1,8,n is Z(9, n) 12[n/2].     

Neighbor Sum Distinguishing Total Coloring of Triangle Free IC-planar Graphs

A graph is IC-planar if it admits a drawing in the plane such that each edge is crossed at most once and two crossed edges share no common end-vertex.A proper total-k-coloring of G is called neighbor sum distinguishing if∑_c(u)≠∑_c(v)for each edge uv∈E(G),where∑_c(v)denote the sum of the color of a vertex v and the colors of edges incident with v.The least number k needed for such a total coloring of G,denoted byχ∑"is the neighbor sum distinguishing total chromatic number.Pilsniak and Wozniak conjecturedχ∑"(G)≤Δ(G)+3 for any simple graph with maximum degreeΔ(G).By using the famous Combinatorial Nullstellensatz,we prove that above conjecture holds for any triangle free IC-planar graph with△(G)≥7.Moreover,it holds for any triangle free planar graph withΔ(G)≥6.     

树的L(3,2,1)-标号问题

An L(3,2,1)-labeling of a graph G is a function f from the vertex set V(G) to the set of all non-negative integers(labels) such that |f(u)-f(v)|≥3 if d(u,v)=1,|f(u)-f(v)≥2 if d(u,v)=2 and |f(u)-f(v)|≥1 if d(u,v)=3.For a non-negative integer k,a k-L(3,2,1)-labeling is an L(3,2,1)-labeling such that no label is greater than k.The L(3,2,1)-labeling number of G,denoted by λ_(3,2,1)(G), is the smallest number k such that G has a k-L(3,2,1)-labeling.In this article,we characterize the L(3,2,1)-labeling numbers of trees with diameter at most 6.