CONSTRUCTIVE APPROXIMATION 2006 Springer Science+Business Media, Inc. Addendum to “On the

Spanning directed trees with many leaves Noga Alon1,Fedor V.Fomin2,Gregory Gutin3,Michael Krivelevich1,andSaket Saurabh21Department of Mathematics,Tel Aviv UniversityTel Aviv69978,Israel{nogaa,krivelev}@post.tau.ac.il2Department of Informatics,University of BergenPOB7803,5020Bergen,Norway{fedor.fomin,saket}@ii.uib.no3Department of Computer ScienceRoyal Holloway,University of LondonEgham,Surrey TW200EX,UKgutin@Abstract.The Directed Maximum Leaf Out-Branching problemis tofind an out-branching(i.e.a rooted oriented spanning tree)in a givendigraph with the maximum number of leaves.In this paper,we obtaintwo combinatorial results on the number of leaves in out-branchings.Weshow that–every strongly connected n-vertex digraph D with minimum in-degree at least3has an out-branching with at least(n/4)1/3−1leaves;–if a strongly connected digraph D does not contain an out-branching with k leaves,then the pathwidth of its underlying graph UG(D)isO(k log k).Moreover,if the digraph is acyclic,the pathwidth is atmost4k.The last result implies that it can be decided in time2O(k log2k)·n O(1)whether a strongly connected digraph on n vertices has an out-branchingwith at least k leaves.On acyclic digraphs the running time of our algo-rithm is2O(k log k)·n O(1).1IntroductionIn this paper,we initiate the combinatorial and algorithmic study of a natural generalization of the well studied Maximum Leaf Spanning Tree problem on connected undirected graphs[11,16,19–21,24,25,31,33].Given a digraph D,a subdigraph T of D is an out-tree if T is an oriented tree with only one vertex s of in-degree zero(called the root).If T is a spanning out-tree,i.e.V(T)=V(D), then T is called an out-branching of D.The vertices of T of out-degree zero are called leaves.The Directed Maximum Leaf Out-Branching(DMLOB) Preliminary extended abstracts of this paper have been presented at FSTTCS2007[5]and ICALP2007[4]2N.Alon,F.V.Fomin,G.Gutin,M.Krivelevich,and S.Saurabhproblem is to find an out-branching in a given digraph with the maximum num-ber of leaves.The combinatorial study of spanning trees with maximum number of leaves in undirected graphs has an extensive history.Linial conjectured around 1987that every connected graph on n vertices with minimum vertex degree δhas a spanning tree with at least n (δ−2)/(δ+1)+c δleaves,where c δdepends on δ.This is indeed the case for all δ≤5.Kleitman and West [27]and Linial and Sturtevant [30]showed that every connected undirected graph G on n vertices with minimum degree at least 3has a spanning tree with at least n/4+2leaves.Griggs and Wu [25]proved that the maximum number of leaves in a spanning tree is at least n/2+2when δ=5and at least 2n/5+8/5when δ=4.All these results are tight.The situation is less clear for δ≥6;the first author observed that Linial’s conjecture is false for all large values of δ.Indeed,the results in [2]imply that there are undirected graphs with n vertices and minimum degree δinwhich no tree has more than (1−(1+o (1))ln(δ+1)δ+1)n leaves,where the o (1)-termtends to zero an δtends to infinity,and this is essentially tight.See also [3],pp.4-5and [13]for more information.In this paper we prove an analogue of the Kleitman-West result for directed graphs:every strongly connected digraph D of order n with minimum in-degree at least 3has an out-branching with at least (n/4)1/3−1leaves.We do not know whether this bound is tight,however we show that there are strongly connected digraphs with minimum in-degree 3in which every out-branching has at most O (√n )leaves.Unlike its undirected counterpart which has attracted a lot of attention in all algorithmic paradigms like approximation algorithms [24,31,33],parameterized algorithms [11,19,21],exact exponential time algorithms [20]and also combina-torial studies [16,25,27,30],the Directed Maximum Leaf Out-Branching problem has largely been neglected until recently.The only paper we are aware of is the very recent paper [18]that describes an O (√opt )-approximation algo-rithms for DMLOB.Our second combinatorial result relates the number of leaves in a DMLOB of a directed graph D with the pathwidth of its underlying graph UG(D ).(We postpone the definition of pathwidth till the next section.)If an undirected graph G contains a star K 1,k as a minor,then it is possible to construct a spanning tree with at least k leaves from this minor.Otherwise,there is no K 1,k minor in G ,and it is possible to prove that the pathwidth of G is O (k ).(See,e.g.[8].)Actually,a much more general result due to Bienstock et al.[10])is that any undirected graph of pathwidth at least k ,contains all trees on k vertices as a minor.We prove a result that can be viewed as a generalization of known bounds on the number of leaves in a spanning tree of an undirected graph in terms of its pathwidth,to strongly connected digraphs.We show that either a strongly connected digraph D has a DMLOB with at least k leaves or the pathwidth of UG(D )is O (k log k ).For an acyclic digraph with a DMLOB having k leaves,we prove that the pathwidth is at most 4k .This almost matches the boundSpanning directed trees with many leaves3 for undirected graphs.These combinatorial results are useful in the design of parameterized algorithms.In parameterized algorithms,for decision problems with input size n,and a parameter k,the goal is to design an algorithm with runtime f(k)n O(1),where f is a function of k alone.(For DMLOB such a parameter is the number of leaves in the out-tree.)Problems having such an algorithm are said to befixed parameter tractable(FPT).The book by Downey and Fellows[17]provides an introduction to the topic of parameterized complexity.For recent developments see the books by Flum and Grohe[23]and by Niedermeier[32].The parameterized version of DMLOB is defined as follows:Given a digraph D and a positive integral parameter k,does D contain an out-branching with at least k leaves?We denote the parameterized versions of DMLOB by k-DMLOB. If in the above definition we do not insist on an out-branching and ask whether there exists an out-tree with at least k leaves,we get the parameterized Di-rected Maximum Leaf Out-Tree problem(denoted k-DMLOT).Our combinatorial bounds,combined with dynamic programming on graphs of bounded pathwidth imply thefirst parameterized algorithms for k-DMLOB on strongly connected digraphs and acyclic digraphs.We remark that the algorith-mic results presented here also hold for all digraphs if we consider k-DMLOT rather than k-DMLOB.This answers an open question of Mike Fellows[14, 22,26].However,we mainly restrict ourselves to k-DMLOB for clarity and the harder challenges it poses,and we briefly consider k-DMLOT only in the last section.Very recently,using a modification of our approach,Bonsma and Dorn[12] proved that either an arbitrary digraph D has an out-branching with at most k leaves or the pathwidth of UG(D )is O(k3),where D is the digraph obtained from D by deleting all arcs not contained in any out-branching of D.The bound O(k3)is much larger than our bounds for strongly connected and acyclic di-graphs,but it suffices to allow Bonsma and Dorn to show that k-DMLOB is FPT,settling another open question of Fellows[22,26].This paper is organized as follows.In Section2we provide additional ter-minology and notation as well as some well-known results.We introduce locally optimal out-branchings in Section3.Bounds on the number of leaves in maxi-mum leaf out-branchings of strongly connected and acyclic digraphs are obtained in Section4.In Section5we prove upper bounds on the pathwidth of the un-derlying graph of strongly connected and acyclic digraphs that do not contain out-branchings with at least k leaves.In Section6we conclude with discussions and open problems.2PreliminariesLet D be a digraph.By V(D)and A(D)we represent the vertex set and arc set of D,respectively.An oriented graph is a digraph with no directed2-cycle. Given a subset V ⊆V(D)of a digraph D,let D[V ]denote the digraph induced by V .The underlying graph UG(D)of D is obtained from D by omitting all4N.Alon,F.V.Fomin,G.Gutin,M.Krivelevich,and S.Saurabhorientations of arcs and by deleting one edge from each resulting pair of parallel edges.The connectivity components of D are the subdigraphs of D induced by the vertices of components of UG(D ).A digraph D is strongly connected if,for every pair x,y of vertices there are directed paths from x to y and from y to x.A maximal strongly connected subdigraph of D is called a strong component .A vertex u of D is an in-neighbor (out-neighbor )of a vertex v if uv ∈A (D )(vu ∈A (D ),respectively).The in-degree d −(v )(out-degree d +(v ))of a vertex v is the number of its in-neighbors (out-neighbors).We denote by (D )the maximum number of leaves in an out-tree of a digraph D and by s (D )we denote the maximum possible number of leaves in an out-branching of a digraph D .When D has no out-branching,we write s (D )=0.The following simple result gives necessary and sufficient conditions for a digraph to have an out-branching.This assertion allows us to check whether s (D )>0in time O (|V (D )|+|A (D )|).Proposition 1([7]).A digraph D has an out-branching if and only if D has a unique strong component with no incoming arcs.Let P =u 1u 2...u q be a directed path in a digraph D .An arc u i u j of D is a forward (backward )arc for P if i ≤j −2(j <i ,respectively).Every backward arc of the type v i +1v i is called double .For a natural number n ,[n ]denotes the set {1,2,...,n }.A tree decomposition of an (undirected)graph G is a pair (X,U )where U is a tree whose vertices we will call nodes and X =({X i |i ∈V (U )})is a collection of subsets of V (G )such that 1. i ∈V (U )X i =V (G ),2.for each edge {v,w }∈E (G ),there is an i ∈V (U )such that v,w ∈X i ,and3.for each v ∈V (G )the set of nodes {i |v ∈X i }forms a subtree of U .The width of a tree decomposition ({X i |i ∈V (U )},U )equals max i ∈V (U ){|X i |−1}.The treewidth of a graph G is the minimum width over all tree decompositions of G .If in the definitions of a tree decomposition and treewidth we restrict U to be a path,then we have the definitions of path decomposition and pathwidth.We use the notation tw (G )and pw (G )to denote the treewidth and the pathwidth of a graph G .We also need an equivalent definition of pathwidth in terms of vertex sepa-rators with respect to a linear ordering of the vertices.Let G be a graph and let σ=(v 1,v 2,...,v n )be an ordering of V (G ).For j ∈[n ]put V j ={v i :i ∈[j ]}and denote by ∂V j all vertices of V j that have neighbors in V \V j .Setting vs (G,σ)=max i ∈[n ]|∂V i |,we define the vertex separation of G asvs (G )=min {vs (G,σ):σis an ordering of V (G )}.The following assertion is well-known.It follows directly from the results of Kirousis and Papadimitriou [29]on interval width of a graph,see also [28].Proposition 2([28,29]).For any graph G ,vs (G )=pw (G ).Spanning directed trees with many leaves53Locally Optimal Out-BranchingsOur bounds are based onfinding locally optimal out-branchings.Given a di-graph,D and an out-branching T,we call a vertex leaf,link and branch if its out-degree in T is0,1and≥2respectively.Let S+≥2(T)be the set of branch vertices,S+1(T)the set of link vertices and L(T)the set of leaves in the tree T. Let P2(T)be the set of maximal paths consisting of link vertices.By p(v)we denote the parent of a vertex v in T;p(v)is the unique in-neighbor of v.We calla pair of vertices u and v siblings if they do not belong to the same path from the root r in T.We start with the following well known and easy to observe facts.Fact1|S+≥2(T)|≤|L(T)|−1.Fact2|P2(T)|≤2|L(T)|−1.Now we define the notion of local exchange which is intensively used in our proofs.Definition3 -Arc Exchange( -AE)optimal out-branching:An out-branching T of a directed graph D with k leaves is -AE optimal if for all arc subsets F⊆A(T)and X⊆A(D)−A(T)of size ,(A(T)\F)∪X is either notan out-branching,or an out-branching with at most k leaves.In other words,Tis -AE optimal if it can’t be turned into an out-branching with more leaves by exchanging arcs.Let us remark,that for everyfixed ,an -AE optimal out-branching can be obtained in polynomial time.In our proofs we use only1-AE optimal out-branchings.We need the following simple properties of1-AE optimal out-branchings. Lemma1.Let T be an1-AE optimal out-branching rooted at r in a digraph D. Then the following holds:(a)For every pair of siblings u,v∈V(T)\L with d+T (p(v))=1,there is no arce=(u,v)∈A(D)\A(T);(b)For every pair of vertices u,v/∈L,d+T (p(v))=1,which are on the samepath from the root with dist(r,u)<dist(r,v)there is no arc e=(u,v)∈A(D)\A(T)(here dist(r,u)is the distance to u in T from the root r); (c)There is no arc(v,r),v/∈L such that the directed cycle formed by the(r,v)-path and the arc(v,r)contains a vertex x such that d+T(p(x))=1. Proof.The proof easily follows from the fact that the existence of any of these arcs contradicts the local optimality of T with respect to1-AE. 4Combinatorial BoundsWe start with a lemma that allows us to obtain lower bounds on s(D).6N.Alon,F.V.Fomin,G.Gutin,M.Krivelevich,and S.SaurabhLemma 2.Let D be a oriented graph of order n in which every vertex is of in-degree 2and let D have an out-branching.If D has no out-tree with k leaves,then n ≤4k 3.Proof.Let us assume that D has no out-tree with k leaves.Consider an out-branching T of D with p <k leaves which is 1-AE optimal.Let r be the root of T .We will bound the number n of vertices in T as follows.Every vertex of T is either a leaf,or a branch vertex,or a link vertex.By Facts 1and 2we already have bounds on the number of leaf and branch vertices as well as the number of maximal paths consisting of link vertices.So to get an upper bound on n in terms of k ,it suffices to bound the length of each maximal path consisting of link vertices.Let us consider such a path P and let x,y be the first and last vertices of P ,respectively.The vertices of V (T )\V (P )can be partitioned into four classes as follows:(a )ancestor vertices :the vertices which appear before x on the (r,x )-path of T ;(b )descendant vertices :the vertices appearing after the vertices of P on pathsof T starting at r and passing through y ;(c )sink vertices :the vertices which are leaves but not descendant vertices;(d )special vertices :none-of-the-above vertices.Let P =P −x ,let z be the out-neighbor of y on T and let T z be the subtree of T rooted at z .By Lemma 1,there are no arcs from special or ancestor vertices to the path P .Let uv be an arc of A (D )\A (P )such that v ∈V (P ).There are two possibilities for u :(i)u ∈V (P ),(ii)u ∈V (P )and uv is backward for P (there are no forward arcs for P since T is 1-AE optimal).Note that every vertex of type (i)is either a descendant vertex or a sink.Observe also that the backward arcs for P form a vertex-disjoint collection of out-trees with roots at vertices that are not terminal vertices of backward arcs for P .These roots are terminal vertices of arcs in which first vertices are descendant vertices or sinks.We denote by {u 1,u 2,...,u s }and {v 1,v 2,...,v t }the sets of vertices on P which have in-neighbors that are descendant vertices and sinks,respectively.Let the out-tree formed by backward arcs for P rooted at w ∈{u 1,...,u s ,v 1,...,v t }be denoted by T (w )and let l (w )denote the number of leaves in T (w ).Observe that the following is an out-tree rooted at z :T z ∪{(in (u 1),u 1),...,(in (u s ),u s )}∪si =1T (u i ),where {in (u 1),...,in (u s )}are the in-neighbors of {u 1,...,u s }on T z .This out-tree has at least s i =1l (u i )leaves and,thus, s i =1l (u i )≤k −1.Let us denote the subtree of T rooted at x by T x and let {in (v 1),...,in (v t )}be the in-neighbors of {v 1,...,v t }on T −V (T x ).Then we have the following out-tree:(T −V (T x ))∪{(in (v 1),v 1),...,(in (v t ),v t )}∪ti =1T (v i )Spanning directed trees with many leaves 7with at least t i =1l (v i )leaves.Thus, t i =1l (v i )≤k −1.Consider a path R =v 0v 1...v r formed by backward arcs.Observe that the arcs {v i v i +1:0≤i ≤r −1}∪{v j v +j :1≤j ≤r }form an out-tree withr leaves,where v +j is the out-neighbor of v j on P.Thus,there is no path ofbackward arcs of length more than k −1.Every out-tree T (w ),w ∈{u 1,...,u s }has l (w )leaves and,thus,its arcs can be decomposed into l (w )paths,each of length at most k −1.Now we can bound the number of arcs in all the trees T (w ),w ∈{u 1,...,u s },as follows: s i =1l (u i )(k −1)≤(k −1)2.We can similarly bound the number of arcs in all the trees T (w ),w ∈{v 1,...,v s }by (k −1)2.Recall that the vertices of P can be either terminal vertices of backward arcsfor P or vertices in {u 1,...,u s ,v 1,...,v t }.Observe that s +t ≤2(k −1)since s i =1l (u i )≤k −1and ti =1l (v i )≤k −1.Thus,the number of vertices in P is bounded from above by 1+2(k −1)+2(k −1)2.Therefore,n =|L (T )|+|S +≥2(T )|+|S +1(T )|=|L (T )|+|S +≥2(T )|+ P ∈P 2(T )|V (P )|≤(k −1)+(k −2)+(2k −3)(2k 2−2k +1)<4k 3.Thus,we conclude that n ≤4k 3.Theorem 4.Let D be a strongly connected digraph with n vertices.(a)If D is an oriented graph with minimum in-degree at least 2,then s (D )≥(n/4)1/3−1.(b)If D is a digraph with minimum in-degree at least 3,then s (D )≥(n/4)1/3−1.Proof.Since D is strongly connected,we have (D )= s (D )>0.Let T be an 1-AE optimal out-branching of D with maximum number of leaves.(a)Delete some arcs from A (D )\A (T ),if needed,such that the in-degree of each vertex of D becomes 2.Now the inequality s (D )≥(n/4)1/3−1follows from Lemma 2and the fact that (D )= s (D ).(b)Let P be the path formed in the proof of Lemma 2.(Note that A (P )⊆A (T ).)Delete every double arc of P ,in case there are any,and delete some more arcs from A (D )\A (T ),if needed,to ensure that the in-degree of each vertex of D becomes 2.It is not difficult to see that the proof of Lemma 2remains valid for the new digraph D .Now the inequality s (D )≥(n/4)1/3−1follows from Lemma 2and the fact that (D )= s (D ). Remark 5It is easy to see that Theorem 4holds also for acyclic digraphs D with s (D )>0.While we do not know whether the bounds of Theorem 4are tight,we can show that no linear bounds are possible.The following result is formulated for Part (b)of Theorem 4,but a similar result holds for Part (a)as well.8N.Alon,F.V.Fomin,G.Gutin,M.Krivelevich,and S.SaurabhTheorem6.For each t≥6there is a strongly connected digraph H t of order n=t2+1with minimum in-degree3such that0< s(H t)=O(t).Proof.Let V(H t)={r}∪{u i1,u i2,...,u i t|i∈[t]}andA(H t)=u i j u i j+1,u i j+1u i j|i∈[t],j∈{0,1,...,t−3}u i j u i j−2|i∈[t],j∈{3,4,...,t−2}u i j u i q|i∈[t],t−3≤j=q≤t,where u i0=r for every i∈[t].It is easy to check that0< s(H t)=O(t). 5Pathwidth of underlying graphs and parameterized algorithmsBy Proposition1,an acyclic digraph D has an out-branching if and only if D possesses a single vertex of in-degree zero.Theorem7.Let D be an acyclic digraph with a single vertex of in-degree zero. Then either s(D)≥k or the underlying undirected graph of D is of pathwidth at most4k and we can obtain this path decomposition in polynomial time. Proof.Assume that s(D)≤k−1.Consider a1-AE optimal out-branching T of D.Notice that|L(T)|≤k−1.Now remove all the leaves and branch vertices from the tree T.The remaining vertices form maximal directed paths consisting of link vertices.Delete thefirst vertices of all paths.As a result we obtain a collection Q of directed paths.Let H=∪P∈Q P.We will show that every arc uv with u,v∈V(H)is in H.Let P ∈Q.As in the proof of Lemma2,we see that there are no forward arcs for P .Since D is acyclic,there are no backward arcs for P .Suppose uv is an arc of D such that u∈R and v∈P ,where R and P are distinct paths from Q.As in the proof of Lemma2,we see that u is either a sink or a descendent vertex for P in T.Since R contains no sinks of T,u is a descendent vertex, which is impossible as D is acyclic.Thus,we have proved that pw(UG(H))=1.Consider a path decomposition of H of width1.We can obtain a path de-composition of UG(D)by adding all the vertices of L(T)∪S+≥2(T)∪F(T),whereF(T)is the set offirst vertices of maximal directed paths consisting of link ver-tices of T,to each of the bags of a path decomposition of H of width1.Observe that the pathwidth of this decomposition is bounded from above by|L(T)|+|S+≥2(T)|+|F(T)|+1≤(k−1)+(k−2)+(2k−3)+1≤4k−5. The bounds on the various sets in the inequality above follows from Facts1and 2.This proves the theorem. Corollary1.For acyclic digraphs,the problem k-DMLOB can solved in time 2O(k log k)·n O(1).Spanning directed trees with many leaves 9Proof.The proof of Theorem 7can be easily turned into a polynomial time algorithm to either build an out-branching of D with at least k leaves or to show that pw (UG(D ))≤4k and provide the corresponding path decomposition.A standard dynamic programming over the path (tree)decomposition (see e.g.[6])gives us an algorithm of running time 2O (k log k )·n O (1).The following simple lemma is well known,see,e.g.,[15].Lemma 3.Let T =(V,E )be an undirected tree and let w :V →R +∪{0}be a weight function on its vertices.There exists a vertex v ∈T such that the weight of every subtree T of T −v is at most w (T )/2,where w (T )= v ∈V w (v ).Let D be a strongly connected digraph with s (D )=λand let T be an out-branching of D with λleaves.Consider the following decomposition of T (called a β-decomposition )which will be useful in the proof of Theorem 8.Assign weight 1to all leaves of T and weight 0to all non-leaves of T .By Lemma 3,T has a vertex v such that each component of T −v has at most λ/2+1leaves (if v is not the root and its in-neighbor v −in T is a link vertex,then v −becomes a new leaf).Let T 1,T 2,...,T s be the components of T −v and let l 1,l 2,...,l s be the numbers of leaves in the components.Notice that λ≤ s i =1l i ≤λ+1(we may get a new leaf).We may assume that l s ≤l s −1≤···≤l 1≤λ/2+1.Let j be the first index such that j i =1l i ≥λ2+1.Considertwo cases:(a)l j ≤(λ+2)/4and (b)l j >(λ+2)/4.In Case (a),we haveλ+22≤j i =1l i ≤3(λ+2)4and λ−64≤s i =j +1l i ≤λ2.In Case (b),we have j =2andλ+2≤l 1≤λ+2and λ−2≤si =2l i ≤3λ+2.Let p =j in Case (a)and p =1in Case (b).Add to D and T a copy v of v (with the same in-and out-neighbors).Then the number of leaves in each of the out-treesT =T [{v }∪(∪pi =1V (T i ))]and T =T [{v }∪(∪s i =p +1V (T i ))]is between λ(1+o (1))/4and 3λ(1+o (1))/4.Observe that the vertices of T have at most λ+1out-neighbors in T and the vertices of T have at most λ+1out-neighbors in T (we add 1to λdue to the fact that v ‘belongs’to both T and T ).Similarly to deriving T and T from T ,we can obtain two out-trees from T and two out-trees from T in which the numbers of leaves are approximately between a quarter and three quarters of the number of leaves in T and T ,respectively.Observe that after O (log λ)‘dividing’steps,we will end up with O (λ)out-trees with just one leaf,i.e.,directed paths.These paths contain O (λ)copies of vertices of D (such as v above).After deleting the copies,we obtain a collection of O (λ)disjoint directed paths covering V (D ).10N.Alon,F.V.Fomin,G.Gutin,M.Krivelevich,and S.SaurabhTheorem8.Let D be a strongly connected digraph.Then either s(D)≥k or the underlying undirected graph of D is of pathwidth O(k log k).Proof.We may assume that s(D)<k.Let T be be a1-AE optimal out-branching.Consider aβ-decomposition of T.The decomposition process can be viewed as a tree T rooted in a node(associated with)T.The children of T in T are nodes(associated with)T and T ;the leaves of T are the directed paths of the decomposition.Thefirst layer of T is the node T,the second layer are T and T ,the third layer are the children of T and T ,etc.In what follows, we do not distinguish between a node Q of T and the tree associated with the node.Assume that T has t layers.Notice that the last layer consists of(some) leaves of T and that t=O(log k),which was proved above(k≤λ−1).Let Q be a node of T at layer j.We will prove thatpw(UG(D[V(Q)]))<2(t−j+2.5)k(1) Since t=O(log k),(1)for j=1implies that the underlying undirected graph of D is of pathwidth O(k log k).Wefirst prove(1)for j=t when Q is a path from the decomposition.LetW=(L(T)∪S+≥2(T)∪F(T))∩V(Q),where F(T)is the set offirst vertices ofmaximal paths of T consisting of link vertices.As in the proof of Theorem7,it follows from Facts1and2that|W|<4k.Obtain a digraph R by deleting from D[V(Q)]all arcs in which at least one end-vertex is in W and which are not arcs of Q.As in the proof of Theorem7,it follows from Lemma1and1-AE opti-mality of T that there are no forward arcs for Q in R.Let Q=v1v2...v q.For every j∈[q],let V j={v i:i∈[j]}.If for some j the set V j contained k vertices,say{v 1,v 2,···,vk },having in-neighbors in the set{v j+1,v j+2,...,v q},then Dwould contain an out-tree with k leaves formed by the path v j+1v j+2...v q to-gether with a backward arc terminating at v i from a vertex on the path for each 1≤i≤k,a contradiction.Thus vs(UG(D2[P]))≤k.By Proposition2,the pathwidth of UG(R)is at most k.Let(X1,X2,...,X s)be a path decomposition of UG(R)of width at most k.Then(X1∪W,X2∪W,...,X s∪W)is a path decomposition of UG(D[V(Q)])of width less than k+4k.Thus,pw(UG(D[V(Q)]))<5k(2) Now assume that we have proved(1)for j=i and show it for j=i−1. Let Q be a node of layer i−1.If Q is a leaf of T,we are done by(2).So,we may assume that Q has children Q and Q which are nodes of layer i.In the β-decomposition of T given before this theorem,we saw that the vertices of T have at mostλ+1out-neighbors in T and the vertices of T have at mostλ+1 out-neighbors in T .Similarly,we can see that(in theβ-decomposition of this proof)the vertices of Q have at most k out-neighbors in Q and the vertices of Q have at most k out-neighbors in Q (since k≤λ−1).Let Y denote the set of the above-mentioned out-neighbors on Q and Q ;|Y|≤2k.Delete from D[V(Q )∪V(Q )]all arcs in which at least one end-vertex is in Y and which do not belong to Q ∪QSpanning directed trees with many leaves11 Let G denote the obtained digraph.Observe that G is disconnected and G[V(Q )]and G[V(Q )]are components of G.Thus,pw(UG(G))≤b,where b=max{pw(UG(G[V(Q )])),pw(UG(G[V(Q )]))}<2(t−i+4.5)k(3) Let(Z1,Z2,...,Z r)be a path decomposition of G of width at most b.Then (Z1∪Y,Z2∪Y,...,Z r∪Y)is a path decomposition of UG(D[V(Q )∪V(Q )]) of width at most b+2k<2(t−i+2.5)k. Similar to the proof of Corollary1,we obtain the following:Corollary2.For a strongly connected digraph D,the problem k-DMLOB can be solved in time2O(k log2k)·n O(1).6Discussion and Open ProblemsIn this paper,we initiated the algorithmic and combinatorial study of the Di-rected Maximum Leaf Out-Branching problem.In particular,we showed that for every strongly connected digraph D of order n and with minimum in-degree at least3, s(D)=Ω(n1/3).An interesting open combinatorial question here is whether this bound is tight.If it is not,it would be interesting tofind the maximum number r such that s(D)=Ω(n r)for every strongly connected digraph D of order n and with minimum in-degree at least3.It follows from ourresults that13≤r≤12.We also provided an algorithm of time complexity2O(k log2k)·n O(1)which solves the k-DMLOB problem for a strongly connected digraph D.The algo-rithm is based on a combinatorial bound on the pathwidth of the underlying graph of D.Instead of using results from Section5,one can use Bodlaender’s algorithm[9]computing(forfixed k)tree decomposition of width k(if such a decomposition exists)in linear bined with our combinatorial bounds this yields a linear time algorithm for k-DMLOB(for a strongly connected di-graphs).However,the exponential dependence of k in Bodlaender’s algorithm is c k3for some large constant c.Finally,let us observe that while our results are for strongly connected di-graphs,they can be extended to a larger class of digraphs.Notice that (D)≥ s(D)for each digraph D.Let L be the family of digraphs D for which either s(D)=0or s(D)= (D).The following assertion shows that L includes a large number digraphs including all strongly connected digraphs and acyclic di-graphs(and,also,the well-studied classes of semicomplete multipartite digraphs and quasi-transitive digraphs,see[7]for the definitions).Proposition3([5]).Suppose that a digraph D satisfies the following property: for every pair R and Q of distinct strong components of D,if there is an arc from R to Q then each vertex of Q has an in-neighbor in R.Then D∈L.。

浅论波普尔的证伪主义波普尔（Karl Popper）是20世纪最重要的哲学家之一，他以其科学哲学和证伪主义理论而闻名于世。

波普尔的证伪主义是对经验主义和归纳主义的一种批判，强调科学理论应该是经验可以证伪的，而无法被证伪的理论则不能被称为科学理论。

波普尔的证伪主义有三个核心观点。

他认为科学理论应当具有可证伪性。

这意味着科学理论应该能够通过实验或观察来得出可以否认或证伪的结果。

只有那些经过严格实验验证、并且可以被证伪的理论，才可以被称为科学理论。

波普尔认为科学理论应当是人们试图解答的问题的解释。

科学理论不仅仅是对事实的描述，更重要的是它们能够解释我们观察到的现象，并提供一种解释现象和预测未来的方式。

只有那些能够提供理论解释的假设才能被认为是科学理论。

波普尔提出了“负责任的实证主义”原则，即科学理论应当包括观察的过程和检验的步骤。

波普尔认为科学研究者不应当仅仅依靠经验数据作为理论的验证，而是应当积极地进行实验和观察，以确定理论的可行性。

波普尔的证伪主义对科学研究有着深远的影响。

它帮助科学家区分科学理论和非科学理论。

科学理论是可以被证伪的，而非科学理论则不具备这种性质。

证伪主义也为科学研究提供了一个明确的方法论，即通过实验和观察来验证或证伪理论。

证伪主义也激励了科学研究者追求更加符合实际的理论。

只有那些能够经过实验证实并取得成果的理论才能够被广泛接受和应用。

波普尔的证伪主义也受到了一些批评。

一些人认为，虽然证伪是科学研究中的重要环节，但并不是唯一的标准。

观察和实验的结果可能受到多种因素的影响，所以实验结果并不能完全验证或证伪一个理论。

一些理论可能具有较高的初始可证伪性，而经过修正和调整后仍然可以适应新的实验观察结果。

一些人认为证伪主义不能完全解释科学研究的复杂性。

波普尔的证伪主义是一种重要的科学哲学思想，它强调科学理论应当具有可证伪性，并且能够解释观察到的现象。

证伪主义为科学研究提供了方法论，并激励了科学研究者不断追求更加符合实际的理论。

LEOPOLD-FRANZENS UNIVERSITYChair of Engineering Mechanicso.Univ.-Prof.Dr.-Ing.habil.G.I.Schu¨e ller,Ph.D.G.I.Schueller@uibk.ac.at Technikerstrasse13,A-6020Innsbruck,Austria,EU Tel.:+435125076841Fax.:+435125072905 mechanik@uibk.ac.at,http://mechanik.uibk.ac.atIfM-Publication2-407G.I.Schu¨e ller.Developments in stochastic structural mechanics.Archive of Applied Mechanics,published online,2006.Archive of Applied Mechanics manuscript No.(will be inserted by the editor)Developments in Stochastic Structural MechanicsG.I.Schu¨e llerInstitute of Engineering Mechanics,Leopold-Franzens University,Innsbruck,Aus-tria,EUReceived:date/Revised version:dateAbstract Uncertainties are a central element in structural analysis and design.But even today they are frequently dealt with in an intuitive or qualitative way only.However,as already suggested80years ago,these uncertainties may be quantified by statistical and stochastic procedures. In this contribution it is attempted to shed light on some of the recent advances in the now establishedfield of stochastic structural mechanics and also solicit ideas on possible future developments.1IntroductionThe realistic modeling of structures and the expected loading conditions as well as the mechanisms of their possible deterioration with time are un-doubtedly one of the major goals of structural and engineering mechanics2G.I.Schu¨e ller respectively.It has been recognized that this should also include the quan-titative consideration of the statistical uncertainties of the models and the parameters involved[56].There is also a general agreement that probabilis-tic methods should be strongly rooted in the basic theories of structural en-gineering and engineering mechanics and hence represent the natural next step in the development of thesefields.It is well known that modern methods leading to a quantification of un-certainties of stochastic systems require computational procedures.The de-velopment of these procedures goes in line with the computational methods in current traditional(deterministic)analysis for the solution of problems required by the engineering practice,where certainly computational pro-cedures dominate.Hence,their further development within computational stochastic structural analysis is a most important requirement for dissemi-nation of stochastic concepts into engineering practice.Most naturally,pro-cedures to deal with stochastic systems are computationally considerably more involved than their deterministic counterparts,because the parameter set assumes a(finite or infinite)number of values in contrast to a single point in the parameter space.Hence,in order to be competitive and tractable in practical applications,the computational efficiency of procedures utilized is a crucial issue.Its significance should not be underestimated.Improvements on efficiency can be attributed to two main factors,i.e.by improved hard-ware in terms of ever faster computers and improved software,which means to improve the efficiency of computational algorithms,which also includesDevelopments in Stochastic Structural Mechanics3 utilizing parallel processing and computer farming respectively.For a con-tinuous increase of their efficiency by software developments,computational procedure of stochastic analysis should follow a similar way as it was gone in the seventieth and eighties developing the deterministic FE approach. One important aspect in this fast development was the focus on numerical methods adjusted to the strength and weakness of numerical computational algorithms.In other words,traditional ways of structural analysis devel-oped before the computer age have been dropped,redesigned and adjusted respectively to meet the new requirements posed by the computational fa-cilities.Two main streams of computational procedures in Stochastic Structural Analysis can be observed.Thefirst of this main class is the generation of sample functions by Monte Carlo simulation(MCS).These procedures might be categorized further according to their purpose:–Realizations of prescribed statistical information:samples must be com-patible with prescribed stochastic information such as spectral density, correlation,distribution,etc.,applications are:(1)Unconditional simula-tion of stochastic processes,fields and waves.(2)Conditional simulation compatible with observations and a priori statistical information.–Assessment of the stochastic response for a mathematical model with prescribed statistics(random loading/system parameters)of the param-eters,applications are:(1)Representative sample for the estimation of the overall distribution.4G.I.Schu¨e ller Indiscriminate(blind)generation of samples.Numerical integration of SDE’s.(2)Representative sample for the reliability assessment by gen-erating adverse rare events with positive probability,i.e.by:(a)variance reduction techniques controlling the realizations of RV’s,(b)controlling the evolution in time of sampling functions.The other main class provides numerical solutions to analytical proce-dures.Grouping again according to the respective purpose the following classification can be made:Numerical solutions of Kolmogorov equations(Galerkin’s method,Finite El-ement method,Path Integral method),Moment Closure Schemes,Compu-tation of the Evolution of Moments,Maximum Entropy Procedures,Asymp-totic Stability of Diffusion Processes.In the following,some of the outlined topics will be addressed stressing new developments.These topics are described within the next six subject areas,each focusing on a different issue,i.e.representation of stochastic processes andfields,structural response,stochastic FE methods and parallel processing,structural reliability and optimization,and stochastic dynamics. In this context it should be mentioned that aside from the MIT-Conference series the USNCCM,ECCM and WCCM’s do have a larger part of sessions addressing computational stochastic issues.Developments in Stochastic Structural Mechanics5 2Representation of Stochastic ProcessesMany quantities involving randomfluctuations in time and space might be adequately described by stochastic processes,fields and waves.Typical ex-amples of engineering interest are earthquake ground motion,sea waves, wind turbulence,road roughness,imperfection of shells,fluctuating prop-erties in random media,etc.For this setup,probabilistic characteristics of the process are known from various measurements and investigations in the past.In structural engineering,the available probabilistic characteristics of random quantities affecting the loading or the mechanical system can be often not utilized directly to account for the randomness of the structural response due to its complexity.For example,in the common case of strong earthquake motion,the structural response will be in general non-linear and it might be too difficult to compute the probabilistic characteristics of the response by other means than Monte Carlo simulation.For the purpose of Monte Carlo simulation sample functions of the involved stochastic pro-cess must be generated.These sample functions should represent accurately the characteristics of the underlying stochastic process orfields and might be stationary and non-stationary,homogeneous or non-homogeneous,one-dimensional or multi-dimensional,uni-variate or multi-variate,Gaussian or non-Gaussian,depending very much on the requirements of accuracy of re-alistic representation of the physical behavior and on the available statistical data.6G.I.Schu¨e ller The main requirement on the sample function is its accurate represen-tation of the available stochastic information of the process.The associ-ated mathematical model can be selected in any convenient manner as long it reproduces the required stochastic properties.Therefore,quite different representations have been developed and might be utilized for this purpose. The most common representations are e.g.:ARMA and AR models,Filtered White Noise(SDE),Shot Noise and Filtered Poisson White Noise,Covari-ance Decomposition,Karhunen-Lo`e ve and Polynomial Chaos Expansion, Spectral Representation,Wavelets Representation.Among the various methods listed above,the spectral representation methods appear to be most widely used(see e.g.[71,86]).According to this procedure,samples with specified power spectral density information are generated.For the stationary or homogeneous case the Fast Fourier Transform(FFT)techniques is utilized for a dramatic improvements of its computational efficiency(see e.g.[104,105]).Advances in thisfield provide efficient procedures for the generation of2D and3D homogeneous Gaus-sian stochasticfields using the FFT technique(see e.g.[87]).The spectral representation method generates ergodic sample functions of which each ful-fills exactly the requirements of a target power spectrum.These procedures can be extended to the non-stationary case,to the generation of stochastic waves and to incorporate non-Gaussian stochasticfields by a memoryless nonlinear transformation together with an iterative procedure to meet the target spectral density.Developments in Stochastic Structural Mechanics7 The above spectral representation procedures for an unconditional simula-tion of stochastic processes andfields can also be extended for Conditional simulations techniques for Gaussianfields(see e.g.[43,44])employing the conditional probability density method.The aim of this procedure is the generation of Gaussian random variates U n under the condition that(n−1) realizations u i of U i,i=1,2,...,(n−1)are specified and the a priori known covariances are satisfied.An alternative procedure is based on the so called Kriging method used in geostatistical application and applied also to con-ditional simulation problems in earthquake engineering(see e.g.[98]).The Kriging method has been improved significantly(see e.g.[36])that has made this method theoretically clearer and computationally more efficient.The differences and similarities of the conditional probability density methods and(modified)Kriging methods are discussed in[37]showing the equiva-lence of both procedures if the process is Gaussian with zero mean.A quite general spectral representation utilized for Gaussian random pro-cesses andfields is the Karhunen-Lo`e ve expansion of the covariance function (see e.g.[54,33]).This representation is applicable for stationary(homoge-neous)as well as for non-stationary(inhomogeneous)stochastic processes (fields).The expansion of a stochastic process(field)u(x,θ)takes the formu(x,θ)=¯u(x)+∞i=1ξ(θ) λiφi(x)(1)where the symbolθindicates the random nature of the corresponding quan-tity and where¯u(x)denotes the mean,φi(x)are the eigenfunctions andλi the eigenvalues of the covariance function.The set{ξi(θ)}forms a set of8G.I.Schu¨e ller orthogonal(uncorrelated)zero mean random variables with unit variance.The Karhunen-Lo`e ve expansion is mean square convergent irrespective of its probabilistic nature provided it possesses afinite variance.For the im-portant special case of a Gaussian process orfield the random variables{ξi(θ)}are independent standard normal random variables.In many prac-tical applications where the random quantities vary smoothly with respectto time or space,only few terms are necessary to capture the major part of the randomfluctuation of the process.Its major advantage is the reduction from a large number of correlated random variables to few most important uncorrelated ones.Hence this representation is especially suitable for band limited colored excitation and stochastic FE representation of random me-dia where random variables are usually strongly correlated.It might also be utilized to represent the correlated stochastic response of MDOF-systems by few most important variables and hence achieving a space reduction.A generalization of the above Karhunen-Lo`e ve expansion has been proposed for application where the covariance function is not known a priori(see[16, 33,32]).The stochastic process(field)u(x,θ)takes the formu(x,θ)=a0(x)Γ0+∞i1=1a i1(x)Γ1(ξi1(θ))+∞i1=1i1i2=1a i1i2(x)Γ2(ξi1(θ),ξi2(θ))+ (2)which is denoted as the Polynomial Chaos Expansion.Introducing a one-to-one mapping to a set with ordered indices{Ψi(θ)}and truncating eqn.2Developments in Stochastic Structural Mechanics9 after the p th term,the above representations reads,u(x,θ)=pj=ou j(x)Ψj(θ)(3)where the symbolΓn(ξi1,...,ξin)denotes the Polynomial Chaos of order nin the independent standard normal random variables.These polynomialsare orthogonal so that the expectation(or inner product)<ΨiΨj>=δij beingδij the Kronecker symbol.For the special case of a Gaussian random process the above representation coincides with the Karhunen-Lo`e ve expan-sion.The Polynomial Chaos expansion is adjustable in two ways:Increasingthe number of random variables{ξi}results in a refinement of the random fluctuations,while an increase of the maximum order of the polynomialcaptures non-linear(non-Gaussian)behavior of the process.However,the relation between accuracy and numerical efforts,still remains to be shown. The spectral representation by Fourier analysis is not well suited to describe local feature in the time or space domain.This disadvantage is overcome in wavelets analysis which provides an alternative of breaking a signal down into its constituent parts.For more details on this approach,it is referred to[24,60].In some cases of applications the physics or data might be inconsistent with the Gaussian distribution.For such cases,non-Gaussian models have been developed employing various concepts to meet the desired target dis-tribution as well as the target correlation structure(spectral density).Cer-tainly the most straight forward procedures is the above mentioned memo-ryless non-linear transformation of Gaussian processes utilizing the spectralrepresentation.An alternative approach utilizes linear and non-linearfil-ters to represent normal and non-Gaussian processes andfields excited by Gaussian white noise.Linearfilters excited by polynomial forms of Poisson white noise have been developed in[59]and[34].These procedures allow the evaluation of moments of arbitrary order without having to resort to closure techniques. Non-linearfilters are utilized to generate a stationary non-Gaussian stochas-tic process in agreement with a givenfirst-order probability density function and the spectral density[48,15].In the Kontorovich-Lyandres procedure as used in[48],the drift and diffusion coefficients are selected such that the solutionfits the target probability density,and the parameters in the solu-tion form are then adjusted to approximate the target spectral density.The approach by Cai and Lin[15]simplifies this procedure by matching the spec-tral density by adjusting only the drift coefficients,which is the followed by adjusting the diffusion coefficient to approximate the distribution of the pro-cess.The latter approach is especially suitable and computationally highly efficient for a long term simulation of stationary stochastic processes since the computational expense increases only linearly with the number n of dis-crete sample points while the spectral approach has a growth rate of n ln n when applying the efficient FFT technique.For generating samples of the non-linearfilter represented by a stochastic differential equations(SDE), well developed numerical procedures are available(see e.g.[47]).3Response of Stochastic SystemsThe assessment of the stochastic response is the main theme in stochastic mechanics.Contrary to the representation of of stochastic processes and fields designed tofit available statistical data and information,the output of the mathematical model is not prescribed and needs to be determined in some stochastic sense.Hence the mathematical model can not be selected freely but is specified a priori.The model involves for stochastic systems ei-ther random system parameters or/and random loading.Please note,due to space limitations,the question of model validation cannot be treated here. For the characterization of available numerical procedures some classifi-cations with regard to the structural model,loading and the description of the stochastic response is most instrumental.Concerning the structural model,a distinction between the properties,i.e.whether it is determinis-tic or stochastic,linear or non-linear,as well as the number of degrees of freedom(DOF)involved,is essential.As a criterion for the feasibility of a particular numerical procedure,the number of DOF’s of the structural system is one of the most crucial parameters.Therefore,a distinction be-tween dynamical-system-models and general FE-discretizations is suggested where dynamical systems are associated with a low state space dimension of the structural model.FE-discretization has no essential restriction re-garding its number of DOF’s.The stochastic loading can be grouped into static and dynamic loading.Stochastic dynamic loading might be charac-terized further by its distribution and correlation and its independence ordependence on the response,resulting in categorization such as Gaussian and non-Gaussian,stationary and non-stationary,white noise or colored, additive and multiplicative(parametric)excitation properties.Apart from the mathematical model,the required terms in which the stochastic re-sponse should be evaluated play an essential role ranging from assessing thefirst two moments of the response to reliability assessments and stabil-ity analysis.The large number of possibilities for evaluating the stochas-tic response as outlined above does not allow for a discussion of the en-tire subject.Therefore only some selected advances and new directions will be addressed.As already mentioned above,one could distinguish between two main categories of computational procedures treating the response of stochastic systems.Thefirst is based on Monte Carlo simulation and the second provides numerical solutions of analytical procedures for obtaining quantitative results.Regarding the numerical solutions of analytical proce-dures,a clear distinction between dynamical-system-models and FE-models should be made.Current research efforts in stochastic dynamics focus to a large extent on dynamical-system-models while there are few new numerical approaches concerning the evaluation of the stochastic dynamic response of e.g.FE-models.Numerical solutions of the Kolmogorov equations are typical examples of belonging to dynamical-system-models where available approaches are computationally feasible only for state space dimensions one to three and in exceptional cases for dimension four.Galerkin’s,Finite El-ement(FE)and Path Integral methods respectively are generally used tosolve numerically the forward(Fokker-Planck)and backward Kolmogorov equations.For example,in[8,92]the FE approach is employed for stationary and transient solutions respectively of the mentioned forward and backward equations for second order systems.First passage probabilities have been ob-tained employing a Petrov-Galerkin FE method to solve the backward and the related Pontryagin-Vitt equations.An instructive comparison between the computational efforts using Monte Carlo simulation and the FE-method is given e.g.in an earlier IASSAR report[85].The Path Integral method follows the evolution of the(transition)prob-ability function over short time intervals,exploiting the fact that short time transition probabilities for normal white noise excitations are locally Gaus-sian distributed.All existing path integration procedures utilize certain in-terpolation schemes where the probability density function(PDF)is rep-resented by values at discrete grid points.In a wider sense,cell mapping methods(see e.g.[38,39])can be regarded as special setups of the path integral procedure.As documented in[9],cumulant neglect closure described in section7.3 has been automated putational procedures for the automated generation and solutions of the closed set of moment equations have been developed.The method can be employed for an arbitrary number of states and closed at arbitrary levels.The approach,however,is limited by available computational resources,since the computational cost grows exponentially with respect to the number of states and the selected closurelevel.The above discussed developments of numerical procedures deal with low dimensional dynamical systems which are employed for investigating strong non-linear behavior subjected to(Gaussian)white noise excitation. Although dynamical system formulations are quite general and extendible to treat non-Gaussian and colored(filtered)excitation of larger systems,the computational expense is growing exponentially rendering most numerical approaches unfeasible for larger systems.This so called”curse of dimen-sionality”is not overcome yet and it is questionable whether it ever will be, despite the fast developing computational possibilities.For this reason,the alternative approach based on Monte Carlo simu-lation(MCS)gains importance.Several aspects favor procedures based on MCS in engineering applications:(1)Considerably smaller growth rate of the computational effort with dimensionality than analytical procedures.(2) Generally applicable,well suited for parallel processing(see section5.1)and computationally straight forward.(3)Non-linear complex behavior does not complicate the basic procedure.(4)Manageable for complex systems.Contrary to numerical solutions of analytical procedures,the employed structural model and the type of stochastic loading does for MCS not play a deceive role.For this reason,MCS procedures might be structured ac-cording to their purpose i.e.where sample functions are generated either for the estimation of the overall distribution or for generating rare adverse events for an efficient reliability assessment.In the former case,the prob-ability space is covered uniformly by an indiscriminate(blind)generationof sample functions representing the random quantities.Basically,at set of random variables will be generated by a pseudo random number generator followed by a deterministic structural analysis.Based on generated random numbers realizations of random processes,fields and waves addressed in section2,are constructed and utilized without any further modification in the following structural analysis.The situation may not be considered to be straight forward,however,in case of a discriminate MCS for the reliability estimation of structures,where rare events contributing considerably to the failure probability should be gener-ated.Since the effectiveness of direct indiscriminate MCS is not satisfactory for producing a statistically relevant number of low probability realizations in the failure domain,the generation of samples is restricted or guided in some way.The most important class are the variance reduction techniques which operate on the probability of realizations of random variables.The most widely used representative of this class in structural reliability assess-ment is Importance Sampling where a suitable sampling distribution con-trols the generation of realizations in the probability space.The challenge in Importance Sampling is the construction of a suitable sampling distribu-tion which depends in general on the specific structural system and on the failure domain(see e.g.[84]).Hence,the generation of sample functions is no longer independent from the structural system and failure criterion as for indiscriminate direct MCS.Due to these dependencies,computational procedures for an automated establishment of sampling distributions areurgently needed.Adaptive numerical strategies utilizing Importance Direc-tional sampling(e.g.[11])are steps in this direction.The effectiveness of the Importance sampling approach depends crucially on the complexity of the system response as well as an the number of random variables(see also section5.2).Static problems(linear and nonlinear)with few random vari-ables might be treated effectively by this approach.Linear systems where the randomness is represented by a large number of RVs can also be treated efficiently employingfirst order reliability methods(see e.g.[27]).This ap-proach,however,is questionable for the case of non-linear stochastic dynam-ics involving a large set of random variables,where the computational effort required for establishing a suitable sampling distribution might exceed the effort needed for indiscriminate direct MCS.Instead of controlling the realization of random variables,alternatively the evolution of the generated sampling can be controlled[68].This ap-proach is limited to stochastic processes andfields with Markovian prop-erties and utilizes an evolutionary programming technique for the genera-tion of more”important”realization in the low probability domain.This approach is especially suitable for white noise excitation and non-linear systems where Importance sampling is rather difficult to apply.Although the approach cannot deal with spectral representations of the stochastic processes,it is capable to make use of linearly and non-linearlyfiltered ex-citation.Again,this is just contrary to Importance sampling which can be applied to spectral representations but not to white noisefiltered excitation.4Stochastic Finite ElementsAs its name suggests,Stochastic Finite Elements are structural models rep-resented by Finite Elements the properties of which involve randomness.In static analysis,the stiffness matrix might be random due to unpredictable variation of some material properties,random coupling strength between structural components,uncertain boundary conditions,etc.For buckling analysis,shape imperfections of the structures have an additional impor-tant effect on the buckling load[76].Considering structural dynamics,in addition to the stiffness matrix,the damping properties and sometimes also the mass matrix might not be predictable with certainty.Discussing numerical Stochastic Finite Elements procedures,two cat-egories should be distinguished clearly.Thefirst is the representation of Stochastic Finite Elements and their global assemblage as random structural matrices.The second category addresses the evaluation of the stochastic re-sponse of the FE-model due to its randomness.Focusingfirst on the Stochastic FE representation,several representa-tions such as the midpoint method[35],the interpolation method[53],the local average method[97],as well as the Weighted-Integral-Method[94,25, 26]have been developed to describe spatial randomfluctuations within the element.As a tendency,the midpoint methods leads to an overestimation of the variance of the response,the local average method to an underestima-tion and the Weighted-Integral-Method leads to the most accurate results. Moreover,the so called mesh-size problem can be resolved utilizing thisrepresentation.After assembling all Finite Elements,the random structural stiffness matrix K,taken as representative example,assumes the form,K(α)=¯K+ni=1K Iiαi+ni=1nj=1K IIijαiαj+ (4)where¯K is the mean of the matrix,K I i and K II ij denote the determinis-ticfirst and second rate of change with respect to the zero mean random variablesαi andαj and n is the total number of random variables.For normally distributed sets of random variables{α},the correlated set can be represented advantageously by the Karhunen-Lo`e ve expansion[33]and for non-Gaussian distributed random variables by its Polynomial chaos ex-pansion[32],K(θ)=¯K+Mi=0ˆKiΨi(θ)(5)where M denotes the total number of chaos polynomials,ˆK i the associated deterministicfluctuation of the matrix andΨi(θ)a polynomial of standard normal random variablesξj(θ)whereθindicates the random nature of the associated variable.In a second step,the random response of the stochastic structural system is determined.The most widely used procedure for evaluating the stochastic response is the well established perturbation approach(see e.g.[53]).It is well adapted to the FE-formulation and capable to evaluatefirst and second moment properties of the response in an efficient manner.The approach, however,is justified only for small deviations from the center value.Since this assumption is satisfied in most practical applications,the obtainedfirst two moment properties are evaluated satisfactorily.However,the tails of the。

Technology and HappinessWhy getting more gadgets won't necessarily increase our well-being. By James SurowieckiIn the 20th century, Americans, Europeans, and East Asians enjoyed material and technological advances that were unimaginable in previous eras. In the United States, for instance, gross domestic product per capita tripled from 1950 to 2000. Life expectancy soared. The benefits of capitalism spread more widely among the population. The boom in productivity after World War II made goods better and cheaper at the same time. Things that were once luxuries, such as jet travel and long-distance phone calls, became necessities. And even though Americans seemed to work extraordinarily hard (at least compared to Europeans), their avid pursuit of entertainment turned media and leisure into multibillion-dollar industries.By most standards, then, you'd have to say that Americans are better off now than they were in the middle of the last century. Oddly, though, if you ask Americans how happy they are, you find that they’re no happier than they were in 1946 (which is when formal surveys of happiness started). In fact, the percentage of people who say they’re very happy has fallen slightly since the early 1970s -- even though the income of people born in 1940 has increased, on average, 116 percent over the course of their working lives. Nor is this a uniquely Americanphenomenon: you can find similar data for most developed countries. Perhaps the most striking example of progress having little impact on what economists call people's sense of subjective well-being is Japan. Between 1960 and the late 1980s, Japan's economy was utterly transformed, as the nation went from a low-cost supplier of cheap manufactured goods to what is perhaps the world’s most technologically sophisticated society. Over that stretch, the country's GDP quintupled. And yet by the late 1980s, the Japanese said they were no happier than they had been in 1960.Even more strikingly, life seems worse for a significant minority of citizens in the rich world. Since the 1950s, reports of major depression have increased tenfold, and while much of that increase undoubtedly represents a new willingness to diagnose mental illness, there’s a general consensus among mental-health experts that it also reflects a real development. People are more anxious, trust government and business less, and get divorced more often. In the 1960s Tom Wolfe confounded those who fretted about the gloominess of American life by insisting that Americans were in the midst of a happiness explosion. Forty years later, plenty of people would disagree.There is, though, one group of Americans that is imperturbably sunny: the Amish. Their depression rates are negligibly low relative tothe rest of society’s. Their happiness levels are consistently high. The Pennsylvania Amish, when asked how much they agree with the statement: You are satisfied with your life (using a scale of 1 to 10), turn out to be as happy as the members of the Forbes 400. The Amish, though, do without most of what we think of as modern technology. They don't rely on the automobile, don't need the Internet, and seem to prefer stability and permanence to the heady growth that propels innovation and the U.S. economy. The comparison is a little facile (the Amish have a lot of other characteristics that make people cheerful, including strong community ties, stable families, and religious faith). But it suggests an interesting question: is it possible that technology, instead of liberating us, is holding us back? Is technological progress merely a treadmill, and if so, would we be happier if we stepped off of it?Can we trust people to know what makes them happy?The relationship between happiness and technology has been a perennial subject for social critics and philosophers since the advent of the Industrial Revolution. But it’s been left largely unexamined by economists and social scientists. The attention that they have paid to the subject of happiness has involved the more capacious relationship between broad material prosperity and well-being. Gregg Easterbrook's book The Progress Paradox grappled with this question directly. Theeconomists Bruno Frey and Alois Stutzer published an academic survey of the subject in Happiness and Economics in 2001. But the truly groundbreaking work on the relationship between prosperity andwell-being was done by the economist Richard Easterlin, who in 1974 wrote a famous paper entitled “Does Economic Growth Improve the Human Lot?”Easterlin showed that when it came to developed countries, there was no real correlation between a nation's income level and its citizens' happiness. Money, Easterlin argued, could not buy happiness -- at least not after a certain point. Easterlin showed that though poverty was strongly correlated with misery, once a country was solidly middle-class, getting wealthier didn't seem to make its citizens any happier.Easterlin's work did not get much attention when it was first published, but its implications were profound. By suggesting that there was no direct link between wealth and well-being, Easterlin was challenging some basic assumptions of mainstream economics. Most economists begin with the idea that people act in their own self-interest most of the time, and that they usually understand that self-interest pretty well. The choices people make, therefore, must be better than the alternatives (or else people would make other choices). By this argument, wealth is a good thing because it increases people’s options and gives them more freedom to pursue whatever it is they want topursue. For classical economists, it was almost tautological to say that the wealthier people are, the happier they are, too.Easterlin's relatively simple study suggested that if what people said about themselves was to be believed, you could give people more choices and more wealth and not have much of an impact on their sense of well-being. Well-being is actually the central idea of economics, says Alan Krueger, an economist at Princeton University. But we’ve never really tried to measure it. We've used proxies, and we've said, If we're richer, and we have more options, we must be better off. But we haven't tried to find out if that's really true.One response to this, of course, is to say that you can't really trust what people say about themselves in surveys, no matter how well executed. Pay attention to what people do, and you’ll get a real sense of what they want. On this view, worrying about whether people say they are happy with the choices they make is nonsense. Of course they are. If people spend a lot of money and time buying and using personal computers and wireless phones and personal digital assistants, then these gadgets must make them happy.There is an inherent logic to this argument, and it has the great virtue of not asking economists to decipher people’s motives. But in the last decade or more, deciphering peoples motives (or at least theirbehavior) is something more economists have become interested in doing, and to great effect. Behavioral economists have moved away from assumptions about individual’s perfect rationality in order to develop what they think of as a more realistic model of economic behavior. They've explored the idea, hardly radical outside economics but pretty radical inside it, that people might sometimes make mistakes, and that their decisions (whether individual or collective) could actually make them unhappy. For instance, behavioral economists have shown that people’s preferences are what is sometimes called time-inconsistent. We would like to save in the long term, but in the short term we'd rather spend. Just as strikingly, behavioral economists have shown that human beings aren't very good at anticipating their own desires. Daniel Kahneman of Princeton University, who won the Nobel Prize in economics in 2002, demonstrated that students, when asked to eat a bowl of their favorite ice cream eight days in a row, had a poor sense of whether they would or would not enjoy the experience.Considering how many decisions about new technologies are based on little or no concrete evidence and involve guessing about the future, it seems plausible that people can get stuck with technologies that don't make them happy but that are hard to get rid of. Plausible, but not certain: as we’ll see, when it comes to the vexed relationship between technology and happiness, certainty is not an easy thing to come by.The question of technology: net loss or net gain?In trying to decipher how technology affects well-being, then, it's worth paying attention to a few things. First, there have been few rigorous studies of the specific relationship between technological change and how people feel about their own lives. So the question “Does more (or better) technology make people happy?”is irreducibly speculative. Second, there is something inherently unstable about people’s accounts of their own states of mind. Forget people's uncertainty about what will make them happy in the future; can we even trust that people know what makes them happy now?Most seriously, thinking about technology is hard because people adapt so quickly to the technologies that are available to them. If you had asked someone in 1870 whether she would be happier if she had a personal vehicle that would give her the freedom to travel hundreds of miles a day, in whatever direction she chose, at relatively little cost; the opportunity to fly across the ocean in a few hours; and the ability to speak to people who were thousands of miles away in real time for a few cents a minute, chances are very good that she would have said, yes, it would make her a lot happier. But today, it's the rare person who gets excited about cars, planes, and telephones. We recognize their utility, but they're also sources of frustration and stress. On balance, mostpeople would say they'd rather have cars and telephones than not, but -- and this is what makes thinking about happiness so hard –it’s not clear they really make us happier.This seems to be close to a universal phenomenon. In fact, one of happiness scholars' most important insights is that people adapt very quickly to good news. Take lottery winners. One famous study showed that although winners were very, very happy when they won, their euphoria quickly evaporated, and after a while their moods and sense of well-being were indistinguishable from what they had been before the victory. Psychologists even have a word for the phenomenon: hedonic adaptation.So, too, with technology: no matter how dramatic a new innovation is, no matter how much easier it makes our lives, it is very easy to take it for granted. You can see this principle at work in the world of technology every day, as things that once seemed miraculous soon become mundane and, worse, frustrating when they don't work perfectly. It’s hard, it turns out, to keep in mind what things were like before the new technology came along. That's why broadband users should occasionally use dial-up: it makes them appreciate just what a difference a high-speed connection really does make.Does our fast absorption of technological progress mean, then, that technology makes no difference? No. It just makes the question of technology's impact, for good and ill, more complicated. Let's start with the downside. There are certain ways in which technology makes life obviously worse. Telemarketing, traffic jams, and identity theft all come to mind. These are all phenomena that make people consciously unhappy. But for the most part, modern critiques of technology have focused not so much on specific, bad technologies as on what Heidegger called the question of technology -- that is, the impact of technology on our humanity.Those critiques have staked out two apparently opposed positions, which nonetheless share a common skepticism about peoples' ability to use technology to their own ends. The first position, which one can see in the work of the French critic Jacques Ellul or, more oddly, in the novels of Philip K. Dick, is that technological progress is leading to an ever more rigid, controlled, soulless society, in which it’s easier for people to be manipulated and monitored. The second position, which has been well articulated in books like Neil Postman's Amusing Ourselves to Death and Robert Putnam's Bowling Alone, is that technology is central to the increasing privatization of experience, which in turn is creating a fragmented, chaotic society, in which traditional relationships are harder to sustain, community isincreasingly an illusion, and people's relationships to each other, mediated as they often are by machines, grow increasingly tenuous.There’s obviously something to both arguments. Privacy has become increasingly fragile in a world of linked databases. In many workplaces, technologies like keystroke monitoring and full recordings of phone calls make it easier to watch workers. The notion that technology disrupts relationships and fractures community gained mainstream prominence as an attack on television, but in recent years it has also become central to the critique of the Internet. In Bowling Alone, Putnam suggests that TV is a chief culprit in the gradual isolation of Americans from each other and the erosion of the social capital that makes societies run smoothly. Similarly, the deleterious effects of the Internet, which supposedly further isolates people from what critics always call the real world, were pointed to early on in a famous study of 169 Pittsburgh residents, Internet Paradox: A Social Technology That Reduces Social Involvement and PsychologicalWell-Being? According to the study, published in the September 1998 issue of American Psychologist, instead of allowing them to connect with a much wider set of potential friends and exposing them to information they might otherwise never have come across, the Internet made people more depressed and lonely than they would otherwise have been.This broad criticism of technology's impact on relationships is an interesting one and is especially relevant to the question of happiness, because one of the few things we can say for certain is that the more friends and close relationships people have, the happier they tend to be. But the evidence that the Internet or even television fundamentally erodes relationships as opposed to changing them is not especially convincing. For instance, when the authors of that 1998 study revisited the question a few years later, using a slightly different methodology, they arrived at the opposite conclusion, finding that the Net had a slightly beneficial impact on people’s sociability, connections with others, and sense of well-being.Obviously, a technology as wide-ranging and ubiquitous as the Net will have myriad, immeasurable effects. But the Internet is essentially a communications technology, one that, like the telephone, allows people to expand their affective and informational networks. The Net is hardly the ideal public sphere, where all discussions are rational and everyone agrees on a definition of the common good. But it is a public sphere, and one that crucially functions without gatekeepers.The dominant critiques of technology have, then, something exaggerated about them. But one way in which technology, as a rule, does make people less happy is in its relentless generation of newness.One of the key insights of happiness studies is that people have a very hard time being content with what they have, at least when they know that others have more. Today, technological change is so rapid that when you buy something, you do so knowing that in a few months there's going to be a better, faster version of the product, and that you’re going to be stuck with the old one. Someone else, in other words, has it better. It's as if disappointment were built into acquisition from the very beginning (unless you're buying a 70-inch plasma screen, in which case you should be fine for at least a couple of years). There's no way to circumvent this drooping of the spirit, which creates dissatisfaction in the heart of the modern consumer.Technology la carte: bad food, but bigger portionsDaily stress, a nagging sense of disappointment, fear that the government knows a lot more about you than you would like it to: if these are some of the ways in which technology reduces peoples sense of well-being, how (if at all) does it increase their happiness? This is terrain that is ordinarily left to the cyber optimists and transhumanists, who believe that technology should be celebrated for the way it remakes and improves our bodies and minds. But setting flights of fancy aside, there is some intriguingly suggestive work about how certain newtechnologies make people not just objectively better off but also happier.In the marketplace, for instance, the Internet has made consumers happier not so much by cutting prices as by expanding the enormous array of choices available to them in a manageable way. In the happiness stakes, expanding consumers’options is really adouble-edged sword: consumers do have a preference for variety and novelty, and the more choices you have, the better the chance that you’ll find the thing you really want. But too much choice can actually paralyze people, leaving them, paradoxically, worse off.A well-known experiment conducted by Professors Mark Lepper and Sheena Iyengar (at Stanford and Columbia, respectively) illustrates the point: they set up two tables in a supermarket, one with 24 jars of jam and the other with six, and offered discount coupons to anyone who stopped to sample the jams. Of the people who stopped at the 24-jam table, only 3 percent went on to buy jam, while 30 percent of the people who stopped at the six-jam table did. More choices often make people frustrated because they have no reasonable way to navigate through them. What the Internet offers, at least in a nascent form, is a host of mechanisms collaborative filtering, shopbots, consumer-rating sites that give people the tools to make informed choices relatively quicklyand easily, reducing paralysis and making them happier. The important point here is that among the infinite choices that the Internet offers, one is the option of less choice.Technology has also radically changed the nature of work, or at least some people’s work. This matters because the workplace is central to people’s sense of well-being and is more important to them than anything, including family. Studies show that nothing -- not even divorce -- makes people more unhappy than unemployment. For much of the 19th and 20th centuries, technology’s impact on the workplace was ambiguous at best. While the mechanization of agriculture allowed people to escape the farm, it often propelled them straight into heavy industrial labor, which was well paying but often miserable. Technology increased the productivity of workers, but it also diminished their autonomy: superiors controlled more of the details of their working days. Even the office work of the postwar period exemplified by the endless rows of desks in Billy Wilder's The Apartment was deeply bureaucratic and controlled. But recently, the rise of the networked society, and the advent of knowledge-based businesses, means that workplaces have become less formal and more open, even while remaining efficient and productive. Already, as Arlie Hochschild points out in The Time Bind, a significant percentage of Americans find the atmosphere at work more congenial than the one at home. As thenumber of knowledge workers grows, and as companies strive to keep them happy, well-being should increase.The most important impact of technology on people’s sense ofwell-being, though, is in the field of health care. Before the Industrial Revolution, two out of every three Europeans died before the age of 30. Today, life expectancy for women in Western Europe is almost 80 years, and it continues to increase. The point is obvious, but important to note: the vast majority of people are happy to be alive, and the more time they get on earth, the better off they feel they'll be. (Remember, the point about prosperity and happiness is not that prosperity makes people unhappy; it’s that it doesn’t necessarily make them happier.) Now, the picture is a little more complicated than this. Living a few extra years as a geriatric may not be ideal. But until very recently, life for the vast majority of people was (in Hobbess formulation) nasty, brutish, and short. Technology has changed that, at least for people in the rich world. As much as we should worry about the rising cost of health care and the problem of the uninsured, it’s also worth remembering how valuable for our spirits as well as our bodies are the benefits that medical technology and pharmaceuticals have brought us.On a deeper level, what the technological improvement of our health and our longevity underscores is a paradox of any discussion ofhappiness on a national or a global level: even though people may not be happier, even though they are wealthier and possess more technology, they’re still as hungry as ever for more time. It's like that old Woody Allen joke: the food may not be so great, but we want the portions to be as big as possible.Technology may only improve the taste of the meals slightly, but it makes them a lot bigger, and for most of us, that has the promise of something like happiness.。

DIRECTIVE NUMBER: CPL 02-00-150 EFFECTIVE DATE: April 22, 2011 SUBJECT: Field Operations Manual (FOM)ABSTRACTPurpose: This instruction cancels and replaces OSHA Instruction CPL 02-00-148,Field Operations Manual (FOM), issued November 9, 2009, whichreplaced the September 26, 1994 Instruction that implemented the FieldInspection Reference Manual (FIRM). The FOM is a revision of OSHA’senforcement policies and procedures manual that provides the field officesa reference document for identifying the responsibilities associated withthe majority of their inspection duties. This Instruction also cancels OSHAInstruction FAP 01-00-003 Federal Agency Safety and Health Programs,May 17, 1996 and Chapter 13 of OSHA Instruction CPL 02-00-045,Revised Field Operations Manual, June 15, 1989.Scope: OSHA-wide.References: Title 29 Code of Federal Regulations §1903.6, Advance Notice ofInspections; 29 Code of Federal Regulations §1903.14, Policy RegardingEmployee Rescue Activities; 29 Code of Federal Regulations §1903.19,Abatement Verification; 29 Code of Federal Regulations §1904.39,Reporting Fatalities and Multiple Hospitalizations to OSHA; and Housingfor Agricultural Workers: Final Rule, Federal Register, March 4, 1980 (45FR 14180).Cancellations: OSHA Instruction CPL 02-00-148, Field Operations Manual, November9, 2009.OSHA Instruction FAP 01-00-003, Federal Agency Safety and HealthPrograms, May 17, 1996.Chapter 13 of OSHA Instruction CPL 02-00-045, Revised FieldOperations Manual, June 15, 1989.State Impact: Notice of Intent and Adoption required. See paragraph VI.Action Offices: National, Regional, and Area OfficesOriginating Office: Directorate of Enforcement Programs Contact: Directorate of Enforcement ProgramsOffice of General Industry Enforcement200 Constitution Avenue, NW, N3 119Washington, DC 20210202-693-1850By and Under the Authority ofDavid Michaels, PhD, MPHAssistant SecretaryExecutive SummaryThis instruction cancels and replaces OSHA Instruction CPL 02-00-148, Field Operations Manual (FOM), issued November 9, 2009. The one remaining part of the prior Field Operations Manual, the chapter on Disclosure, will be added at a later date. This Instruction also cancels OSHA Instruction FAP 01-00-003 Federal Agency Safety and Health Programs, May 17, 1996 and Chapter 13 of OSHA Instruction CPL 02-00-045, Revised Field Operations Manual, June 15, 1989. This Instruction constitutes OSHA’s general enforcement policies and procedures manual for use by the field offices in conducting inspections, issuing citations and proposing penalties.Significant Changes∙A new Table of Contents for the entire FOM is added.∙ A new References section for the entire FOM is added∙ A new Cancellations section for the entire FOM is added.∙Adds a Maritime Industry Sector to Section III of Chapter 10, Industry Sectors.∙Revises sections referring to the Enhanced Enforcement Program (EEP) replacing the information with the Severe Violator Enforcement Program (SVEP).∙Adds Chapter 13, Federal Agency Field Activities.∙Cancels OSHA Instruction FAP 01-00-003, Federal Agency Safety and Health Programs, May 17, 1996.DisclaimerThis manual is intended to provide instruction regarding some of the internal operations of the Occupational Safety and Health Administration (OSHA), and is solely for the benefit of the Government. No duties, rights, or benefits, substantive or procedural, are created or implied by this manual. The contents of this manual are not enforceable by any person or entity against the Department of Labor or the United States. Statements which reflect current Occupational Safety and Health Review Commission or court precedents do not necessarily indicate acquiescence with those precedents.Table of ContentsCHAPTER 1INTRODUCTIONI.PURPOSE. ........................................................................................................... 1-1 II.SCOPE. ................................................................................................................ 1-1 III.REFERENCES .................................................................................................... 1-1 IV.CANCELLATIONS............................................................................................. 1-8 V. ACTION INFORMATION ................................................................................. 1-8A.R ESPONSIBLE O FFICE.......................................................................................................................................... 1-8B.A CTION O FFICES. .................................................................................................................... 1-8C. I NFORMATION O FFICES............................................................................................................ 1-8 VI. STATE IMPACT. ................................................................................................ 1-8 VII.SIGNIFICANT CHANGES. ............................................................................... 1-9 VIII.BACKGROUND. ................................................................................................. 1-9 IX. DEFINITIONS AND TERMINOLOGY. ........................................................ 1-10A.T HE A CT................................................................................................................................................................. 1-10B. C OMPLIANCE S AFETY AND H EALTH O FFICER (CSHO). ...........................................................1-10B.H E/S HE AND H IS/H ERS ..................................................................................................................................... 1-10C.P ROFESSIONAL J UDGMENT............................................................................................................................... 1-10E. W ORKPLACE AND W ORKSITE ......................................................................................................................... 1-10CHAPTER 2PROGRAM PLANNINGI.INTRODUCTION ............................................................................................... 2-1 II.AREA OFFICE RESPONSIBILITIES. .............................................................. 2-1A.P ROVIDING A SSISTANCE TO S MALL E MPLOYERS. ...................................................................................... 2-1B.A REA O FFICE O UTREACH P ROGRAM. ............................................................................................................. 2-1C. R ESPONDING TO R EQUESTS FOR A SSISTANCE. ............................................................................................ 2-2 III. OSHA COOPERATIVE PROGRAMS OVERVIEW. ...................................... 2-2A.V OLUNTARY P ROTECTION P ROGRAM (VPP). ........................................................................... 2-2B.O NSITE C ONSULTATION P ROGRAM. ................................................................................................................ 2-2C.S TRATEGIC P ARTNERSHIPS................................................................................................................................. 2-3D.A LLIANCE P ROGRAM ........................................................................................................................................... 2-3 IV. ENFORCEMENT PROGRAM SCHEDULING. ................................................ 2-4A.G ENERAL ................................................................................................................................................................. 2-4B.I NSPECTION P RIORITY C RITERIA. ..................................................................................................................... 2-4C.E FFECT OF C ONTEST ............................................................................................................................................ 2-5D.E NFORCEMENT E XEMPTIONS AND L IMITATIONS. ....................................................................................... 2-6E.P REEMPTION BY A NOTHER F EDERAL A GENCY ........................................................................................... 2-6F.U NITED S TATES P OSTAL S ERVICE. .................................................................................................................. 2-7G.H OME-B ASED W ORKSITES. ................................................................................................................................ 2-8H.I NSPECTION/I NVESTIGATION T YPES. ............................................................................................................... 2-8 V.UNPROGRAMMED ACTIVITY – HAZARD EVALUATION AND INSPECTION SCHEDULING ............................................................................ 2-9 VI.PROGRAMMED INSPECTIONS. ................................................................... 2-10A.S ITE-S PECIFIC T ARGETING (SST) P ROGRAM. ............................................................................................. 2-10B.S CHEDULING FOR C ONSTRUCTION I NSPECTIONS. ..................................................................................... 2-10C.S CHEDULING FOR M ARITIME I NSPECTIONS. ............................................................................. 2-11D.S PECIAL E MPHASIS P ROGRAMS (SEP S). ................................................................................... 2-12E.N ATIONAL E MPHASIS P ROGRAMS (NEP S) ............................................................................... 2-13F.L OCAL E MPHASIS P ROGRAMS (LEP S) AND R EGIONAL E MPHASIS P ROGRAMS (REP S) ............ 2-13G.O THER S PECIAL P ROGRAMS. ............................................................................................................................ 2-13H.I NSPECTION S CHEDULING AND I NTERFACE WITH C OOPERATIVE P ROGRAM P ARTICIPANTS ....... 2-13CHAPTER 3INSPECTION PROCEDURESI.INSPECTION PREPARATION. .......................................................................... 3-1 II.INSPECTION PLANNING. .................................................................................. 3-1A.R EVIEW OF I NSPECTION H ISTORY .................................................................................................................... 3-1B.R EVIEW OF C OOPERATIVE P ROGRAM P ARTICIPATION .............................................................................. 3-1C.OSHA D ATA I NITIATIVE (ODI) D ATA R EVIEW .......................................................................................... 3-2D.S AFETY AND H EALTH I SSUES R ELATING TO CSHO S.................................................................. 3-2E.A DVANCE N OTICE. ................................................................................................................................................ 3-3F.P RE-I NSPECTION C OMPULSORY P ROCESS ...................................................................................................... 3-5G.P ERSONAL S ECURITY C LEARANCE. ................................................................................................................. 3-5H.E XPERT A SSISTANCE. ........................................................................................................................................... 3-5 III. INSPECTION SCOPE. ......................................................................................... 3-6A.C OMPREHENSIVE ................................................................................................................................................... 3-6B.P ARTIAL. ................................................................................................................................................................... 3-6 IV. CONDUCT OF INSPECTION .............................................................................. 3-6A.T IME OF I NSPECTION............................................................................................................................................. 3-6B.P RESENTING C REDENTIALS. ............................................................................................................................... 3-6C.R EFUSAL TO P ERMIT I NSPECTION AND I NTERFERENCE ............................................................................. 3-7D.E MPLOYEE P ARTICIPATION. ............................................................................................................................... 3-9E.R ELEASE FOR E NTRY ............................................................................................................................................ 3-9F.B ANKRUPT OR O UT OF B USINESS. .................................................................................................................... 3-9G.E MPLOYEE R ESPONSIBILITIES. ................................................................................................. 3-10H.S TRIKE OR L ABOR D ISPUTE ............................................................................................................................. 3-10I. V ARIANCES. .......................................................................................................................................................... 3-11 V. OPENING CONFERENCE. ................................................................................ 3-11A.G ENERAL ................................................................................................................................................................ 3-11B.R EVIEW OF A PPROPRIATION A CT E XEMPTIONS AND L IMITATION. ..................................................... 3-13C.R EVIEW S CREENING FOR P ROCESS S AFETY M ANAGEMENT (PSM) C OVERAGE............................. 3-13D.R EVIEW OF V OLUNTARY C OMPLIANCE P ROGRAMS. ................................................................................ 3-14E.D ISRUPTIVE C ONDUCT. ...................................................................................................................................... 3-15F.C LASSIFIED A REAS ............................................................................................................................................. 3-16VI. REVIEW OF RECORDS. ................................................................................... 3-16A.I NJURY AND I LLNESS R ECORDS...................................................................................................................... 3-16B.R ECORDING C RITERIA. ...................................................................................................................................... 3-18C. R ECORDKEEPING D EFICIENCIES. .................................................................................................................. 3-18 VII. WALKAROUND INSPECTION. ....................................................................... 3-19A.W ALKAROUND R EPRESENTATIVES ............................................................................................................... 3-19B.E VALUATION OF S AFETY AND H EALTH M ANAGEMENT S YSTEM. ....................................................... 3-20C.R ECORD A LL F ACTS P ERTINENT TO A V IOLATION. ................................................................................. 3-20D.T ESTIFYING IN H EARINGS ................................................................................................................................ 3-21E.T RADE S ECRETS. ................................................................................................................................................. 3-21F.C OLLECTING S AMPLES. ..................................................................................................................................... 3-22G.P HOTOGRAPHS AND V IDEOTAPES.................................................................................................................. 3-22H.V IOLATIONS OF O THER L AWS. ....................................................................................................................... 3-23I.I NTERVIEWS OF N ON-M ANAGERIAL E MPLOYEES .................................................................................... 3-23J.M ULTI-E MPLOYER W ORKSITES ..................................................................................................................... 3-27 K.A DMINISTRATIVE S UBPOENA.......................................................................................................................... 3-27 L.E MPLOYER A BATEMENT A SSISTANCE. ........................................................................................................ 3-27 VIII. CLOSING CONFERENCE. .............................................................................. 3-28A.P ARTICIPANTS. ..................................................................................................................................................... 3-28B.D ISCUSSION I TEMS. ............................................................................................................................................ 3-28C.A DVICE TO A TTENDEES .................................................................................................................................... 3-29D.P ENALTIES............................................................................................................................................................. 3-30E.F EASIBLE A DMINISTRATIVE, W ORK P RACTICE AND E NGINEERING C ONTROLS. ............................ 3-30F.R EDUCING E MPLOYEE E XPOSURE. ................................................................................................................ 3-32G.A BATEMENT V ERIFICATION. ........................................................................................................................... 3-32H.E MPLOYEE D ISCRIMINATION .......................................................................................................................... 3-33 IX. SPECIAL INSPECTION PROCEDURES. ...................................................... 3-33A.F OLLOW-UP AND M ONITORING I NSPECTIONS............................................................................................ 3-33B.C ONSTRUCTION I NSPECTIONS ......................................................................................................................... 3-34C. F EDERAL A GENCY I NSPECTIONS. ................................................................................................................. 3-35CHAPTER 4VIOLATIONSI. BASIS OF VIOLATIONS ..................................................................................... 4-1A.S TANDARDS AND R EGULATIONS. .................................................................................................................... 4-1B.E MPLOYEE E XPOSURE. ........................................................................................................................................ 4-3C.R EGULATORY R EQUIREMENTS. ........................................................................................................................ 4-6D.H AZARD C OMMUNICATION. .............................................................................................................................. 4-6E. E MPLOYER/E MPLOYEE R ESPONSIBILITIES ................................................................................................... 4-6 II. SERIOUS VIOLATIONS. .................................................................................... 4-8A.S ECTION 17(K). ......................................................................................................................... 4-8B.E STABLISHING S ERIOUS V IOLATIONS ............................................................................................................ 4-8C. F OUR S TEPS TO BE D OCUMENTED. ................................................................................................................... 4-8 III. GENERAL DUTY REQUIREMENTS ............................................................. 4-14A.E VALUATION OF G ENERAL D UTY R EQUIREMENTS ................................................................................. 4-14B.E LEMENTS OF A G ENERAL D UTY R EQUIREMENT V IOLATION.............................................................. 4-14C. U SE OF THE G ENERAL D UTY C LAUSE ........................................................................................................ 4-23D.L IMITATIONS OF U SE OF THE G ENERAL D UTY C LAUSE. ..............................................................E.C LASSIFICATION OF V IOLATIONS C ITED U NDER THE G ENERAL D UTY C LAUSE. ..................F. P ROCEDURES FOR I MPLEMENTATION OF S ECTION 5(A)(1) E NFORCEMENT ............................ 4-25 4-27 4-27IV.OTHER-THAN-SERIOUS VIOLATIONS ............................................... 4-28 V.WILLFUL VIOLATIONS. ......................................................................... 4-28A.I NTENTIONAL D ISREGARD V IOLATIONS. ..........................................................................................4-28B.P LAIN I NDIFFERENCE V IOLATIONS. ...................................................................................................4-29 VI. CRIMINAL/WILLFUL VIOLATIONS. ................................................... 4-30A.A REA D IRECTOR C OORDINATION ....................................................................................................... 4-31B.C RITERIA FOR I NVESTIGATING P OSSIBLE C RIMINAL/W ILLFUL V IOLATIONS ........................ 4-31C. W ILLFUL V IOLATIONS R ELATED TO A F ATALITY .......................................................................... 4-32 VII. REPEATED VIOLATIONS. ...................................................................... 4-32A.F EDERAL AND S TATE P LAN V IOLATIONS. ........................................................................................4-32B.I DENTICAL S TANDARDS. .......................................................................................................................4-32C.D IFFERENT S TANDARDS. .......................................................................................................................4-33D.O BTAINING I NSPECTION H ISTORY. .....................................................................................................4-33E.T IME L IMITATIONS..................................................................................................................................4-34F.R EPEATED V. F AILURE TO A BATE....................................................................................................... 4-34G. A REA D IRECTOR R ESPONSIBILITIES. .............................................................................. 4-35 VIII. DE MINIMIS CONDITIONS. ................................................................... 4-36A.C RITERIA ................................................................................................................................................... 4-36B.P ROFESSIONAL J UDGMENT. ..................................................................................................................4-37C. A REA D IRECTOR R ESPONSIBILITIES. .............................................................................. 4-37 IX. CITING IN THE ALTERNATIVE ............................................................ 4-37 X. COMBINING AND GROUPING VIOLATIONS. ................................... 4-37A.C OMBINING. ..............................................................................................................................................4-37B.G ROUPING. ................................................................................................................................................4-38C. W HEN N OT TO G ROUP OR C OMBINE. ................................................................................................4-38 XI. HEALTH STANDARD VIOLATIONS ....................................................... 4-39A.C ITATION OF V ENTILATION S TANDARDS ......................................................................................... 4-39B.V IOLATIONS OF THE N OISE S TANDARD. ...........................................................................................4-40 XII. VIOLATIONS OF THE RESPIRATORY PROTECTION STANDARD(§1910.134). ....................................................................................................... XIII. VIOLATIONS OF AIR CONTAMINANT STANDARDS (§1910.1000) ... 4-43 4-43A.R EQUIREMENTS UNDER THE STANDARD: .................................................................................................. 4-43B.C LASSIFICATION OF V IOLATIONS OF A IR C ONTAMINANT S TANDARDS. ......................................... 4-43 XIV. CITING IMPROPER PERSONAL HYGIENE PRACTICES. ................... 4-45A.I NGESTION H AZARDS. .................................................................................................................................... 4-45B.A BSORPTION H AZARDS. ................................................................................................................................ 4-46C.W IPE S AMPLING. ............................................................................................................................................. 4-46D.C ITATION P OLICY ............................................................................................................................................ 4-46 XV. BIOLOGICAL MONITORING. ...................................................................... 4-47CHAPTER 5CASE FILE PREPARATION AND DOCUMENTATIONI.INTRODUCTION ............................................................................................... 5-1 II.INSPECTION CONDUCTED, CITATIONS BEING ISSUED. .................... 5-1A.OSHA-1 ................................................................................................................................... 5-1B.OSHA-1A. ............................................................................................................................... 5-1C. OSHA-1B. ................................................................................................................................ 5-2 III.INSPECTION CONDUCTED BUT NO CITATIONS ISSUED .................... 5-5 IV.NO INSPECTION ............................................................................................... 5-5 V. HEALTH INSPECTIONS. ................................................................................. 5-6A.D OCUMENT P OTENTIAL E XPOSURE. ............................................................................................................... 5-6B.E MPLOYER’S O CCUPATIONAL S AFETY AND H EALTH S YSTEM. ............................................................. 5-6 VI. AFFIRMATIVE DEFENSES............................................................................. 5-8A.B URDEN OF P ROOF. .............................................................................................................................................. 5-8B.E XPLANATIONS. ..................................................................................................................................................... 5-8 VII. INTERVIEW STATEMENTS. ........................................................................ 5-10A.G ENERALLY. ......................................................................................................................................................... 5-10B.CSHO S SHALL OBTAIN WRITTEN STATEMENTS WHEN: .......................................................................... 5-10C.L ANGUAGE AND W ORDING OF S TATEMENT. ............................................................................................. 5-11D.R EFUSAL TO S IGN S TATEMENT ...................................................................................................................... 5-11E.V IDEO AND A UDIOTAPED S TATEMENTS. ..................................................................................................... 5-11F.A DMINISTRATIVE D EPOSITIONS. .............................................................................................5-11 VIII. PAPERWORK AND WRITTEN PROGRAM REQUIREMENTS. .......... 5-12 IX.GUIDELINES FOR CASE FILE DOCUMENTATION FOR USE WITH VIDEOTAPES AND AUDIOTAPES .............................................................. 5-12 X.CASE FILE ACTIVITY DIARY SHEET. ..................................................... 5-12 XI. CITATIONS. ..................................................................................................... 5-12A.S TATUTE OF L IMITATIONS. .............................................................................................................................. 5-13B.I SSUING C ITATIONS. ........................................................................................................................................... 5-13C.A MENDING/W ITHDRAWING C ITATIONS AND N OTIFICATION OF P ENALTIES. .................................. 5-13D.P ROCEDURES FOR A MENDING OR W ITHDRAWING C ITATIONS ............................................................ 5-14 XII. INSPECTION RECORDS. ............................................................................... 5-15A.G ENERALLY. ......................................................................................................................................................... 5-15B.R ELEASE OF I NSPECTION I NFORMATION ..................................................................................................... 5-15C. C LASSIFIED AND T RADE S ECRET I NFORMATION ...................................................................................... 5-16。

1.That sex ratio will be favored which maximizes the number of descendantsan individual will have and hence the number of gene copies transmitted.那种性别比例能在最大程度上增加一个个体所能拥有的后代数量，并因此能在最大程度上增加所传递到后代身上去的基因复制品的数量。

2.Hardy’s weakness derived from his apparent inability to control the comings and goings of these divergent impulses and from his unwillingness to cultivate and sustain the energetic and risky ones.哈代的缺陷一方面缘起于他的某种明显的无能，无法控制好那结不尽相同的创作冲动的穿梭往来；另一方面缘起于他不愿意去培养和维持那些富于生机活力和风险性强的创作冲动。

3.Virginia Woolf’s provocative statement about her intentions in writing Mrs. Dalloway has regularly been ignored by the critics，since it highlightsan aspect of her literary interests very different from the traditional picture of the "poetic" novelist concerned with examining states of reverie and vision and with following the intricate pathways of individual consciousness.弗吉尼亚.伍尔夫（Virginia Woolf）在创作《黛洛维夫人》（Mrs. Dalloway）时有关其创作意图的这番发人深思的陈述，迄今为止一贯为文学评论家们所忽略，因为它突出反映了她诸多文学兴趣中某一方面，而这一方面则与人们对“诗性”小说家（poetic n ovelist）所形成的传统见解大相径庭。

Excessive Long-Time Deflections of PrestressedBox Girders.I:Record-Span Bridge inPalau and Other ParadigmsZden ěk P.Ba žant,Hon.M.ASCE 1;Qiang Yu 2;and Guang-Hua Li 3Abstract:The segmental prestressed concrete box girder of Koror-Babeldaob (KB)Bridge in Palau,which had a record span of 241m (791ft),presents a striking paradigm of serviceability loss because of excessive multidecade deflections.The data required for analysis have recently been released and are here exploited to show how the analysis and design could be improved.Erected segmentally in 1977,this girder developed a midspan deflection of 1.61m (5.3ft)compared with the design camber after 18years,and it collapsed in 1996as a consequence of remedial prestressing,after a 3-month pared with three-dimensional analysis,the traditional beam-type analysis of box girder deflections is found to have errors up to 20%,although greater errors are likely for bridges with higher box-width-to-span ratios than the KB Bridge.However,even three-dimensional finite-element analysis with step-by-step time integration cannot explain the observed deflections when the current American Concrete Institute,Japan Society of Civil Engineers,ComitéEuro-International du Béton (or ComitéEuro-International du Béton —Fédération internationale de la précontrainte),and Gardner and Lockman prediction models for creep and shrinkage are used.These models give 18-year deflection estimates that are 50–77%lower than measured and yield unrealistic shapes of the deflection history.They also predict the 18-year prestress loss to be 46–56%lower than the measured mean prestress loss,which was 50%.Model B3,which is the only theoretically based model,underestimates the 18-year deflection by 42%and gives a prestress loss of 40%when the default parameter values are used.However,in Model B3,several input parameters are adjustable and if they are adjusted according to the long-time laboratory tests of Brooks,a close fit of all the measurements is obtained.For early deflections and their extrapolation,it is important that Model B3can capture realistically the differences in the rates of shrinkage and drying creep caused by the differences in the thickness of the walls of the cross section.The differences in temperature and possible cracking of the top slab also need to be taken into account.Other paradigms on which data have recently been released are four bridges in Japan and one in the Czech Republic.Their excessive deflections can also be explained.The detailed method of analysis and the lessons learned are presented in Part II.DOI:10.1061/(ASCE)ST.1943-541X .0000487.©2012American Society of Civil Engineers.CE Database subject headings:Creep;Shrinkage;Box girders;Serviceability;Deflection;Span bridges.Author keywords:Prestressed box girder;Bridges;Segmental erection;Shear lag;Design standards;Concrete;Relaxation.IntroductionClarification of the causes of major disasters and serviceability loss has been and will always be a prime opportunity for progress in struc-tural engineering.A paradigm that presents such an opportunity for creep and shrinkage analysis and design is offered by the excessive deflections of the Koror-Babeldaob (KB)Bridge,which crossed the Toegel Channel between the islands of Koror and Babeldaob in the Republic of Palau in the tropical western Pacific [Fig.1(a)].When it was completed in 1977,its main span of 241m (791ft)set the worldrecord for segmental prestressed concrete box girders (Yee 1979).The final deflection,measured as the difference from the design cam-ber of À0:3m (or À12in.),was expected to terminate at 0.76–0.88m (30–34.6in.),as predicted by the design (ABAM 1993;Khaled Shawwaf,personal communication,September,18,2008)based on the original CEB-FIP design recommendations (1970–1972).According to the 1971American Concrete Institute (ACI)model (ACI 1971),which is still in force today (reapproved in 2008)(ACI 2008a ),the deflection measured from the design camber would have been predicted as 0.71m (28in.)according to McDonald et al.(2003)and 0.737m (29in.)according to the present analysis.After 18years,the deflection measured at the end of the con-struction reached 1.39m (54.7in.)and kept growing (ABAM 1993;Berger/ABAM 1995a ).The design camber of 0.30m (12in.)was not met (Khaled Shawwaf,personal communication,September 18,2008)and an additional creep deflection of 0.22m (9in.)had accumulated during the segmental erection,making the actual camber only 0.075m (3in.)when the cantilevers were joined.Thus,the total 18-year deflection at midspan was 1.61m (5.3ft).Remedial prestressing was undertaken but caused the bridge to collapse (after a 3-month delay)on September 26,1996,with two fatalities and many injuries (SSFM 1996;Parker 1996;Pilz 1997,1999;McDonald et al.2003;Burgoyne and Scantlebury 2006)[see Fig.1(b)].1McCormick Institute Professor and W.P.Murphy Professor of Civil Engineering and Materials Science,Dept.of Civil and Environmental En-gineering,Northwestern Univ.,2145Sheridan Rd.,CEE/A135,Evanston,IL 60208(corresponding author).E-mail:z-bazant@ 2Assistant Professor,Dept.of Civil Engineering,Univ.of Pittsburgh,PA;formerly,Postdoctoral Research Associate,Northwestern Univ.,Evanston,IL 60208.3Graduate Research Assistant,Northwestern Univ.,Evanston,IL 60208.Note.This manuscript was submitted on February 1,2010;approved on August 1,2011;published online on May 15,2012.Discussion period open until November 1,2012;separate discussions must be submitted for indi-vidual papers.This paper is part of the Journal of Structural Engineering ,V ol.138,No.6,June 1,2012.©ASCE,ISSN 0733-9445/2012/6-676–686/$25.00.676/JOURNAL OF STRUCTURAL ENGINEERING ©ASCE /JUNE 2012D o w n l o a d e d f r o m a s c e l i b r a r y .o r g b y H u a z h o n g U n i v e r s i t y o f S c i e n c e & T e c h n o l o g y o n 03/18/14. C o p y r i g h t A S CE .F o r p e r s o n a l u s e o n l y ; a l l r i g h t s r e s e r v e d .As a result of the legal litigation,the technical data collected by the investigating agencies in relation to this major disaster were unavailable to the engineering public for many years.A worldwide group of 47experts (see the Appendix),therefore pro-posed a resolution at the Third Structural Engineers World Congress in Bangalore that called,on the grounds of engineering ethics,for the release of all technical data necessary for analyses of major structural collapses,including the bridge in Palau.The resolution passed on November 6,2007,and was circulated widely.In January 2008,the Attorney General of the Republic of Palau permitted the release of the necessary technical data.The present two-part study (see also Ba žant et al.2012),which updates a 2008preliminary report (Ba žant et al.2008)and expands a brief recent article (Ba žant et al.2010),aims to explain the reasons for the excessive long-term deflections and compare the per-formance of various existing models.Understanding the reasons is important because recent data collection (Ba žant et al.2011a ,b ,c )has revealed similar,mostly excessive,deflections of 69similar bridge spans (and likely many more).The method of analysis is presented in detail in Part II (Ba žant et al.2012),which also enun-ciates the lessons for structural analysis and design.Hopefully,these lessons will resolve the currently intractable disagreements in tech-nical committees about the optimal prediction model that can be used as a standard guide.These lessons should also help interpret the health monitoring of structures.Clarification of the collapse caused by remedial prestressing will be postponed for a subsequent article.A forthcoming article (Yu et al.2012)further makes a comparison with a popular commercial bridge creep program (SOFiSTiK).Bridge Description and Input Data for AnalysisThe main span of 241m (791ft)consisted of two symmetric concrete cantilevers connected at midspan by a horizontally sliding hinge.Each cantilever consisted of 25cast-in-place segments of depths varying from 14.17m (46.5ft)at the main piers to 3.66m (12ft)at the midspan.The main span was flanked by 72.2m (237ft)long side spans in which the box girder was partially filled with rock bal-last to balance the moment at the main pier.The total length of the bridge was 386m (1,266ft).The thickness of the top slab ranged from 432mm (17in.)at the main piers to 280mm (11in.)at the midspan.The thickness of the bottom slab varied from 1,153mm (45.4in.)at the main piers to 178mm (7in.)at the -pared with the depth of the girder,the webs had an unusually small thickness of 356mm (14in.),which was constant throughout the whole main span.The typical cross sections are shown in Fig.2.Type I portland cement was used for the superstructure (Khaled Shawwaf,personal communication,September,18,2008).The mass density of the concrete was ρ¼2;325kg ∕m 3(145lb ∕ft 3).The top slab was covered by concrete pavement with an average thickness of 76mm (3in.)and a density of 2;233kg ∕m 3(139lb ∕ft 3).The aggregate was crushed basalt rock of the maxi-mum aggregate size of approximately 19mm (3∕4in),supplied from a quarry on the island of Malakal.Beach sand from Palau was used as the fine aggregate,and its washing by mechanical means helped keep the chloride content within the limit allowed (Berger/ABAM 1995b ).Although no original measurements of the Young ’s elastic modu-lus E c of the concrete are known,some information was obtained in 1990through core sample tests (JICA 1990).These tests yielded E c ¼22:1GPa (3,200ksi).In 1995,further core sample tests (Berger/ABAM 1995a )made just before the retrofit revealed the porosity to be high and E c to be approximately 21.7GPa (3,150ksi).Both investigations showed values approximately 23%lower than the value estimated from the design compression strength according to the ACI empirical formula,which is 28.3GPa (4,110ksi).Truck load tests were conducted during an on-site investigation by the Japan International Cooperation Agency (JICA).Matching the deflections measured at midspan by finite-element elastic analysis provided,after a correction for concrete age according to the ACI formula,an average 28-day E c of approximately 22.0GPa (3,190ksi)(JICA 1990).This E c value was adopted for analysis because the load test gives the average elastic modulus in the box girder.The prestress was generated by Dywidag threaded alloy bars (tendons)[yield strength 1,034MPa (150kip);diameterFig.1.(a)Koror-Babeldaob Bridge in Palau (in 1977);(b)Babeldaob side after the collapse (in 1996)(images courtesy DYWIDAG Systems International and Wiss,Janney,Elstner Associates,Inc.,withpermission)Fig.2.3D view of one-half of the box girder,its cross sections at the main pier and at the middle of the main span,and the placement of prestressing tendons at the main pierJOURNAL OF STRUCTURAL ENGINEERING ©ASCE /JUNE 2012/677D o w n l o a d e d f r o m a s c e l i b r a r y .o r g b y H u a z h o n g U n i v e r s i t y o f S c i e n c e & T e c h n o l o g y o n 03/18/14. C o p y r i g h t A S CE .F o r p e r s o n a l u s e o n l y ; a l l r i g h t s r e s e r v e d .31.8mm (1.25in.)],extended by couplers,anchored by nuts,and grouted in ducts [diameter 47.6mm (1.9in.)](ABAM 1993;DRC 1996).Some tendons were stressed from one end and some from both ends (Yee 1979;McDonald et al.2003).The jacking force of each tendon was 0.60MN (135kip)(DRC 1996).There were 316tendons above the main pier,densely packed in four layers within the top slab (see Fig.2).Their combined initial prestressing force was approximately 190MN (42,606kip)(Yee 1979;Pilz 1997;McDonald et al.2003).The same threaded bars were used to provide vertical prestress in the webs and horizontal transverse prestress in the top slab.The tendon spacing in the webs ranged from 0.3to 3m (1to 10ft)(Khaled Shawwaf,personal commu-nication,September,18,2008).The horizontal transverse tendons in the top slab were spaced at 0.56m (22in.)(ABAM 1993;McDonald et al.2003).The alloy steel of the tendons had a yield strength of 1,034MPa (150ksi)and an ultimate strength of 1,054MPa (153ksi)(DRC 1996).Its Young ’s elastic modulus was assumed to be 200GPa (29,000ksi),and the Poisson ’s ratio was assumed to be 0.3.Unprestressed steel reinforcement (ABAM 1993)was taken into account in the calculations.In postcollapse examination,neither the prestressed nor the unprestressed steel showed any signs of significant corrosion despite the tropical marine environment,although some of the ducts showed mild corrosion.The construction of each segment took slightly more than one week (TYLI 1996).When the concrete strength in the segment just cast attained 17.2MPa (2,500psi),6–12tendons were stressed to 50%of their final jacking force (TYLI 1996).When the concrete strength reached 24.1MPa (3,500psi),all the tendons terminating in this segment were stressed fully.The segmental erection of the opposite symmetric cantilevers was almost simultaneous and took 6–7months (Yee 1979).Although the construction was closely monitored,the camber that was planned to offset the anticipated long-term deflections was not met.The creep and shrinkage during the segmental erection caused an unintentional initial sag of 229mm (9in.)at midspan that could not be corrected during the erection because it would have required abrupt large changes of slope (Khaled Shawwaf,personal communication,September 18,2008).The initial sag before installation of the midspan hinge was not in-cluded in the reported deflection measurements or in the deflection curves in the figures.The initial deflections for the first 2years were benign.How-ever,in 1990,the longer-term deflections revealed that the midspan deflection had reached 1.22m (48in.)(JICA 1990),which caused ride discomfort,vibrations after vehicle passage,and excessive deterioration of the road surface.By 1993(ABAM 1993),the deflection had reached 1.32m (52in.).In 1995,just before removal of the roadway pavement [average thickness of 76mm (3in.)],the midspan deflection had reached 1.39m (54.7in.)and was still growing (Berger/ABAM 1995a ).Creep and Shrinkage Models ConsideredAs an adequate approximation under service conditions,concrete can be assumed to follow aging linear viscoelasticity with correc-tions for tensile cracking,variations of humidity and temperature,and drying creep (or the Pickett effect).The concrete deformation is then fully characterized by one of the existing prediction models for the shrinkage strain ϵsh (t )and the compliance function J ðt ;t 0Þ.The prediction models considered in the analysis were the ACI model (ACI 1971,2008a ),the ComitéEuro-Internationale du Béton (CEB),Fédération internationale de la précontrainte (FIP)(orCEB-FIP,or fib)model (Fédération internationale du béton,fib 1999),the Japan Society of Civil Engineers (JSCE)model (JSCE 1991),the Gardner and Lockman (GL)model (Gardner 2000;Gardner and Lockman 2001),and Model B3(Ba žant and Baweja 1995,2000;Ba žant and Prasannan 1988,1989a ,b ;Jirásek and Ba žant 2002).The same computer program,ABAQUS (SIMULIA,Providence,Rhode Island),with the same step-by-step time inte-gration based on the Kelvin chain,was used for all models (see Ba žant et al.2012).The smallest deviations from the data were obtained with Model B3based on the solidification theory (Ba žant and Prasannan 1989a ,b ),which was first presented in 1995(Ba žant and Baweja 1995),slightly updated in 2000(Ba žant and Baweja 2000),and summarized in Jirásek and Ba žant (2002).Model B3represents a refinement of the earlier Ba žant-Panula and Ba žant-Panula-Kim-Xi models (Ba žant and Panula 1978a ,b ,c ,d ,1979a ,b ;Ba žant and Kim 1991b ,1992a ,b ,c ;Ba žant et al.1991,1992).The theo-retical justification has been provided in several studies (Ba žant et al.1997;Ba žant 2000,2001).The form of the B3compliance function for basic creep was theoretically derived and experimen-tally supported in Ba žant and Prasannan (1988,1989a ,b ).In stat-istically unbiased comparisons with a large database (Ba žant and Li 2008a ),Model B3was clearly superior to the other existing models (Ba žant and Li 2008b ;Ba žant et al.2008).The input parameters of the creep and shrinkage prediction models are divided into extrinsic and intrinsic.For all models,the extrinsic parameters,which include the environmental factors,are the following:1.The age at the start of drying,taken here as t c ¼7days,which is the mean period of the segmental erection cycle ranging from 5to 10days (Khaled Shawwaf,personal communication,September 18,2008;TYLI 1996);2.The average environmental humidity h ¼0:70;3.The effective thickness of cross section D ¼2V ∕S ,in which a minor correction k s for body shape is applied in the case of Model B3;k s ¼1for all slabs and webs considered here (V ∕S =volume —surface ratio);and4.For the extended Model B3only,and also the temperature.The intrinsic input parameters,which reflect the composition of concrete,vary from model to model.Formulation of the ACI,CEB,and GL models was driven by the desire for simplicity.Accordingly,the only important intrinsic parameter in these models is the standard 28-day compression strength f 0c ,while other major influencing parameters such as the cement content and the water-cement and aggregate-cement ratios are not taken into account.Model B3is special in that the free intrinsic input parameters are more than one.They introduce the main aspects of concrete composition.If unknown,they can be set equal to their recom-mended default values.Their advantages are that reasonable ranges of the unknown concrete mix parameters can be explored,compu-tation of structural responses for various plausible sets of values of these parameters can be run,and a picture of the possible range of structural responses to expect can be obtained.Two sets of input parameters have been considered in the computations.Set 1Pure PredictionThe mean 28-day compressive strength f 0cr of concrete was approx-imately 35.9MPa (5,200psi),as indicated by the cylinder tests during construction reported by Raymond Zelinski (personal communication,December 12,2010).However,in Ba žant et al.(2010),the value of 35.9MPa was considered according to ABAM (1993)to be the 28-day specified compressive strength f 0c .The mean strength f c from the cylinder tests during construction must not have been lower than f 0cx ;and according to the ACI code678/JOURNAL OF STRUCTURAL ENGINEERING ©ASCE /JUNE 2012D o w n l o a d e d f r o m a s c e l i b r a r y .o r g b y H u a z h o n g U n i v e r s i t y o f S c i e n c e & T e c h n o l o g y o n 03/18/14. C o p y r i g h t A S CE .F o r p e r s o n a l u s e o n l y ; a l l r i g h t s r e s e r v e d .(ACI 2008b ),Zelinski ’s value implies that f 0c ≤35:9MPa ÀΔf ,where Δf ≈1:34×standard deviation (Ba žant and Yu 2006),which would have been much less than 35.9MPa.On the other hand,the f 0c value from ABAM (1993)implies that f 0cr ≈35:9MPa þΔf .ABAM and Zelinski cannot both be right.The records of Zelinski (the resident engineer at the KB Bridge con-struction representing both the designer,Alfred A.Yee &Associ-ates,and the owner,the Trust Territory Government)are deemed more reliable,and so the curves from Ba žant et al.(2010)had to be recalculated.Nonetheless,the recalculation changed the results very little because other Zelinski ’s input changes happened to com-pensate.Furthermore,the prediction models should properly use the mean strength or an estimated f 0cr ,as stated in Model B3,but the ACI Guide (ACI 2008a )specifies the use of f 0c for all mod-els.To keep the results comparable,f 0c had to be used as the input for all models,including B3Set 1.The 28-day elastic modulus E c was neither specified in design nor measured on the site.The modulus value was measured on core samples just before the retrofit,but this value is appropriate for Set 2and must not be used for Set 1,which is intended to check the prediction capability.The only way that E c could be estimated at the time of design was from the approximate ACI formula E c ¼ð57;000psi Þffiffiffiffiffiffiffiffiffiffiffiffiffiffiffif 0cr ðpsi Þp ,which gives E c ¼28:3GPa (4,110ksi).Furthermore,according to Zelinski ’s records,the spe-cific cement content c was 535kg ∕m 3(33:4lb ∕ft 3),the aggregate-cement ratio a ∕c was 2.90,and the water-cement ratio w ∕c was 0.40(in which a superplasticizer was used).A higher w ∕c value was considered in Ba žant et al.(2010),but this was an estimate from ABAM (1993)and Khaled Shawwaf (personal communica-tion,September 18,2008).On the basis of the foregoing input,the B3empirical formulas (Ba žant and Baweja 2000)yield the following Model B3parameters,which are different from Ba žant et al.(2010):q 1¼0:146;q 2¼1:42;q 3¼0:011;q 4¼0:080;q 5¼2:33ð×10À6∕psi Þð1Þεk ∞¼0:000981and k t ¼19:2ðset 1Þð2Þwhere the values of q 2,q 3,and q 4are increased by 20%because of the mean of the plasticizer effects observed by Brooks (2000)(the use of plasticizer was not known in Ba žant et al.2010).Set 2UpdatedFor a better estimate,only the values of q 2,q 5,and εs ∞,governing mainly the response for the first few years,have been estimated from the composition,and the estimates of the remaining param-eters were improved as follows:q 1¼0:188;q 3¼0:262;q 4¼0:140ð×10À6∕psi Þðas changed for set 2Þð3Þwhere q 1was adjusted according to the elastic modulus obtained in the truck load test (Ba žant et al.2010).Here,q 3and q 4were identified by a trial-and-error procedure,conducted with two objectives in mind:(1)stay close to the values of multidecade creep tests,which are only the 30-year tests of Brooks (1984,2005);and (2)obtain the closest possible fit of the measured deflection of the KB Bridge.Fig.3indicates that the selected in-trinsic parameters agree with these tests reasonably well.It has been noted that the compliance function J ðt ;t 0Þagrees with the 30-year tests of Brooks and is in good agreement withthe measured deflections.This result suggests using these tests for recalibrating input parameters q 3and q 4,which are the main controlling parameters of the multidecade creep in Model B3and are difficult to estimate from the database because the database is dominated by test data for load durations <5years.To calculate and compare the predictions of various models,all the properties of the concrete and the environmental histories of the KB Bridge concrete would have to be known,but they are not.Therefore,comparing the predictions of various models ei-ther mutually or with the observations is not fully informative.Nevertheless,what can be compared is whether the observed deflections are within the realistic range of each model.They are indeed within the realistic range for Model B3but not at all for other models,including the ACI,CEB,JSCE,and GL models.For Model B3,the predictions are not fixed because there exist input parameters that are uncertain for the KB Bridge and are thus free to be set within their realistic range.The predictions of the other models are fixed by the reported value of the concrete strength,with no flexibility of adjustment (a partial exception is the JSCE model,which takes into account the water content w and cement content c ).The data available for the KB Bridge,as presented here,do not suffice to obtain a unique compliance func-tion for this bridge unless the default parameter values are used;they do suffice to obtain unique compliance functions for the ACI,CEB,JSCE,and GL models —although at the cost of ignoring many important influences.Some engineers want the model to predict the creep and shrink-age from as few parameters as possible,particularly from the concrete design strength only (ACI 2008a ).This might be more convenient,but it is not realistic.If the additional parameters of Model B3for a given concrete are known,better predictions can be made.If they are unknown,they can be assigned their typical,or default,values,and thus predictions can still be made even if only the strength is known.Furthermore,by varying the influencing parameters of Model B3through their realistic range,a realistic range of expected responses can be explored;and a struc-ture for the most unfavorable realistic combination can be designed.With the other models,one can explore only the effect of strengthvariation.Fig.3.Model B3curve for adjusted q 3and q 4compared with the creep tests by Brooks (1984,2005)JOURNAL OF STRUCTURAL ENGINEERING ©ASCE /JUNE 2012/679D o w n l o a d e d f r o m a s c e l i b r a r y .o r g b y H u a z h o n g U n i v e r s i t y o f S c i e n c e & T e c h n o l o g y o n 03/18/14. C o p y r i g h t A S CE .F o r p e r s o n a l u s e o n l y ; a l l r i g h t s r e s e r v e d .Computed Deflections,Prestress Loss,and Comparisons to MeasurementsBecause of symmetry,only one-half of the bridge was analyzed.A three-dimensional(3D)finite-element program that automatically captured all the stress-redistribution effects attributable to creep was used(see the mesh in Fig.2).As a first check of the program, a comparison was made with the bridge stiffness,which was mea-sured in January1990in a load test by JICA(1990).An average downward deflection of30.5mm(0.10ft)was recorded at midspan when two12.5t trucks were parked side by side on each side of the midspan hinge(a previous paper erroneously assumed that only one truck was parked on each side).The front wheels of the two trucks on each side were assumed to have been3m away from the midspan.The rear wheels,12m behind the front wheels,were assumed to carry60%of the truck weight.The finite-element code predicted the deflection of30mm(0.098ft)that was measured approximately within2.4h(the2.4h creep was based on Model B3Set2)under a load of245kN(55.1kip).Given the uncertainty about the actual rate of loading,the difference was small enough.The results of the calculations are shown in Figs.4–7,both in linear and logarithmic time scales(t−t1=time measured from the end of construction;t1=time when the midspan hinge was in-stalled).The data points show the measured values.The circles re-present the data reported by the firm that investigated the excessive deflections(JICA1990),and the diamonds represent thedata Fig.4.Mean deflections calculated using Model B3and the ACI,CEB(one using SOFiSTiK),JSCE,and GL models in normal and logarithmicscalesFig.5.Mean deflections calculated as in Fig.4but for time extended up to150years(assuming no retrofit and no collapse have taken place) 680/JOURNAL OF STRUCTURAL ENGINEERING©ASCE/JUNE2012Downloadedfromascelibrary.orgbyHuazhongUniversityofScience&Technologyon3/18/14.CopyrightASCE.Forpersonaluseonly;allrightsreserved.accepted from a secondary source (Berger/ABAM 1995a ).For comparison,Figs.4–7show the results obtained with Model B3and the ACI,CEB,JSCE,and GL models.All these responses were computed with the same finite-element program and the same step-by-step time integration algorithm.For Model B3,it was possible to consider the effect of the differences in thickness of the slabs and webs on their drying rates.In Fig.4,the deflection obtained by using the popular commercial program SOFiSTiK,which is based on the one-dimensional beam element model,is also demonstrated (Yu et al.2012).Fig.4shows the calculated deflection curves up to the moment of retrofit at approximately 19years of age.Except for the curves in the JSCE model,the curves differ only slightly from those in Ba žant et al.(2010)because of the input being compensated by various changes.Because a lifetime well beyond 100years is generally expected,Fig.5shows the same curves extended up to 150years under the assumption that there has been no retrofit and,thus,no collapse.Fig.6presents the midspan deflection that is obtained (1)if the drying creep is neglected,(2)if both the shrinkage and drying creep are neglected,and (3)if the shrinkage and the drying creep compliance are considered to be uniform over the cross section and to be deduced from the overall effective thickness D ¼2V ∕S of the whole cross section.The use of uniform creep and shrinkage properties throughout the cross section neglects the cur-vature growth attributable to differential shrinkage and differential drying creep and gives results dominated by the unusually thin webs.Also,the effect of mean drying can be very different from the mean of the effects of drying in the individual slabs (Ba žant et al.1992).The shear lag effect with the associated creep-induced stress re-distributions within the cross sections necessitates 3D simulations.It cannot be realistically captured by the classical concept of effec-tive width of the top slab (which was actually used in the design of the KB Bridge).The computations show that the shear lag occurs in four different ways —in the transmission of vertical shear force because of the vertical reaction at the pier,in the transmissionofFig.6.Deflections in normal and logarithmic scales computed using Model B3for (1)no drying creep;(2)no shrinkage and no drying creep;(3)uniform creep and shrinkage over the crosssectionFig.7.Prestress loss in tendons at the main pier using Model B3and the ACI,CEB,JSCE,and GL models in normal and logarithmic scalesJOURNAL OF STRUCTURAL ENGINEERING ©ASCE /JUNE 2012/681D o w n l o a d e d f r o m a s c e l i b r a r y .o r g b y H u a z h o n g U n i v e r s i t y o f S c i e n c e & T e c h n o l o g y o n 03/18/14. C o p y r i g h t A S CE .F o r p e r s o n a l u s e o n l y ; a l l r i g h t s r e s e r v e d .。

基于SPO语义三元组的自闭症谱系障碍药物知识发现吕艳华，赵宏霞，李琦，梁傲雪，于琦山西医科大学管理学院，山西 030001Drug knowledge discovery for autism spectrum disorders based on SPO predicationsLYU　Yanhua, ZHAO　Hongxia, LI　Qi, LIANG　Aoxue, YU　QiSchool of Management, Shanxi Medical University, Shanxi 030001 ChinaCorresponding Author LYUYanhua,E⁃mail:******************Abstract Objective：To extract SPO（Subject⁃Predicate⁃Object，SPO） from literature related to Autism Spectrum Disorders（ASD） using semantic mining technology and construct a knowledge graph of ASD drug entities，to explore the potential drug for the treatment of ASD at a deeper level， and provide new ideas for discovering valuable potential drugs for other diseases（https：//）.Methods：Using the tools SemRep and Metamap based on the Unified Medical Language System （ULMS） to process ASD literature records and obtain SPO of ASD drug entities.The Neo4j database was used for knowledge storage to construct an ASD drug entities knowledge ing three semantic pathways to discovery ASD drug knowledge based on the knowledge graph.Then verified and analyzed the effectiveness of the results in the clinical trials databases.Results：The SPO obtained includes 1 262 head entities， 687 tail entities， and 18 entity relationships.A total of 32 drugs were discovered through three semantic pathways，27 potential drugs for ASD was screened out，and 19 drugs can be validated in the clinical trials databases.Conclusions：The knowledge discovery of ASD drugs based on knowledge graph which built by SPO can provide a certain theoretical and methodological basis for drug repositioning，provide new ideas for traditional drug discovery，and provide decision support for clinical experiments and scientific research.Keywords autism spectrum disorders； knowledge graph； semantic mining； drug repositioning摘要目的:运用语义挖掘技术抽取自闭症相关文献中的三元组并构建自闭症药物实体知识图谱，深层次开展自闭症治疗的潜力药物知识发现，同时也为其他疾病发现有价值的潜在治疗药物提供新思路。