An implicit upwind algorithm for computing turbulent flows on unstructured grids

Approximation Algorithms for Constrained Node Weighted Steiner Tree ProblemsA. MOSS AND Y. RABANIAbstract We consider a class of optimization problems, where the input is an undirected graph with two weight functions defined for each node, namely the node’s profit and its cost. The goal is to find a connected set of nodes of low cost and high profit. We present approximation algorithms for three natural optimization criteria that arise in this context, all of which are NP-hard. The budget problem asks for maximizing the profit of the set subject to a budget constraint on its cost. The quota problem requires minimizing the cost of the set subject to a quota constraint on its profit. Finally, the prize collecting problem calls for minimizing the cost of the set plus the profit (here interpreted as a penalty) of the complement set. For all three problems, our algorithms give an approximation guarantee of , where is the number of nodes. To the best of our knowledge, these are the first approximation results for the quota problem and for the prize collecting problem, both of which are at least as hard to approximate as set cover. For the budget problem, our results improve on a previous result of Guha, Moss, Naor, and Schieber. Our methods involve new theorems relating tree packings to (node) cut conditions. We also show similar theorems (with better bounds) using edge cut conditions. These imply bounds for the analogous budget and quota problems with edge costs which are comparable to known (constant factor) bounds.1 IntroductionWe consider optimization problems on graphs with node costs and profits. Let be an undirected graph. Let every node have a non-negative cost and a non-negative profit . Our goal is to find a connected set of nodes that has low cost and high profit. There are several ways to cast this goal as an optimization criterion. In this paper we consider three such problems. In the quota problem, we are given a profit quota , and we have to find a set of minimum total cost among those with total profit at least . In the budget problem, the total cost is constrained to be at most a budget . Subject to this constraint, we have to find a set of maximum total profit. Finally, in the prize collecting problem, the (the profit loss). All three problems objective is to minimize the total cost of plus the total profit of . Clearly, an algorithm for the also have a rooted version, where must contain a specified node rooted version can be used to solve the unrooted version, by enumerating over all possible roots. We give approximation guarantees for the rooted (and thus the unrooted) quota problem, for the (rooted) budget problem, and for the (rooted) prize collecting problem. Our result for the budget problem is a bicriteria approximation in the sense that the approximation algorithm is allowed to exceed the budget by a factor of . The quota problem, as well as the prize collecting problem, are at least as hard to approximate as set cover, so our guarantees are asymptotically the best possible under reasonable assumptions on the complexity of NP-hard problems (see, for example, the survey by Arora and Lund(1997)). By the same token, the budget problem is at least as hard to approximate as maximum coverage, so there is a constant lower bound on its approximability under the same assumptions (see Khuller, Moss, and Naor (1998)). In addition to these new results, our methods can be used to derive previously discovered approximation 1guarantees for some related problems. Our solutions are more uniform, and perhaps more elegant, than previous results. See the discussion below for more details. Most previous related research was done on closely related problems with edge costs instead of node costs. (The cost of a set of nodes is the total cost of its minimum spanning tree.) These problems are NP-hard, and in recent years constant factor approximation algorithms were found for most of them. Goemans and approximation algorithm for the prize collecting Steiner tree Williamson (1995) give a primal-dual problem, which is the edges costs version of our prize collecting problem. Following the ground-breaking work of Blum, Ravi, and Vempala (1996), Garg (1996) gives a -approximation (as well as a simpler approximation) for -MST, which is a special case of the edge costs version of our quota problem, with unit profits and a quota of . Arora and Karakostas (2000) improve Garg’s approximation guarantee to , for all . The constant factor approximations of the latter three works are derived by using the Goemans-Williamson prize collecting Steiner tree algorithm on the graph with uniform profits. The profit is determined (using binary search) to yield a tree (more precisely, a convex combination of two trees) of size . As noted by Chudak, Roughgarden, and Williamson (2001), Garg’s -MST -approximation algorithm can be recast in terms of a Lagrangian relaxation for the problem, similar to the treatment by Jain and Vazirani (1999) of the -median problem. Awerbuch, Azar, Blum, and Vempala (1995) (in a previous -MST paper giving polylogarithmic approximation guarantees) note that a polynomial time -MST approximation algorithm can be used to get a pseudo-polynomial time approximation algorithm with the same guarantee for the (edge costs) quota problem. Johnson, Minkoff, and Phillips (2000) note that for the above-mentioned constant approximation MST algorithms, the pseudo-polynomial time algorithm can be converted into a truly polynomial time one. Moreover, they show that such an algorithm can be used to solve the (edge costs) unrooted budget problem, losing a constant factor in the approximation guarantee. The budget problem (with node costs) was introduced by Guha, Moss, Naor, and Schieber (1999), who motivate it by applications to problems in maintenance of electric power networks. They give an approximation guarantee for the unrooted version. They also show how to obtain a similar approximation guarantee for the rooted version using a set that has total cost at most twice the allowed budget . Their algorithm is based on an approximation algorithm for the node weighted Steiner tree problem by Klein and Ravi (1995). This problem is similar to the well-known Steiner tree problem, except that nodes and not edges have costs. The problem is at least as hard to approximate as set cover. As pointed out by Guha et al., the algorithm of Klein and Ravi is implicitly a primal-dual algorithm. The starting point for all our algorithms is a standard linear programming relaxation for the rooted version, where nodes are chosen fractionally to be in the output set , and the connectivity requirement is expressed as constraints on (node) cuts. For the quota and budget problems we show that any feasible solution to the linear programming relaxation can be approximated by a convex combination of connected sets of nodes containing the root. Moreover, such a convex combination is computable in polynomial time. It follows from an averaging argument that a good set can be found. Our algorithm for the prize collecting problem is used to construct the convex combination. It combines ideas from both the Klein-Ravi node weighted Steiner tree algorithm (with its primal-dual interpretation by Guha et al.) and the Goemans-Williamson prize collecting Steiner tree algorithm. Both the region growing process and the final delete step are more complicated in our algorithm than in either of those algorithms. We then use the solution to the prize collecting problem to prove the following theorem: Theorem 1. Let be an undirected graph with non-negative node weights . Let , and assume that for every , and . Furthermore assume that for every node , the minimum weight node cut separating and has weight of at least . Then, there exist polynomial time algorithms that compute 21. a packing in of connected sets containing such that for every node and ; and, containing is between 2. a packing in of connected sets containing such that for every node and . containing is between, the total weight of sets , the total weight of setswhere, in both cases, is an absolute constant. Notice that the second claim implies the first. We state both claims for ease of application. For optimization problems that can be formulated as positive integer programs, Carr and Vempala (2000) prove that an approximation algorithm for the problem can be used to generate a packing of integer solutions that approximates a feasible solution to the LP relaxation of the integer program with the same guarantee. Our results extend their results, and use an approximation algorithm for a different problem to generate the packing. Our approximation guarantees for the budget and quota problems follow from applying the packing algorithms to the solutions for the linear programming relaxations we use, and then using averaging arguments to find good integer solutions. We can also show an analogous packing theorem for the case of edge capacities. Theorem 2. Let be an undirected graph with non-negative node weights and non-negative edge capacities . Let with . Assume that for every node , the minimum capacity edge cut separating and has capacity of at least . Then, there exist polynomial time algorithms that compute , the total weight of trees containing 1. a packing in of trees rooted at such that for every node is between and , and for every edge , the total weight of trees containing is at most ; and, 2. a packing in of trees rooted at such that for every node , the total weight of trees containing is between and , and for every edge , the total weight of trees containing is at most . The celebrated theorem of Nash-Williams (see Diestel (2000)) implies such packings in the case of for all . One of the consequences of Theorem 2 is a modification of Garg’s -approximation for -MST avoiding the Lagrangian relaxation. A similar modification (using another packing theorem) can be applied to the -approximation for metric -median of Jain and Vazirani. It is not clear if the better algorithms that use continuity properties of the Lagrangian relaxation (for example, Garg’s -approximation for -MST or the -approximation for metric -median of Charikar and Guha (1999)) can be derived from our packings. The rest of the paper is organized as follows. In Section 2, we present the primal-dual algorithm for the prize collecting problem. In Section 3, we present the proof of Theorem 1. In Section 4, we give the algorithm for the quota problem. Finally, in Section 5, we give the algorithm for the budget problem.2 The Prize Collecting ProblemIn the prize collecting problem, one is given an undirected graph with a cost function , a profit function , and a specified root . The objective is to find a subtree of containing is minimized. In this section we present an approximation the root such that algorithm for the prize collecting problem and analyze its approximation ratio. This algorithm is used to obtain the results in the following sections. 32.1The Algorithm. Observe that the prize collecting problem can be formulated as the following integerLet program:minimizesubject to (1) (2)where and s.t. . A linear programming relaxation (denoted PC-LP) is obtained by replacing the last two sets of constraints with . Consider the dual program for PC-LP, denoted by PC-D: maximize subject toThe algorithm we propose for the prize collecting problem is a primal-dual algorithm which greedily constructs an implicit solution to the dual problem, PC-D. Partition the vertices of into cheap vertices for which and expensive vertices, which are the for each cheap , and for each expensive . Consider the rest of . Implicitly set connected components induced by cheap vertices and the root . Let denote the set of these components. For each vertex , define the residual cost and the residual penalty . The algorithm greedily constructs a packing which together with the values of determined above, is a feasible solution to PC-D, i.e., it satisfies: cheap expensive cheap (3) (4) , ,The algorithm maintains a set of active and inactive components. We say that is deactivated iff it changes its status from active to inactive. Initially, , and all the components are active, corresponding to except for the component containing the root. We raise uniformly the dual variables each active component, until either constraint (3) becomes tight for some expensive vertex , or constraint (4) becomes tight for some active component . In the former case, the vertex joins a component such that , and in case there are several such components these components are merged. In the latter case, the component gets deactivated. The component containing the root remains inactive throughout the algorithm, and the process terminates when no active components remain. The algorithm also builds a connection tree which contains edges by which expensive vertices join components. At the end of the 4algorithm, we perform a deletion step on the tree . During this step, a set of vertices is expendable iff its removal does not disconnect any remaining cheap vertex from . The code in Fig. 1 defines the algorithm more rigorously. The variables maintain the values , and the variables maintain the values . The algorithm does not need to maintain explicitly the values . Their computation is included in the code for the purpose of analysis.2.2Analysisapproximation guarantee for the primal-dual algo-Next we prove Theorem 3 that establishes an rithm. Theorem 3.where.Proof. Let be the set of cheap vertices not spanned by the final solution , and let denote the set of cheap vertices spanned by . Also, let be the set of expensive vertices spanned by . Recall that for each cheap vertex , and for each expensive vertex , . Therefore, to establish the claim of the theorem, it suffices to prove that the following inequality holds:where. We establish the inequality above by proving that the following two inequalities hold:(5) (6)First, observe that Inequality (6) follows from the greedy construction of the dual solution by the algorithm. of maximal components deactivated by the algorithm due to the residual penalty Indeed, consider the set constraints (4), such that no vertex of the component is included in the final solution . Clearly, these contains some cheap vertex, we get: components are disjoint, and as each with non-zero value ofTo see the last equality, notice that by the elimination step of the algorithm every vertex in some deactivated component not containing a vertex from .is included inIn the rest of the proof we show that Inequality (5) holds. We refer to vertices that caused two or more components (active or inactive) to be merged as merge vertices. We proceed by establishing the following properties of the dual solution constructed by the algorithm. Note that it can be easily shown by induction that at each step of the algorithm. 5PrizeCollecting Initialize: for all for all for all All are active, except for the union of spanning trees for Main loop: while active Let Letdoactive Find that minimizes Let cheap Find an active that minimizes for all active , for all active , for all active if then Deactivate Label all Let Let Let,by labelelseargmax,if elsethen is inactiveis active endif Add to the node set of Add to the edge set of , for every endif endwhile Deletion step: Remove from nodes that are disconnected from . while cheap labeled s.t. is expendable do Remove from endwhile while expensive that is expendable do Remove from endwhile Output .Figure 1: Algorithm PrizeCollecting for the prize collecting problem 6Lemma 4. Let be a simple path in the connection tree is not a merge vertex, and gets connected to by an edge connected to it holds: dist where dist costs of and is the distance from . to insuch that for each . Then at the moment, getswith respect to the cost function, not including theProof. We prove the claim of the lemma by induction on . If the increase of dual variables caused by . Then by ,, let before , and after the increase of dual variablesproving the basis of the induction. For the induction step, suppose that the claim of the lemma holds for vertices , and consider the moment when gets connected to via the edge . By entered , it holds that . Let the induction hypothesis, when at the current iteration. As participates only in those sets that got non-zero values after entered , it holds thatThe increasein the dual variables, caused by, is, and therefore, whenjoins , we haveLemma 5. Let , immediately after the merge,be components merged via an expensive vertex . Let argmax , that is, is an edge in by which gets connected to . ThenProof. Without loss of generality, let be inactive. Putbe active at the time of the merge, and letbefore the merge, for each. Then the increase of dual variables, induced byisSince dual variable of each of the components it holds thatgets increased by this amount, after the merge7Divide the algorithm into phases, so that at the end of each phase, the number of active components condenote the set of such components taining a cheap vertex spanned by the final solution is decreased. Let at the end of phase of the algorithm, and let be the number of such components at the end of phase . Clearly, is at most the number of cheap vertices, which is bounded by . The decrease in can result either from the merge of two or more components from , where is the component containing the root, or from deactivation of some component from . In the former case, let be the components from merged at the end of phase , and let be the corresponding merge vertex. In the latter case, let be the component deactivated at the end of phase , and let . For each phase , we bound the residual cost of a subtree of such that . Before defining , let us consider a phase ending in deactivating a component . A vertex from can appear in the final solution if and only if the removal of and from disconnects a pair of cheap vertices or a cheap vertex and the root in . Consider the path in between the first pair of such vertices that get connected using a vertex from . If the removal of disconnects the pair, let and be the first and the last vertex from , respectively, along the path between and . If the removal of a vertex from disconnects and , let be the neighbor in of the first vertex from connecting and . We say that the vertices as above become connection vertices at the end of phase . Now consider the forest constructed by the algorithm by the end of phase . Let be the subforest of consisting of trees spanning active and connection vertices within each connected component of . Let . If phase ends with a merge, let be the set of neighbors of merge vertices in , so that for every there is a neighbor which is a merge vertex. Define . If phase ends in deactivating a component , then if the removal of disconnects a pair of active vertices with connection vertices and , define . Otherwise, if the removal of a vertex from disconnects a pair of active vertices, and is a connection vertex, then define . Note that by Lemma 5, . Lemma 6.Proof. Let denote the sum of the values of for each iteration of the algorithm, till the end of phase . First, consider a phase ending in a merge of active components via a merge vertex . Then is a set of paths from some cheap vertex in each to , not including the paths within components to by inactive at the beginning of the phase . Denote the path from an active vertexwhere are merge vertices and . The contribution of such path toare paths within components inactive in the beginning of the phase is, by Lemmas 4 and 5, at most8The last inequality follows since only one component containing are increased by a value of . As there are paths contributing to the cost of , we getis active at each time the dual variables .Now consider a phase ending in deactivation of a component . Then is a set of at most two paths between connection vertices , to cheap vertices in . By the same reasoning as above, each of these paths contributes at most to the cost of , therefore we get . Observe that each component active at the beginning of phase must contain a vertex that has always been in some active component since the beginning of the algorithm. Clearly, for such vertex , . Therefore,Therefore, we getLet denote the total number of phases. We can now apply a theorem of Klein and Ravi (1995) to establish is at most that the residual cost of the subgraph . By Lemma 6, the cost of the subgraph added at the last phase of the algorithm is at mostTherefore, Inequality 5 follows. This completes the proof of Theorem 3.3 Tree PackingsIn this section we prove Theorem 1. We prove part 1 of the theorem first, as the proof is somewhat simpler to follow. Notice that part 2 of the theorem implies part 1. Let . We wish to show that for such that , for every , , and (7)9there exists a packing of connected node sets containing , such that has weight , and such that for every node , the following property holds:in the packing, (8)where . The best packing satisfying the above property is given by the solution to the following linear program which we denote CLP. maximize subject to (9)whereand.The dual program, which we denote by CD, is minimize subject to (10)where.. Consider Let be the approximation guarantee for the prize collecting problem. We have now a modified program, which we denote by MCD, where the constraints 10 are replaced by the constraints (11) Lemma 7. Let CD and MCD be the optimal values of CD and MCD, respectively (with the same coefficients ). Then, CD MCD . Proof. If is a feasible solution to CD, then is a feasible solution to MCD.Let be a feasible solution to CLP. Note that . This follows from the fact that the root is contained in every tree, and therefore, the inequality above is implied by constraint (9) for . Observe that if we could find in polynomial time a solution to CLP of value , it would induce a packing . of sets satisfying the property (8). Indeed, such packing could be obtained by picking sets with Unfortunately, the linear program CLP has an exponential number of variables, and therefore cannot be solved in polynomial time by a linear programming algorithm. We overcome this problem by solving the modified dual program MCD. This program has an exponential number of constraints, but it can be solved in polynomial time using the ellipsoid algorithm, given a separation oracle. (Each constraint of MCD has a short description, see Gr¨ tschel, Lov´ sz, and Schrijver (1993) for the conditions required for applying o a ellipsoid.) Next we describe a separation oracle for MCD, which can be applied under the assumption that . We show that such an oracle suffices for computing a solution that suits our purpose. Formally, under the assumption set such that , we wish to find a set violating the constraint (11), i.e., a (12) The following lemma provides a method for finding such a set. 10Lemma 8.Let so that and ,where is a vector satisfyingthe conditions of Theorem 1.Then the setproduced by PrizeCollecting for the instance of the prizecollecting problem with and ,,satis fies Inequality (12).Proof.By Theorem 3,PrizeCollecting produces a set which satis fies:PC -OPT (13)where PC -OPT is an optimal value of PC-LP for the problem instance described above.De fine a feasible solution to PC-LP as follows.Number the vertices ofso that ,.De fine ,for .SetFirst,observe that this is,indeed,a feasible solution to PC-LP.To see that the constraints (1)are satis fied,consider any set.Let be a vertex with maximal in .Then sets with non-zero containing are exactly the sets .Therefore,we get .Thenconstraint (1)is satis fied for as satis fies constraint (7)for and.It can be easily veri fied thatconstraints 2are also satis fied.Now consider the value of the solution to PC-LP described above.Observe that ,.Therefore,each vertex ,contributes its penalty multipliedby to the objective function value.Thus,we get that the value of this solution is.As this value is not smaller than the optimal value for PC-LP,by (13)we getThe latter inequality follows by the assumption that.Therefore,it follows thatwhich implies the lemma.We use the separation oracle described in the lemma above on the set of constraints of MCD together with the constraint ,until no feasible solution satisfying the latter constraint and the constraintsalready used by the algorithm can be found.At this point,the optimal value of MCD with the subset of constraints used by the ellipsoid algorithm is at least 1,and therefore the optimal value of CLP with just thevariables corresponding to the used constraints is at least.Therefore,we can solve CLP with just thosevariables to obtain the packing of sets satisfying(8).We now proceed with the proof of part2of Theorem1.The proof structure is essentially the same as the proof of part1.However,some of the details are more complicated.Let.We show that for such that,for every,,and such thatconstraints(7)are satisfied,there exists a packing of connected node sets containing,such thathas weight in the packing,,and such that for every node,the following propertyholds:(14)where.The best packing satisfying the above property is given by the solution to the followinglinear program which we denote CLP’.minimize subject to(15)where and.Consider the dual program for CLP’,denoted CD’:maximize subject to(16)where.We modify CD’by replacing constraints16by:(17)We denote the modified dual program by MCD’.By the argument,similar to that of the proof of Lemma7,Next we show a separation oracle for MCD’,which can be applied under assumption.Formally,we wish tofind a set that violates constraint(17).Similarly to the proof of Lemma8,we applyPrizeCollecting to an instance with costs,and penalties.Let be the set produced by the algorithm.By the same reasoning as in the proof of Lemma8,we get:Since,by our assumptionwe get:or,equivalently,Since,it follows thatimplying that the set violates constraint(17).We use the separation oracle described above on the set of constraints of MCD’together with the constraint ,until no feasible solution satisfying the latter constraint,and the constraints alreadyused by the algorithm,can be found.At this point,the optimal value of MCD’with the subset of constraints used by the ellipsoid algorithm,is at most1,and therefore the optimal value of CLP’with just the variables corresponding to the used constraints is at most.Therefore,we can solve CLP’with just those variablesto obtain the packing of sets satisfying(14).4The Quota ProblemIn the quota problem,given an undirected graph with a cost function,a profitfunction,a specified root and a quota,the objective is tofind a connected subset ofcontaining such that the total profit of is at least,and the total cost of is minimized.For every node,we denote by the minimum cost of a path connecting and.Notice that in dealingwith the quota problem we may eliminate nodes with.If the optimal solution contains sucha node,then the optimal solution is a least-cost path connecting and.We can compute such a pathfor every node with and compare its cost to the solution produced by the algorithm describedbelow.Furthermore,let Q-OPT denote the cost of the optimal solution for the quota problem.Clearly,if Q-OPT,then is not contained in any optimal solution.We can eliminate nodes with Q-OPTby enumerating over possible values for Q-OPT.The only interesting values for this purpose are the values ,for all nodes(i.e.,for we eliminate all nodes with).In the following discussionwe assume that does not contain nodes with or withQ-OPT.Consider the following linear programming relaxation for the quota problem(denotes),whichwe denote by Q-LP.minimize subject to(18)Note that constraints(18)imply,.Further note that Q-LP can be solved using the ellipsoidalgorithm(a separation oracle requires computing minimum node cuts).。

软件学报ISSN 1000-9825, CODEN RUXUEW E-mail: jos@Journal of Software,2011,22(11):2729−2748 [doi: 10.3724/SP.J.1001.2011.03900] +86-10-62562563 ©中国科学院软件研究所版权所有. Tel/Fax:∗融合安全的网格依赖任务调度双目标优化模型及算法朱海+, 王宇平(西安电子科技大学计算机学院,陕西西安 710071)Integration of Security Grid Dependent Tasks Scheduling Double-Objective OptimizationModel and AlgorithmZHU Hai+, WANG Yu-Ping(School of Computer Science and Technology, Xidian University, Xi’an 710071, China)+ Corresponding author: E-mail: zhu_sea@, Zhu H, Wang YP. Integration of security grid dependent tasks scheduling double-objective optimizationmodel and algorithm. Journal of Software, 2011,22(11):2729−2748. /1000-9825/3900.htmAbstract: In order to solve the security threats that dependent tasks scheduling problems face under theheterogeneous grid environment, this paper takes into account the inherent safety and behavior of security of thegrid resource node and the reliability of measurement functions in the grid resource node. In addition, the behaviorin credibility assessment strategies are also constructed. In order to establish the subordinate relationship betweenthe security requirements of the task nodes and resources security attributes, security benefits of the membershipfunctions are defined. Hence, a grid task scheduling model for security integration is established. On this basis, therequirement representation model and the grid resource topology model are defined; thus, the models of double-objective optimization of grid task scheduling are proposed. In order to solve this model, the definition of depthvalues and the sort of coupling is introduced when dealing with the constraints between tasks. A particle evolutionequation is re-defined and re-designed to consider the specific characteristics of the grid task scheduling problem.At the same time, a selection strategy is defined, based on the uniformly distributed vector and concentration ofparticles. Thus, this paper presents a multi-objective optimization of grid task scheduling particle algorithm, and thealgorithm is proved to be viable by applying the relevant knowledge of a probability theory. Simulation results showthat compared with similar algorithms, under the same conditions, this algorithm has a faster convergence speed anda better performance in double-objective optimization.Key words: grid computing; dependent tasks scheduling; security integration model; double-objectiveoptimization; evolution equation; uniform distribution; discrete particle swarm optimizationalgorithm摘要: 为了解决异构网格环境下依赖任务调度问题面临的安全威胁,综合考虑网格资源节点的固有安全性和行为安全性,分别构建了一个网格资源节点身份可靠性度量函数和行为表现信誉度评估策略.同时,为了确立任务安全∗基金项目: 国家自然科学基金(61103143, 60873099); 国家教育部博士点基金(20090203110005)收稿时间:2009-12-28; 修改时间: 2010-03-30; 定稿时间: 2010-06-10CNKI网络优先出版: 2010-12-29 13:50, /kcms/detail/11.2560.TP.20101229.1350.000.html2730 Journal of Software软件学报 V ol.22, No.11, November 2011需求与资源节点安全属性之间的隶属关系,定义了安全效益隶属度函数,从而建立一个网格任务调度的安全融合模型.以此为基础,提出一个时间-安全驱动的双目标优化网格依赖任务调度模型.为了求解该模型,处理任务间约束关系时引入深度值和关联耦合度的排序定义,再结合网格任务调度问题的具体特点,重新定义和设计新的粒子进化方程.同时,基于均匀分布向量和粒子浓度定义了选择策略,从而提出一种双目标优化的网格依赖任务调度粒子群进化算法,并运用概率论的有关知识证明算法的收敛性.最后,对所提出的离散粒子群进化算法进行了多角度分析和大规模仿真实验,其仿真结果表明,该算法与同类算法相比,不仅具有较好的收敛速度和单目标优化性能,而且在任务调度长度和安全满意度方面具有更好的双目标优化综合性能.关键词: 网格计算;依赖任务调度;安全融合模型;双目标优化;进化方程;均匀分布;离散粒子群算法中图法分类号: TP311文献标识码: A网格将互联网中的计算资源、存储资源、信息资源、知识资源等多种资源组织在一个统一的框架下[1],为各种复杂的应用任务提供服务资源.因此,应用任务在各种资源间的有效调度就成为网格应用系统获得高性能的关键因素之一.然而,由于网格环境具有异构性、分布性、开放性、不确定性及动态性等特征,对传统的调度策略提出了新的挑战.任务在网格平台调度执行时,除了满足传统调度策略中的时间性能需求以外,还必须面临网格环境的开放特性可能造成敏感数据在执行或传输过程中被泄密、篡改或冒名顶替等风险[2,3];同时,由于网格资源节点的行为属性失效[4]任务需要重新调度或延迟执行等,因此,应用任务在网格平台的安全可靠调度成为一个新的必须要考虑的因素.针对此问题,本文提出了一个网格任务调度的安全融合模型.该模型综合考虑异构网格环境下资源节点的固有安全性和行为安全性,根据资源节点本身所采用的加密算法、Hash函数及身份认证技术类型构造资源节点的身份可靠性度量函数,同时根据资源节点历史行为表现构建节点的信誉度动态评估策略,并且定义安全效益隶属度函数,使任务安全需求和资源节点安全属性间关系得以确立.当前,网格任务调度的研究大多针对独立任务或元任务的特殊形式[5,6],忽视了任务间的数据关联与优先约束关系,不能反映应用任务间的实际特征.具有依赖关系的任务调度在传统调度策略中的研究由来已久[7],但通常很少考虑任务间的通信关系以及资源节点的异构性带来的链路竞争等影响.典型的依赖任务调度模型都是建立在图的基础之上[8,9],也就是任务图优先模型.根据任务图的基本信息、处理单元本身及其拓扑结构的基本信息是否在应用任务调度前获得、已经调度好的任务是否可以迁移等因素,将任务调度分为静态调度和动态调度两大类.本文对具有依赖关系的静态网格任务调度问题,基于安全融合模型将不同网格任务的时间性能和安全性能等需求和网格资源服务水平结合起来,使网格任务调度在满足任务间依赖关系的约束下将任务调度长度和安全效益值达到最优,从而建立了一个双目标优化新模型.如何把复杂的应用任务合理调度到网格资源节点上有效执行,已被证明是一个NP难完全问题.不少学者将遗传算法、模拟退火算法和蚁群算法等[10,11]应用到任务调度,并取得了很好的效果.粒子群算法作为一种新的群智能算法[12],具有收敛速度快、容易克服早熟缺陷和分布式运算等优点,并且操作简单,易于实现,因此一经提出就受到广泛关注,目前已经在函数优化领域取得了成功的应用.但对粒子群算法的研究目前主要集中在连续优化问题的方面[13],在离散组合优化方面,特别分配调度问题的研究非常有限[14],而且多为求解单目标优化问题.另外,粒子群算法在求解离散组合优化问题时,由于当前粒子与最优粒子位置难以用定量的方式表示,导致粒子的速度和位置不能参照标准粒子群进化方程更新,此时基本PSO失效.为了求解本文提出的新模型,结合双目标优化的网格任务调度问题具体特点,运用粒子群算法运行机理对粒子的位置、速度及其运算规则进行了重新表示,设计了新的粒子进化方程,并基于均匀分布和浓度定义了新的选择策略来保证双目标非劣解集的分布均匀性;同时,为了处理依赖任务间约束关系在算法设计中引入任务深度值和关联度的排序定义,从而提出一种双目标优化离散粒子群算法(discrete particle swarm optimization,简称DPSO),并运用概率论的有关知识证明算法的收敛性.本文第1节对相关工作进行阐述.第2节给出双目标优化的网格资源任务调度体系框架和网格任务调度过程的简要描述.第3节着重对网格资源安全融合模型进行探讨研究;在第4节提出网格任务调度的双目标优化朱海等:融合安全的网格依赖任务调度双目标优化模型及算法2731模型.根据任务调度组合优化问题的具体特点,在第5节提出一种双目标优化的粒子群进化算法.第6节进行仿真实验与性能分析.最后一节对本文所做工作进行总结和展望.1 相关工作传统的任务调度策略,比如DSL,TCS等[15,16],虽然都比较成功地应用到调度系统中,但通常忽略了任务调度对安全的需求,也没有考虑到网格资源节点的开放性及动态性等特征,从而使调度系统难以在开放、动态、真实的网格环境中有效运行.近年来,有不少学者也开始关注研究此问题.如,文献[17]对同构网格环境下的实时任务调度应用融入了安全因素,但没有考虑网格节点异构性和不确定性等因素;文献[18]针对网格资源节点的不确定性,参考社会人际关系信任模型建立了网格节点信任推荐机制,有效提高了任务在信任方面的服务质量需求,但是对网格资源节点本身固有的安全性欠缺考虑;文献[19]对传统批作业调度问题进行信任扩展,考虑了信任机制和调度机制的关系,但对信任表达并没有给出具体量化处理办法,在实际网格中无法应用.目前的这些相关研究工作大多数仅仅关注资源的可靠性而忽视安全性,特别是对任务需求和资源属性间的关系缺乏把握,调度机制和安全机制的分离,导致调度系统难以在开放、动态真实的网格环境中有效运行.本文基于现有工作基础并针对其不足提出了一种安全融合模型,综合考虑了网格资源节点的固有安全性和行为安全性,采用安全效益函数使任务安全需求和资源节点安全属性间关系得以确立,较好地解决了此问题.随着网格应用研究的深入,对网格任务调度,特别是依赖网格任务调度问题的研究已有不少相关工作.如文献[20]对传统同构调度方案向异构进行了扩展,同时考虑任务的执行时间以及任务之间的通信时间.但由于其在计算过程中使用平均计算时间和平均通信时间,因而忽略了资源的差异性,不能适用于资源个体差异较大的网格环境中.文献[21]根据资源的能力分配任务从而实现资源的负载平衡,进而消除资源差异造成的影响.但异构资源节点间通信及资源本身安全性考虑欠缺,没有从根本上解决资源差异性问题.文献[22]将网格依赖任务可能的资源分配方案表示成任务资源分配图,在此基础上提出了优化选取的依赖任务调度模型,把依赖任务调度问题转化为图的优化选取问题,在资源差异较大及存在大量数据通信传输时取得了较好的效果,但由于它也没有考虑网格资源节点及链路本身的安全可靠性,不能直接适用于动态开放的网格环境.上述这些依赖网格任务调度的研究主要针对时间性能指标建立单目标优化模型,在一定程度上解决了网格异构性面临的问题,但对网格环境开放性带来的安全性欠缺考虑.鉴于这些不足,将本文提出的安全模型融合到依赖网格任务调度问题中,提出了时间-安全优化的双目标调度模型,并引入深度值和关联耦合度的排序定义,较好地处理了任务间的依赖约束关系.对网格任务调度算法的研究,目前主要在QoS需求建模基础上,采用调度启发式来直接构造最终调度方案.已有不少研究者进行了基于多QoS约束的网格任务调度算法研究.文献[23]提出了一种QoS-Min-min启发式调度算法,采用的调度任务分为高、低两种服务质量需求,通过优先调度高服务质量的任务来满足用户.但由于其解决独立任务调度问题,并不适合解决依赖关系任务调度问题.文献[24]根据负载的情况进行调度,解决了任务调度的NASH均衡问题,但未考虑不同节点执行效率的问题,因而不能将调度长度降到最低.文献[25]将任务与聚类资源相匹配并实施调度,提出一种网格资源多维性能聚类任务调度算法,但没有在全局范围比较最优解,不能保证调度算法的收敛性.文献[26]提出了一个多QoS模型,基于这个模型比较了QSMTS-IP,GA,Least Slack First和Sufferage等几种启发式算法的性能.以上这些启发式调度策略考虑了任务的多个目标需求,将多目标聚合成单一目标函数处理.这种方法简单而有效,因此被广泛研究和采用,但其自身也存在一些固有的缺陷:由于多目标优化问题的解并非唯一的,而是存在一个最优解集,集合中的解称为Pareto最优或非劣解.而单目标优化算法仅能根据聚合函数得到决策空间的一个可行解,降低了最终解的质量,缺乏灵活性和扩展性.更为合理的途径是采用多目标组合最优化算法来解决这个问题,基于进化理论的粒子群算法是其中较为有效的方法之一.粒子群主要被设计为在连续论域中搜索数值函数的最优值,并且实验证明它是一个非常有效的工具,但在离散论域中PSO算法的研究非常少.文献[27]对电网机组离散量的高维非线性控制问题,用基于二进制编码的PSO处理机组开工控制,同时用实数编码PSO求解经济负载分配问题,两个算法同时运行组成混合PSO算法,2732 Journal of Software 软件学报 V ol.22, No.11, November 2011取得了较好的效果.但由于其基于连续空间生成的连续解与目标函数评价值存在多对一映射,不能完全反映解的质量.文献[28]针对TSP 问题用所有城市的一个排列表示粒子的一个位置,并引入了基本交换序的概念,在求解14个城市的TSP 问题时只搜索问题空间的0.064%就找到了最优解.文献[29]把任务分配问题映射为一个N维空间的搜索问题,由于位置在速度作用下会产生负数且不是整数,采用了舍去符号和小数方法,使速度作用的位置依然是合法搜索空间的位置,并重新定义了粒子方程,对单目标优化取得了不错的效果.本文在这些工作的基础上并针对其不足,结合网格任务调度的双目标组合优化问题具体特点,运用粒子群算法进化机理对粒子的位置、速度及其运算规则进行了重新表示,设计了新的粒子进化方程,同时基于均匀分布向量和粒子浓度定义了新的选择策略,从而提出一种双目标优化的网格任务调度粒子群进化算法.2 网格资源任务调度体系框架双目标优化的任务调度器可以设计成一个中间件,然后插入到网格资源系统中,从而使网格任务能够有效分配到目标性能达到最优的节点上执行.这样,一方面有效降低了任务调度长度,另一方面尽可能地提高了任务执行的完全性和可靠性,较好地满足了网格应用的服务质量需求.网格资源任务调度的体系架构如图1所示.网格资源任务调度体系架构的最底层为网格资源层(包括节点局部调度器),第2层为网格中间件层,第3层为任务全局调度器层,最上一层为网格应用任务客户端.在全局调度器中,调度顾问为基于安全模型的离散粒子群算法. Gridapplication ...Grid middlewareTask queue Task scheduler Scheduling consultant SecurityIntegrationmodel Behavioral security Inherent security Authentication technologyLocalscheduler Grid monitor...Grid application GridapplicationHash function EncryptionalgorithmTask successrateNodeutilization Local scheduler LocalschedulerFig.1 Architecture of grid resource task scheduling图1 网格资源任务调度体系框架图在基于安全融合模型的双目标优化网格资源任务调度系统框架下,一个网格用户提交并执行一个网格任务的过程如下:朱海 等:融合安全的网格依赖任务调度双目标优化模型及算法2733(1) 应用客户端将网格应用提交到任务队列进行排队. (2) 任务调度器(全局)从任务队列中取出一个网格应用中所有具有依赖关系的子任务,同时与调度顾问进行交互.(3) 调度顾问与网格监视器和安全融合模型交互.(4) 网格监视器将网络目前链路状态和可用资源信息反馈给调度顾问.(5) 安全融合模型通过分析网格监视器反馈的可用资源信息,对资源节点的调度成功率及利用率进行分析获得行为安全性;同时,根据资源节点加密水平等获得固有安全性,然后将网格资源的安全信息反馈给调度顾问.(6) 调度顾问将网格监视器和安全融合模型反馈的信息传递给任务全局调度器,通过网格中间件将所有子任务分配到较优资源节点集执行.(7) 局部调度器对其控制范围内网格资源节点上任务进行最优调度.3 网格资源安全融合模型3.1 资源节点的身份可靠性度量函数网格资源节点的身份可靠性确保主要是由其采用的算法或方法决定的:如保密性一般主要依赖不同加密算法(如IDEA,DES,RC5,Blowfish 和RC4等)实现,预防任务在网格环境中执行或传输时暴露给未经授权的其他用户或进程,避免信息泄露;完整性主要通过不同的Hash 函数(如MD4,RIPEMD,SHA-1和Tiger 等)来实现,确保任务在网格平台下执行时不会被非法的用户修改或篡改;真实性使用不同的数字签名技术(HMAC-MD5,HMAC-SHA-1和CBC-MAC-AES 等)对通讯实体身份的真实性进行鉴别,保证所处理的任务是从合法的用户提交的.下面以保密性为例,说明如何合理设计网格资源节点的保密性安全水平值.假定在网格环境下所有资源节点共采用了8种加密算法[3],见表1.Table 1 Encrypt algorithms and their security value表1 加密算法及其安全水平值Encrypt algorithm Algorithm performance (KB/ms)Security levelRC4 96.43 0.14Blowfish 37.5 0.36Knufu/Khafre 33.75 0.40RC5 29.35 0.46Rijndael 21.09 0.64DES 15 0.90IDEA 13.5 1.00将性能最低的IDEA 对应的保密性安全水平值假定为1,其他任一网格资源节点r u 上加密算法的安全水平值根据其性能可由公式(1)计算获得:13.5/(),18u u e e r r SL k k μ=≤≤ (1)这样,根据加密算法的不同性能将其安全值设定为0.08~1之间的值.可以看出,加密算法的保密性安全水平值与它的性能成反比例关系,安全水平值越低,其性能一般越高.这也符合一般逻辑思维,在同等条件下,没有人会选一个安全水平低而其性能也低的加密机制.同理,网格资源节点r u 根据其采用的Hash 函数和数字签名技术类型,得到其完整性和真实性水平值分别为u er SL 和.u a r SL 定义1(节点的身份可靠性). 节点的身份可靠性指其上执行任务时所能够提供的保密性、完整性和真实性等安全服务保障能力.对任一网格资源节点r u ,若只考虑保密性、完整性和真实性等安全性能,则其身份可靠性安全水平值为2734Journal of Software 软件学报 V ol.22, No.11, November 201112331s.t. 1,001, {,,}u u u u e g a r r r r i i i k SL SL SL SL SL k e g a ωωωωω=⎫=++⎪⎪=⎬⎪⎪∈⎭∑≥≤≤ (2) 在公式(2)中,ωi 表示不同安全服务的权重,权重越大,表示其相应的安全服务越重要.3.2 资源节点的信誉度评估策略定义2(节点信誉度). 节点信誉度主要表征资源节点的历史行为表现特征,定义为一个随时间变化的函数,除了与网格资源节点累计使用率有关以外,还与节点在累计执行任务获得的信任评价相关.资源节点r u 在网格系统中的信誉度评估策略为e s.t. 0,,1 1r u u u u TB r r r RL RS RU αβγαβγαβγ−⎫=×+×+×⎪⎪<<⎬⎪++=⎪⎭(3)在公式(3)中,α为时间衰减权重系数,β为网格资源节点r u 累计执行调度任务获得的信任评价权重系数,γ为资源累计使用率权重系数;u r TB 为网格节点r u 最近一次成功执行任务到目前为止的时间间隔,0;u u r r TB RU >为节点r u 累计使用率,可用节点r u 累计执行任务时间与累计活跃时间的比值来表示;u r RS 为节点累计执行任务获得的信任评价,包含3个因子,即时间、身份可靠性安全值和行为信誉度,其计算方法为 ()()()u io i i io io i i i i r io io ioi i ic c s s r r RS c s r χδη−−−=×+×+×∑∑∑∑∑∑ (4) 在公式(4)中,系数χ,δ和η分别为时间、身份可靠性性和信誉度对节点r u 信任评价值的贡献率,0<χ,δ,η<1且χ+δ+η=1;c io 为预估计完成时间,c i 为实际花费时间;s io 为资源节点r u 声明的安全值,s i 为实际获得的安全值;同样,r io 为资源节点r u 调度时声称的信誉度值,r i 为实际获得的信誉值.3.3 安全融合模型定义3(身份可靠性隶属度). 身份可靠性隶属度表征网格任务对资源节点的保密性、完整性及真实性等固有安全水平的满意程度.网格任务t i 对资源节点r u 的身份可靠性满意度可由下式定义的隶属度函数获得: 1, if (,)1, else max_i u i u u t r t r i u r TS SL TS SL SV t r level SL ⎧⎪−=⎨−⎪−⎩≤ (5) 在公式(5)中,i t TS 为网格任务t i 的可靠性安全需求,u r SL 为网格资源节点r u 的身份可靠性安全水平值.定义4(行为可信性隶属度). 行为可信性隶属度表征网格任务对资源节点的历史行为表现特征的满意程度.网格任务t i 对资源节点r u 的行为可信性满意度隶属度函数可参照文献[19]定义如下: 1, if exp((1))1(,)exp((1)), else exp(1)1exp((1))i u u i i i t r r t i u t t TR RS RS TR RV t r TR TR ⎧⎪−+−⎪−⎪=−−⎨⎪−⎪−−−⎪⎩≤ (6) 在公式(6)中,i t TR 为网格任务t i 的对资源节点行为可信性的安全需求,u r RS 为网格资源节点r u 的外部行为信誉度安全水平值.定义5(安全满意度). 网格任务调度安全满意度是指网格任务对向其提供服务资源节点的安全属性满意程度,其值由隶属度函数获得的综合安全效益值表征.网格任务t i 被分配到资源节点r u 上执行获得的综合安全朱海 等:融合安全的网格依赖任务调度双目标优化模型及算法2735效益值定义为121212(,)(,)(,)s.t. 0,1 1i u i u i u Sec t r SV t r RV t r ωωωωωω=+⎫⎪⎬⎪+=⎭≤≤ (7)在公式(7)中,ω1,ω2分别代表任务t i 在节点r u 上获得的身份可靠性和行为可信性满意度的权重,SV (t i ,r u )和RV (t i ,r u )的值可分别由公式(5)和公式(6)获得.定义6(安全融合模型). 安全融合模型定义为一个四元组(R ,T ,A ,S ),其中,R 代表网格资源节点集合即服务提供者,T 代表应用任务集合即服务需求者,A 代表安全属性集合即包括任务调度的身份可靠性和行为可信性,S代表安全效益函数集合(任务需求满意度)即包括身份可靠性隶属度函数和行为可信性隶属度函数.在网格安全融合模型中,综合考虑了网格资源节点的固有安全性和行为安全性,采用安全效益函数使任务安全需求和资源节点安全属性间关系得以确立,将调度机制和安全机制较好地融合起来.4 双目标优化的网格任务调度新模型网格任务分配调度策略可由任务-资源映射图表示,如图2所示.其中,图的顶点表示任务-资源的映射对,顶点的权值为任务的计算量、安全需求以及相应资源节点的计算能力和安全水平,边表示任务之间的约束及通信关系,边的权值为具有约束关系相邻任务间的通信量、通信安全需求及对应资源节点间的单位通信能力和链路安全性. t 0,r 1t 6,r 0t 5,r 3t 4,r 3t 3,r 2t 2,r 0t 1,r 1t 8,r 3t 7,r 2Fig.2 Model of grid task-resource distribution图2 网格任务-资源分配模型定义7(网格任务-资源分配图表示模型). 网格任务资源分配映射图可以用一个四元组T -RAG 表示:T -RAG =(V L ,E L ,W L ,U L ).其中,•V L 为任务-资源分配图的顶点集合V L ={l 0,l 1,…,l n −1},l x ={(t i ,r u )|0≤i <n ,0≤u <mr 0,r 1,…,r m −1},(t i ,r u )表示任务t i 映射到网格资源节点r u 上执行.• E L 为任务-资源分配图边的集合,{|(,),(,) and }x y L l l x i u y j v E e l t r l t r x y ===≠,表示资源之间具有通信关系的集合,,x y l l e 表示网格资源r u 上的任务t i 和资源r v 上的任务t j 之间的通信关系.• W L 为任务-资源分配图顶点权值集合,W L =(W T ,W R )为一个二元组,W T 和W R 分别为任务图和资源拓扑结构图中相应顶点权值.2736Journal of Software 软件学报 V ol.22, No.11, November 2011• U L 为任务-资源分配图边权值集合,U L =(U T ,U R )也是一个二元组,表示图中顶点l x =(t i ,r u )和顶点l y =(t j ,r v )连接边上的权值集合.定义8(任务调度系统安全效益值). 网格任务调度系统获得的安全效益值表征网格应用在资源节点上调度的安全满意程度,定义为任务资源分配图中每个任务获得安全效益值的平均值即系统安全效益值,可由下式获得: 1100(,)()n m iu i u i u K x Sec t r S G N−−===∑∑ (8) 其中,Sec (t i ,r u )可由公式(7)得到,为任务t i 在网格节点r u 上获得的安全效益值;x iu 为决策变量,其定义如下: 1, 0, i u iu t r x ⎧=⎨⎩任务分配到节点上执行否则(9) 定义9(任务调度长度). 网格任务调度长度为任务-资源分配图模型中从入口节点到出口节点最大路径的长度:()max{()}max ()()S L S L K S S S V V E E L G L P L V L E ∈∈⎧⎫⎪⎪==+⎨⎬⎪⎪⎩⎭∑∑ (10) 在公式(10)中: •L (P S )表示图T -RAG (简称图G )中任意某路径P S 从入口节点S e 到出口节点S o 的时间花费. •L (E S )为路径P S 中间的数据通信时间,若任务t i ,t j 分别分配到资源r u 和r v ,则有L (E S )=c (t i ,t j )/d (r u ,r v ), c (t i ,t j )为任务t i 和t j 之间数据传输量,d (r u ,r v )为资源r u 和r v 之间的通信能力. • L (V S )为路径P S 中某一节点的时间花费,若任务t i 分配网格资源节点r u 上,则有L (V S )=a (t i )/b (r u )+ST (t i ,r u ),ST (t i ,r u )为任务t i 在网格节点r u 上获得安全效益值的时间花费,其可由公式(11)得到:{,,}(,)((,))k i u i u k a e g ST t r ST SV t r ∈=∑ (11)其中,公式(11)的计算方法可查阅我们在文献[30]中所做的工作.定义10(双目标优化调度模型). 网格任务的双目标优化调度模型是由需求模型、网格资源拓扑结构模型、安全模型及分配调度方案组成,可表示为一个四元组(T ,R ,S ,MAP ),其中,MAP 为分配调度方案集合,即MAP ={map 1,map 2,…,map n }.分配调度方案为二元组map =(a ,ϕ),其中,a 表示将网格应用任务T 中n 个任务映射到资源节点R 上的分配方案(可由网格-任务资源分配图表示),ϕ表示单个网格节点r u 上的调度方案.那么,异构网格系统下任务调度的目标就是寻找任务需求模型与资源拓扑结构模型之间的映射调度方案,在满足任务间依赖关系的约束下,使网格任务的调度长度和获得的安全效益达到最优.其数学模型表示如下: 10min : {(),1()}s.t. 1,0,1,...,1(,)() (,)(,)(,)(,)()K K m iu u i j j j v i u j v u v v L G S G x i n c t t a t f t r f t r ST t r d r r b r −=−⎫⎪⎪==−⎪⎬⎪⎪−++⎪⎭∑≥ (12) 其中,L (G K )和S (G K )为网格任务的调度长度和安全满意度,可分别由公式(8)和公式(10)获得;第1个约束条件保证每个网格任务有且仅分配到1个资源节点上完成,第2个约束条件满足任务执行时的依赖关系.5 双目标离散粒子群算法5.1 PSO 的进化方程标准粒子群算法作为一种基于群智能的全局优化进化算法,已成功应用到不同领域,其进化方程为。

Priority Algorithms forGraph Optimization ProblemsAllan Borodin,Joan Boyar,and Kim rsenDepartment of Computer Science,University of Toronto.bor@,fax:+14169781931.Department of Mathematics and Computer Science,University of Southern Denmark,Odense.joan,kslarsen@imada.sdu.dk,fax:+4565502325.Abstract.We continue the study of priority or“greedy-like”algorithms as ini-tiated in[6]and as extended to graph theoretic problems in[8].Graph theoreticproblems pose some modelling problems that did not exist in the original applica-tions of[6]and[2].Following[8],we further clarify these concepts.In the graphtheoretic setting there are several natural input formulations for a given problemand we show that priority algorithm bounds in general depend on the input for-mulation.We study a variety of graph problems in the context of arbitrary andrestricted priority models corresponding to known”greedy algorithms”.1IntroductionThe concept of a greedy algorithm was explicitly articulated in a paper by Edmonds [10],following a symposium on mathematical programming in1967although one sus-pects that there are earlier references to this concept.Since that time,the greedy algo-rithm concept has taken on a broad intuitive meaning and a broader set of applications beyond combinatorial approximation.The importance of greedy algorithms is well mo-tivated by Davis and Impagliazzo[8]and constitutes an important part of many texts concerning algorithm design and analysis.New greedy algorithms keep emerging,as, for instance,in[17],which considers mechanisms for combinatorial auctions,requir-ing solutions to difficult optimization problems.Given the importance of greediness as an algorithm design“paradigm”,it is somewhat surprising that a rigorous framework, as general as priority algorithms,for studying greedy algorithms is just emerging.Of course,the very diversity of algorithms purported to be greedy makes it perhaps impos-sible tofind one definition that will satisfy everyone.The goal of the priority algorithm model is to provide a framework which is sufficiently general so as to capture“most”(or at least a large fraction)of the algorithms we consider to be greedy or greedy-like while still allowing good intuition and rigorous analysis,e.g.,being able to produce results on the limitations of the model and suggesting new algorithms.2Determine an allowable ordering of the set of possible input items(without knowing the actual input set of items)while not empty():=index of input item in that comesfirst in the orderingMake an irrevocable decision concerning and remove fromFig.1.The form of afixed priority algorithmThe priority model has two forms,fixed priority and the more general adaptive pri-ority model.The general form offixed and adaptive priority algorithms is presented in Figures1and2.To make this precise,for each specific problem we need to define the nature and representation(the type)of the input items and the nature of the allowable (irrevocable)decisions.Surprisingly,the issue as to what orderings are allowed has a rather simple and yet very inclusive ly,the algorithm can use any total ordering on some sufficiently large set of items from which the actual set of in-put items will come.(For adaptive algorithms,the ordering can depend on the items already considered.)The priority framework wasfirst formulated in Borodin,Nielsen and Rackoff[6]and applied to(worst case approximation algorithms for)some clas-sical scheduling problems such as Graham’s makespan problem and various interval scheduling problems.In a subsequent paper,Angelopoulos and Borodin[2]applied the framework to the set cover and uncapacitated facility location problems.These prob-lems were formulated so that the data items were“isolated”in the sense that one data item did not refer to another data item and hence any set of valid data items constituted a valid input instance.For example,in the makespan problem on identical machines with no precedence constraints,a data item is represented by a processing time and the items are unrelated.The version of facility location studied in[2]was for the“disjoint model”where the set of facilities and the set of clients/cities are disjoint sets and a fa-cility is represented by its opening cost and a vector of distances to each of the cities. In contrast,in the“complete model”for facility location,there is just a set of cities and every city can be a facility.Here a city is represented by its opening cost and a vector of distances to every other city.In the complete model for facility location,an input item (a city)directly refers to other input items.This is similar to the standard situation for graph theoretic problems when vertices are,say,represented by adjacency lists.The work of Davis and Impagliazzo[8]extends the priority formulation to graph theoretic problems.Davis and Impagliazzo consider a number of basic graph theory problems(single source shortest path,vertex cover,minimum spanning tree,Steiner trees,maximum independent set)with respect to one of two different input models depending on the problem and known“greedy algorithms”.For the shortest path,min-imum spanning tree and Steiner tree problems,the model used is the“edge model”, where input items are edges represented by their weights,the names of the endpoints, and in the case of the Steiner tree problem by the types(required or Steiner)of the edge endpoints.Note that in this edge representation,input items are isolated and all of3while input set not emptyDetermine a total ordering of all possible input items(without knowing the input items in not yet considered):=index of item in that comesfirst in the orderingMake an irrevocable decision concerning and remove fromFig.2.The form of an adaptive priority algorithmthe definitions in[6]can be applied.In particular,the definition of a greedy decision is well defined.In contrast,for the vertex cover and maximum independent set problems, Davis and Impagliazzo use a vertex adjacency list representation,where input items are vertices,represented by the names of the vertices to which they are adjacent,and in some problems also the weight of the vertex.This representation presents some chal-lenges for defining priority algorithms and greedy decisions.These definitional issues have helped to clarify the nature and usefulness of“memoryless priority algorithms”.Noting that lower bounds for graph theoretic priority algorithms appear to be hard to obtain in(say)the vertex adjacency model,Angelopoulos has recently[1]proposed a reasonable change to the model by restricting what priority algorithms can do,thus increasing the power of the adversary.The basic effect of his change is to force items which are indistinguishable(except for their different identification labels)to receive the same priority.Angelopoulos proves lower bounds for the complete facility location problem(for bothfixed and adaptive priority algorithms)and the dominating set prob-lem(for the more general adaptive priority algorithms).It is not clear if Angelopoulos’results can be obtained in the model which we use,but even if they can,this simple restriction on priority algorithms should make it easier to derive lower bound proofs.In this paper,we continue the study of priority algorithms for graph problems us-ing two models(again motivated by current algorithms),namely the vertex adjacency model as in Davis and Impagliazzo and an“edge adjacency model”,where input items are vertices now represented by a list of adjacent edge names(rather than a list of ad-jacent vertex names)and possible vertex weights where appropriate.It should be clear that the vertex adjacency model is more general in the sense that any priority algorithm in the edge adjacency model can be simulated in the vertex adjacency model(making exactly the same set of decisions).Most existing priority algorithms can function in the edge adjacency model;the authors were unable to recall one which does not.However, we show(using an example in Davis and Impagliazzo showing that memorylessness is restrictive)that the edge adjacency model can be restrictive.In the appendix,we pro-vide a definition for greedy decisions that can be applied even when input items are not isolated.We also introduce an“acceptances-first”model and clarify the relation of memoryless algorithms to this“acceptances-first”model rather than to greediness.We prove a number of new results within these models.Many proofs have been omitted,but they are all included in the appendix for the convenience of the program committee.42Priority Algorithms for Graph ProblemsAs mentioned in the introduction,we consider two input formulations.In the com-mon vertex adjacency formulation,an input item is a vertex,represented by the tuple ,where is the name of the vertex,is the weight(if any)of vertex and is a list of adjacent vertices.In the more restrictive edge ad-jacency formulation(but still a model sufficient to capture most known greedy graph algorithms),an input item is a vertex where again is the vertex name,is the weight(if any)of and is a list of adjacent edges.In either of the above models,we have the situation that not every set of valid input items constitutes a valid input instance.Clearly,a valid input instance cannot have the same vertex appear as two different items.And in the vertex adjacency model,if a vertex is an input item and is in its adjacency list then must also be an input item with in its adjacency list.Similarly,if an edge appears in some input item then must appear in exactly one other input item.Although the priority algorithm framework is designed to model greedy algorithms,it is possible to define priority algorithms where the irrevocable decisions do not seem greedy.As noted by Davis and Impagliazzo, the definition of“greedy decision”(as formulated in[6])is no longer well defined when the algorithm“knows”that the current item is not the last.More specifically, in[6],a greedy priority algorithm is one in which all of the irrevocable decisions are “greedy”in the sense that the algorithm acts as if the current item being considered is the last item in the input.In more colloquial terms,greediness is defined by the motto “live for today”.We would like to formulate a general concept of a greedy decision that also makes sense when the input items are not isolated.(We would like such a definition to also make sense for non-graph problems such as scheduling problems with precedence relations amongst the jobs where one can have non-isolated input items.) We offer one such definition in Appendix A.We note,however,that in the context of priority algorithms the greedy versus non greedy distinction is not that important and to the extent that it is important it is only because greedy is such a widely used (albeit mostly undefined)concept.We do argue that the priority algorithm formulation is important as it captures such a wide variety of existing algorithms which might be called“greedy-like”extending the concept of greedy and including(for example)all online algorithms.One can always make an ad hoc definition of a greedy decision in the context of any given problem.For example,for the vertex coloring problem one might define a greedy decision to be one that never assigns a new color to a vertex if an existing color could be used now.But for a given input and history of what has been seen,it may be known to the algorithm that any valid completion of the input sequence will force an additional color and it might be that in such a case one would also allow a new color to be used before it was needed.This can,of course,all be considered as a relatively minor definitional issue and one is free to choose whatever definition seems to be more natural and captures known“greedy algorithms”.Perhaps a more meaningful distinction is the concept of“memoryless”priority algo-rithms.Although motivated by the concept of memoryless online algorithms,especially in the context of the-server problem,the concept of memorylessness takes on a some-what different meaning as applied in[6]and[2].Namely these papers apply the concept5 to problems where the irrevocable decision is an accept/reject decision(or at least that acceptance/rejection is part of the irrevocable decision).In this context memoryless pri-ority algorithms are defined as priority algorithms in which the irrevocable decision for the current item(and the choice of next item in the case of adaptive algorithms)depends only on the set of previously accepted items.That is,in the words of[8],a rejected item is treated as a NO-OP.In the accept/reject context,memoryless algorithms are equiva-lent to acceptances-first algorithms which do not accept any items after thefirst rejected item.As observed1in[6]and[2],we have the following:Theorem1.Let be a memoryless priority algorithm for a problem with accept/reject decisions.Then there exists an“acceptances-first”adaptive priority algorithm that “simulates”in the sense that it accepts the same set of items and makes the same irrevocable decisions.We observe that many graph theoretic algorithms called greedy may or may not sat-isfy some generic general definition of greedy.But many of these algorithms are indeed memoryless(or equivalently,acceptances-first)according to the above definition.(By the definition of memoryless,the converse of the above theorem holds trivially.) To prove negative results,showing that no priority algorithm in some model can achieve an approximation ratio better than for a given problem,we use an adver-sary.The adversary initially chooses a set of valid input items.It interacts with an algorithms,maintaining the invariant that the items remaining in,together with the items already selected by,contain at least one valid input instance.At each step, the adversary removes the item remaining in,to which has given the highest pri-ority.It may also remove more items from at this point,as long as the invariant is maintained.In most cases the initial set contains multiple copies of each vertex in thefinal graph,and possibly even more different vertices than in thefinal graph.After the algo-rithm chooses a vertex,the adversary removes the other copies of that vertex from, since its adjacency list is now determined.An adaptive priority algorithm in the edge-adjacency model knows the names of the edges adjacent to the vertices already chosen, so it can give vertices with the same edges in their lists either high or low priority.The adversary may still have more than one copy of the neighbors at this time,though.In the vertex adjacency model,an adaptive priority algorithm has even more power;it can give the neighbors high or low priority and it can also give the neighbors of the neighbors high or low priority,since it knows the names of the neighbors.Although the adversary may still retain multiple copies of the neighbors,it cannot make arbitrary decisions as to whether or not a vertex chosen by the algorithm is or is not at distance at most two from any chosen vertices.For some scheduling results in[6],the adversaries assume that the algorithm does not know(or use information concerning)thefinal number of jobs to be processed.The same holds here for graph problems;in some cases the adversary createsfinal input6graphs that have different sizes for different algorithms.In practice,most priority algo-rithms do not seem to use the total number of vertices or edges in the graph in assigning priorities or in making the irrevocable decisions,so the results based on adversaries of this type are widely applicable.Unless otherwise stated,the results below assume the algorithm does not know the total number of vertices or edges in the graph.3Independent SetMaximum Independent Set is the problem offinding a largest subset,,of vertices in a graph such that no two vertices in are adjacent to each other.The independent set problem and the clique problem,whichfinds the same set in the complement of the graph,are well studied NP-hard problems,where approximation also appears to be hard.The bounded degree maximal independent set problem is one of the original MAX SNP-Complete problems[18].H˚a stad[12]has shown a general lower bound on the approximation ratio for the independent set problem of,for all ,provided that NP ZPP,where ZPP is the class of languages decidable by a random expected polynomial-time algorithm that makes no errors.A general upper bound of was presented by Boppana and Halld´o rsson[5],and an upper bound for graphs of degree3of was shown by Berman and Fujito[4].These algorithms are not priority algorithms.Davis and Impagliazzo[8]have shown that no adaptive priority algorithm(in the vertex adjacency model)can achieve an approximation ratio better than.Theorem2.No acceptances-first adaptive algorithm in the vertex adjacency model for independent set can achieve an approximation ratio better than2We have defined the approximation ratio so that all ratios are at least one.7 Theorem3.Nofixed priority algorithm in the edge adjacency model for independent set(or clique)can achieve an approximation ratio better than,where is the number of vertices.Proof.The adversary uses possibly several copies of the construction,.Since is a fixed priority algorithm and all vertices have the same degree,cannot distinguish the vertices when assigning priorities.The adversary arranges that the selected vertices are independent during thefirst phase.We let denote the number vertices processed so far.Thefirst phase continues until either has accepted at least.If thefirst phase stopped because,the adversary uses a single copy of the construction,.The vertices are in.Note that the number of accepted vertices is strictly smaller thanfor the approximation ratio for this same problem in the edge adjacency model, thus showing that the edge adjacency model can be restrictive when compared to the vertex adjacency model.Theorem4.For the WIS problem with,no adaptive priority algorithm in the edge adjacency model can obtain an approximation ratio better than8We use to denote a vertex accepted by the priority algorithm and to denote a vertex rejected by the priority algorithm.To demonstrate a best possible result which the priority algorithm can obtain given the accept/reject actions it has already made,weuse to mark vertices which could be included in addition to the already accepted vertices.Finally,we indicate an optimal vertex cover by marking vertices in one suchcover by can in general be chosen uniquely, but their total weight will be unique.The argument is structured according to the choices made by the priority algorithm,beginning with whether thefirst vertex has weight or and whether the priority algo-rithm accepts or rejects that vertex.In all but one case,the adversary can immediately guarantee a specific approximation ratio,but in one case,the next vertex chosen by the algorithm must also be used by the adversary:First accept weight vertex:givesgives.First reject weight vertex:We now ensure that no vertex of weight will appear as a neighbor of the rejected vertex.All the remaining cases are subcases of the current case.Next accept non-neighbor weight vertex:.Next accept non-neighbor weight vertex:gives.Next reject non-neighbor weight vertex:givesgives.Choosing ensures the stated approximation ratio lower bound ofapproximation ratio for WIS can be achieved in the edge adjacency model3.Theorem5.For the WIS problem,there is an adaptive priority algorithm in theedge adjacency model with approximation ratio3In contrast,for the WIS problem in the vertex adjacency model,Davis and Impagliazzo show a2-approximation lower bound for memoryless algorithms.9 IV.If there are any vertices remaining,there must be a vertex of weight adja-cent to only one already processed vertex.Reject this vertex of weight and accept its unprocessed neighbor.Follow this around the cycle,accepting every other vertex until reaching a vertex which has already been processed.Repeat this step until all processed chains have been joined.Note that this algorithm maintains the invariant that for any maximal chain of ver-tices already processed,the endpoints have been rejected.The remainder of the proof is a case analysis and is given in the appendix.4Vertex CoverMinimum Vertex Cover is the problem offinding a smallest subset,,of vertices in a graph such that all edges are incident to some vertex in.The unweighted vertex cover problem is one of the most celebrated open problems in the area of worst case approximation algorithms.The naive algorithm(taking both adjacent vertices in any maximal matching)provides a2-approximation.This is essen-tially the best known polynomial time approximation bound in the sense that there are no known polynomial time approximation algorithms(for afixed),although various algorithms are known that guarantee an approximation better than2but con-verging to2as some parameter grows.This maximal matching algorithm is easily seen to be an acceptances-first adaptive priority algorithm in the edge adjacency model.Sur-prisingly,Johnson[15]showed that the greedy algorithm which chooses the vertex with highest degree in the remaining graph is only a-approximation,and that this bound is tight in that there are arbitrarily large graphs on which the algorithm produces a ver-tex cover whose size is times the size of the optimal cover.Although the weighted vertex cover problem can be essentially reduced(in polynomial time)to the unweighted case(by making multiple copies of vertices),this reduction does not preserve the prop-erty of being a priority algorithm and hence the study of the unweighted and weighted vertex cover problems may be substantially different problems in the context of priority algorithms.It turns out that there are several priority algorithms for the weighted case that also achieve a2-approximation algorithm(or slightly better).One such algorithm is Johnson’s“greedy algorithm”(the layered algorithm as given in Vazirani’s excellent text on approximation algorithms[20]).Essentially for the vertex cover problem this algorithm chooses all maximum degree vertices and removes them simultaneously.An-other simple to state(and also called greedy)algorithm is given by Clarkson[7].This algorithm achieves the approximation bound where is the max-imum degree in the graph and is the number of vertices4.Both the layered algorithm and Clarksons’s algorithm can be expressed as acceptances-first adaptive algorithms in the edge adjacency model.In terms of complexity lower bounds,Dinur and Safra[9] provide a sophisticated proof that it is NP-hard to have a c-approximation algorithm for the(unweighted)vertex cover problem for..10Davis and Impagliazzo show that for the weighted case,priority algorithms(in the vertex adjacency model)cannot essentially do better than a-approximation.Priority lower bounds for the unweighted case seem more difficult.The following5If the number of edges should also be the same,we can add a cycle of4vertices to graph2 and a cycle of4vertices with one diagonal to graph1and obtain a bound of.11 5Vertex ColoringMinimum Vertex Coloring is the problem of coloring the vertices in a graph using the minimum number of different colors in such a way that no two adjacent vertices havethe same color.The problem is also known as Graph-Colorability and as Chromatic Number.Hardness results are known for minimum vertex coloring under various complexitytheoretical assumptions:minimum vertex coloring is NP-hard to approximate within ),for all,provided that NP ZPP[11].It is NP-hard to approximate withinprovided that P NP[3].From[16],it is known that it is NP-hard to-color a-chromatic graph,NP-hard to color a-chromatic graph with at most colors,and NP-hard to approximate within for somefixed as the chromatic number of graphs tend towards infinity.On the positive side,a general upper bound of is shown by Halld´o rsson[13].In[19],an upper bound of is established,where is any function of graphs such thatdegLet be the maximum over all vertex-induced subgraphs of the minimum de-gree in that subgraph.The result in[19]constructively establishes that any graph is colorable,so a corollary of the theorem below is that the algorithm from[19] is not a priority algorithm.Theorem9.No priority algorithm in the edge adjacency model can3-color all graphs with.In more restrictive models,we obtain stronger lower bounds.The following two results apply to models which include the simplest and most natural greedy algorithm; namely,order the vertices in any way and then color vertices using the lowest possible numbered color.Theorem10.Anyfixed priority algorithm in the edge adjacency model must use atleast colors on a bipartite graph of maximum degree.In the next result,we consider adaptive priority algorithms which use different in-formation in its two main phases.When assigning priorities to vertices,it only considers the number of uncolored neighbors a vertex has and the vector of the colors used so far where is the number of nodes that have already been colored with color.In this phase,the algorithm may not use information about how many of a ver-tex’s neighbors have already been colored or what colors these neighbors have been given.For the irrevocable decision of coloring a vertex,the color given will simply be a function of the set of colors already given to the neighbors.This could,for example, be the lowest possible numbered color.Theorem11.Any adaptive priority algorithm in the edge adjacency model,whichgives priorities based only on the current degree of the vertex and the already processedsubgraph,must use colors on a-colorable graph of maximum degree,when the color given is a function of the set of currently adjacent colors(no state information).12References1.S.Angelopoulos.Ordering-preserving transformations and greedy-like algorithms.Manuscript,2004.2.S.Angelopoulos and A.Borodin.On the power of priority algorithms for facility location andset cover.In Proceedings of the5th International Workshop on Approximation Algorithms for Combinatorial Optimization,volume2462of Lecture Notes in Computer Science,pages 26–39.Springer-Verlag,2002.3.Mihir Bellare,Oded Goldreich,and Madhu Sudan.Free bits,PCPs and non-approximability—towards tight results.SIAM Journal on Computing,27:804–915,1998. 4.Piotr Berman and Toshihiro Fujito.On approximation properties of the independent setproblem for degree3graphs.In Fourth International Workshop on Algorithms and Data Structures,volume955of Lecture Notes in Computer Science,pages449–460.Springer-Verlag,1995.5.Ravi Boppana and Magn´u s M.Halld´o rsson.Approximating maximum independent sets byexcluding subgraphs.Bit,32:180–196,1992.6. A.Borodin,M.Nielsen,and C.Rackoff.(Incremental)priority algorithms.Algorithmica,37:295–326,2003.7.Kenneth L.Clarkson.A modification of the greedy algorithm for vertex rmationProcessing Letters,16:23–25,1983.8.S.Davis and R.Impagliazzo.Models of greedy algorithms for graph problems.In Proceed-ings of the15th Annual ACM-SIAM Symposium on Discrete Algorithms,2004.9.Irit Dinur and Shmuel Safra.The importance of being biased.In Proceedings of the34thSymposium on Theory of Computing,pages33–42.ACM Press,2002.10.Jack Edmonds.Matroids and the greedy algorithm.Mathematical Programming,1:127–136,1971.11.Urid Feige and Joe Kilian.Zero knowledge and the chromatic number.Journal of Computerand System Sciences,57:187–199,1998.12.Johan H˚a stad.Clique is hard to approximate within.Acta Mathematica,182:105–142,1999.13.Magn´u s M.Halld´o rsson.A still better performance guarantee for approximate graph color-rmation Processing Letters,45:19–23,1993.14. D.Hochbaum.Efficient bounds for the stable set,vertex cover and set packing problems.Discrete Applied Mathematics,6:243–254,1983.15.David S.Johnson.Approximation algorithms for combinatorial problems.Journal of Com-puter and System Sciences,9(3):256–278,1974.16.Sanjeev Khanna,Nathan Linial,and Shmuel Safra.On the hardness of approximating thechromatic binatorica,20(3):393–415,2000.17. D.Lehmann,L.O’Callaghan,and Y.Shoham.Truth revelation in approximately efficientcombinatorial auctions.Journal of the ACM,49(5):1–26,2002.18. C.Papadimitriou and M.Yannakakis.Optimization,approximation and complexity classes.Journal of Computer and System Sciences,43:425–440,1991.19.G.Szekeres and Herbert S.Wilf.An inequality for the chromatic number of graphs.Journalof Combinatorial Theory,4:1–3,1968.20.Vijay V.Vazirani.Approximation Algorithms.Springer-Verlag,2001.。

Chapter21Michelle Bodnar,Andrew LohrApril12,2016Exercise21.1-1EdgeP rocessedinitial{a}{b}{c}{d}{e}{f}{g}{h}{i}{j}{k} (d,i){a}{b}{c}{d,i}{e}{f}{g}{h}{j}{k} (f,k){a}{b}{c}{d,i}{e}{f,k}{g}{h}{j}(g,i){a}{b}{c}{d,i,g}{e}{f,k}{h}{j}(b,g){a}{b,d,i,g}{c}{e}{f,k}{h}{j}(a,h){a,h}{b,d,i,g}{c}{e}{f,k}{j}(i,j){a,h}{b,d,i,g,j}{c}{e}{f,k}(d,k){a,h}{b,d,i,g,j,f,k}{c}{e}(b,j){a,h}{b,d,i,g,j,f,k}{c}{e}(d,f){a,h}{b,d,i,g,j,f,k}{c}{e}(g,j){a,h}{b,d,i,g,j,f,k}{c}{e}(a,e){a,h,e}{b,d,i,g,j,f,k}{c}So,the connected components that we are left with are{a,h,e},{b,d,i,g,j,f,k},and{c}.Exercise21.1-2First suppose that two vertices are in the same connected component.Thenthere exists a path of edges connecting them.If two vertices are connected bya single edge,then they are put into the same set when that edge is processed.At some point during the algorithm every edge of the path will be processed,soall vertices on the path will be in the same set,including the endpoints.Nowsuppose two vertices u and v wind up in the same set.Since every vertex startsoffin its own set,some sequence of edges in G must have resulted in eventuallycombining the sets containing u and v.From among these,there must be apath of edges from u to v,implying that u and v are in the same connectedcomponent.Exercise21.1-3Find set is called twice on line4,this is run once per edge in the graph,so,we have thatfind set is run2|E|times.Since we start with|V|sets,at the end1only have k,and each call to UNION reduces the number of sets by one,we have that we have to of made|V|−k calls to UNION.Exercise21.2-1The three algorithms follow the english description and are provided here. There are alternate versions using the weighted union heuristic,suffixed with WU.Algorithm1MAKE-SET(x)Let o be an object with threefields,next,value,and setLet L be a linked list object with head=tail=oo.next=NILo.set=Lo.value=xreturn LAlgorithm2FIND-SET(x)return o.set.head.valueAlgorithm3UNION(x,y)L1=x.setL2=y.setL1.tail.next=L2.headz=L2.headwhile z.next=NIL doz.set=L1end whileL1.tail=L2.tailreturn L1Exercise21.2-2Originally we have16sets,each containing x i.In the following,we’ll replace x i by i.After the for loop in line3we have:{1,2},{3,4},{5,6},{7,8},{9,10},{11,12},{13,14},{15,16}.After the for loop on line5we have{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16}.Line7results in:2Algorithm4MAKE-SET-WU(x)L=MAKE-SET(x)L.size=1return LAlgorithm5UNION-WU(x,y)L1=x.setL2=y.setif L1.size≥L2.size thenL=UNION(x,y)elseL=UNION(y,x)end ifL.size=L1.size+L2.sizereturn L{1,2,3,4,5,6,7,8},{9,10,11,12},{13,14,15,16}.Line8results in:{1,2,3,4,5,6,7,8},{9,10,11,12,13,14,15,16}.Line9results in:{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}.FIND-SET(x2)and FIND-SET(x9)each return pointers to x1.Exercise21.2-3During the proof of theorem21.1,we concluded that the time for the n UNION operations to run was at most O(n lg(n)).This means that each of them took an amortized time of at most O(lg(n)).Also,since there is only a constant actual amount of work in performing MAKE-SET and FIND-SET operations,and none of that ease is used to offset costs of UNION operations, they both have O(1)runtime.Exercise21.2-4We call MAKE-SET n times,which contributesΘ(n).In each union,the smaller set is of size1,so each of these takesΘ(1)time.Since we union n−1 times,the runtime isΘ(n).Exercise21.2-53For each member of the set,we will make itsfirstfield which used to point back to the set object point instead to the last element of the linked list.Then, given any set,we canfind its last element by going ot the head and following the pointer that that object maintains to the last element of the linked list.This only requires following exactly two pointers,so it takes a constant amount of time.Some care must be taken when unioning these modified sets.Since the set representative is the last element in the set,when we combine two linked lists,we place the smaller of the two sets before the larger,since we need to update their set representative pointers,unlike the original situation,where we update the representative of the objects that are placed on to the end of the linked list.Exercise21.2-6Instead of appending the second list to the end of thefirst,we can imag-ine splicing it into thefirst list,in between the head and the elements.Store a pointer to thefirst element in S1.Then for each element x in S2,set x.head=S1.head.When the last element of S2is reached,set its next pointer to thefirst element of S1.If we always let S2play the role of the smaller set, this works well with the weighted-union heuristic and don’t affect the asymp-totic running time of UNION.Exercise21.3-1182426 3546215239Exercise21.3-2To implement FIND-SET nonrecursively,let x be the element we call the function on.Create a linked list A which contains a pointer to x.Each time we most one element up the tree,insert a pointer to that element into A.Once the root r has been found,use the linked list tofind each node on the path from the root to x and update its parent to r.Exercise21.3-34Suppose that n =2k is the smallest power of two less than n.To see that this sequences of operations does take the required amount of time,we’llfirst note that after each iteration of the for loop indexed by j,we have that the elements x1,...,x n are in trees of depth i.So,after wefinish the outer for loop,we have that x1...x n all lie in the same set,but are represented by a tree of depth k∈Ω(lg(n)).Then,since we repeatedly call FIND-SET on an item that is lg(n)away from its set representative,we have that each one takes time lg(n).So,the last for loop alltogther takes time m lg(n).Algorithm6Sequence of operations for Exercise21.3-3for i=1..n doMAKE-SET x iend forfor i=1..k dofor j=1..n −2i=1by2i doUNION(x i,x i+2j−1)end forend forfor i=1..m doFIND-SET(x1)end forExercise21.3-4In addition to each tree,we’ll store a linked list(whose set object contains a single tail pointer)with which keeps track of all the names of elements in the tree.The only additional information we’ll store in each node is a pointer x.l to that element’s position in the list.When we call MAKE-SET(x),we’ll also cre-ate a new linked list,insert the label of x into the list,and set x.l to a pointer to that label.This is all done in O(1).FIND-SET will remain unchanged. UNION(x,y)will work as usual,with the additional requirement that we union the linked lists of x and y.Since we don’t need to update pointers to the head, we can link up the lists in constant time,thus preserving the runtime of UNION. Finally,PRINT-SET(x)works as follows:first,set s=FIND-SET(x).Then print the elements in the linked list,starting with the element pointed to by x.(This will be thefirst element in the list).Since the list contains the same number of elements as the set and printing takes O(1),this operation takes linear time in the number of set members.Exercise21.3-5Clearly each MAKE-SET and LINK operation only takes time O(1),so, supposing that n is the number of FIND-SET operations occuring after the making and linking,we need to show that all the FIND-SET operations only5take time O(n).To do this,we will ammortize some of the cost of the FIND-SET operations into the cost of the MAKE-SET operations.Imagine paying some constant amount extra for each MAKE-SET operation.Then,when do-ing a FIND-SET(x)operation,we have three possibilities.First,we could have that x is the representative of its own set.In this case,it clearly only takes constant time to run.Second,we could have that the path from x to its set’s representative is already compressed,so it only takes a single step tofind the set representative.In this case also,the time required is stly,we could have that x is not the representative and it’s path has not been compressed. Then,suppose that there are k nodes between x and its representative.The time of thisfind-set operation is O(k),but it also ends up compressing the paths of k nodes,so we use that extra amount that we paid during the MAKE-SET operations for these k nodes whose paths were compressed.Any subsequent call tofind set for these nodes will take only a constant amount of time,so we would never try to use the work that amortization amount twice for a given node. Exercise21.4-1The initial value of x.rank is0,as it is initialized in line2of the MAKE-SET(x)procedure.When we run LINK(x,y),whichever one has the larger rank is placed as the parent of the other,and if there is a tie,the parent’s rank is incremented.This means that after any LINK(y,x),the two nodes being linked satisfy this strict inequality of ranks.Also,if we have that x=x.p,then,we have that x is not its own set representative,so,any linking together of sets that would occur would not involve x,but that’s the only way for ranks to increase, so,we have that x.rank must remain constant after that point.Exercise21.4-2We’ll prove the claim by strong induction on the number of nodes.If n=1,then that node has rank equal to0= lg1 .Now suppose that the claim holds for1,2,...,n nodes.Given n+1nodes,suppose we perform a UNION operation on two disjoint sets with a and b nodes respectively,where a,b≤n.Then the root of thefirst set has rank at most lg a and the root of the second set has rank at most lg b .If the ranks are unequal,then the UNION operation preserves rank and we are done,so suppose the ranks are equal.Then the rank of the union increases by1,and the resulting set has rank lg a +1≤ lg(n+1)/2 +1= lg(n+1) .Exercise21.4-3Since their value is at most lg(n) ,we can represent them usingΘ(lg(lg(n))) bits,and may need to use that many bits to represent a number that can take that many values.Exercise21.4-46MAKE-SET takes constant time and both FIND-SET and UNION are bounded by the largest rank among all the sets.Exercise21.4-2bounds this from about by lg n ,so the actual cost of each operation is O(lg n).Therefore the actual cost of m operations is O(m lg n).Exercise21.4-5He isn’t correct,suppose that we had that rank(x.p)>A2(rank(x))but that rank(x.p.p)=1+rank(x.p),then we would have that level(x.p)=0,but level(x)≥2.So,we don’t have that level(x)≤level(x.p)even though we have that the ranks are monotonically increasing as we go up in the tree.Put another way,even though the ranks are monotonically increasing,the rate at which they are increasing(roughly captured by the level vales)doesn’t have to,itself be increasing.Exercise21.4-6First observe that by a change of variables,α (2n−1)=α(n).Earlier in the section we saw thatα(n)≤3for0≤n≤2047.This means thatα (n)≤2for0≤n≤22046,which is larger than the estimated number of atoms in the observ-able universe.To prove the improved bound of O(mα (n))on the operations,the general structure will be essentially the same as that given in the section.First, modify bound21.2by observing that Aα (n)(x.rank)≥Aα (n)(1)≥lg(n+1)> x.p.rank which implies level(x)≤α (n).Next,redefine the potential replacing α(n)byα (n).Lemma21.8now goes through just as before.All subsequent lemmas rely on these previous observations,and their proofs go through exactly as in the section,yielding the bound.Problem21-1a.index value 14 23 32 46 58 61b.As we run the for loop,we are picking offthe smallest of the possible elementsto be removed,knowing for sure that it will be removed by the next unused EXTRACT-MIN operation.Then,since that EXTRACT-MIN operation is used up,we can pretend that it no longer exists,and combine the set of things that were inserted by that segment with those inserted by the next, since we know that the EXTRACT-MIN operation that had separated the7two is now used up.Since we proceed tofigure out what the various extract operations do one at a time,by the time we are done,we havefigured them all out.c.We let each of the sets be represented by a disjoint set structure.To unionthem(as on line6)just call UNION.Checking that they exist is just a matter of keeping track of a linked list of which ones exist(needed for line5),initially containing all of them,but then,when deleting the set on line6,we delete it from the linked list that we were maintaining.The only other interaction with the sets that we have to worry about is on line2,which just amounts toa call of FIND-SET(j).Since line2takes amortized timeα(n)and we call itexactly n times,then,since the rest of the for loop only takes constant time, the total runtime is O(nα(n)).Problem21-2a.MAKE-TREE and GRAFT are both constant time operations.FIND-DEPTH is linear in the depth of the node.In a sequence of m operations the maximal depth which can be achieved is m/2,so FIND-DEPTH takes at most O(m).Thus,m operations take at most O(m2).This is achieved as follows: Create m/3new trees.Graft them together into a chain using m/3calls to GRAFT.Now call FIND-DEPTH on the deepest node m/3times.Each call takes time at least m/3,so the total runtime isΩ((m/3)2)=Ω(m2).Thus the worst-case runtime of the m operations isΘ(m2).b.Since the new set will contain only a single node,its depth must be zero and its parent is itself.In this case,the set and its corresponding tree are in-distinguishable.Algorithm7MAKE-TREE(v)v=Allocate-Node()v.d=0v.p=vReturn vc.In addition to returning the set object,modify FIND-SET to also return the depth of the parent node.Update the pseudodistance of the current node v to be v.d plus the returned pseudodistance.Since this is done recursively,the running time is unchanged.It is still linear in the length of thefind path.To implement FIND-DEPTH,simply recurse up the tree containing v,keeping a running total of pseudodistances.d.To implement GRAFT we need tofind v’s actual depth and add it to the pseudodistance of the root of the tree S i which contains r.8Algorithm8FIND-SET(v)if v=v.p then(v.p,d)=F IND−SET(v.p)v.d=v.d+dReturn(v.p,v.d)elseReturn(v,0)end ifAlgorithm9GRAFT(r,v)(x,d1)=FIND-SET(r)(y,d2)=FIND-SET(v)if x.rank>y.rank theny.p=xx.d=x.d+d2+y.delsex.p=yx.d=x.d+d2if x.rank==y.rank theny.rank=y.rank+1end ifend ife.The three implemented operations have the same asymptotic running time as MAKE,FIND,and UNION for disjoint sets,so the worst-case runtime of m such operations,n of which are MAKE-TREE operations,is O(mα(n)). Problem21-3a.Suppose that we let≤LCA to be an ordering on the vertices so that u≤LCA vif we run line7of LCA(u)before line7of LCA(v).Then,when we are running line7of LCA(u),we immediately go on to the for loop on line8.So,while we are doing this for loop,we still haven’t called line7of LCA(v).This means that v.color is white,and so,the pair{u,v}is not considered during the run of LCA(u).However,during the for loop of LCA(v),since line7of LCA(u)has already run,u.color=black.This means that we will consider the pair{u,v}during the running of LCA(v).It is not obvious what the ordering≤LCA is,as it will be implementation dependent.It depends on the order in which child vertices are iterated in the for loop on line3.That is,it doesn’t just depend on the graph structure.b.We suppose that it is true prior to a given call of LCA,and show thatthis property is preserved throughout a run of the procedure,increasing the number of disjoint sets by one by the end of the procedure.So,supposing9that u has depth d and there are d items in the disjoint set data structure before it runs,it increases to d+1disjoint sets on line1.So,by the time we get to line4,and call LCA of a child of u,there are d+1disjoint sets,this is exactly the depth of the child.After line4,there are now d+2disjoint sets,so,line5brings it back down to d+1disjoint sets for the subsequent times through the loop.After the loop,there are no more changes to the number of disjoint sets,so,the algorithm terminates with d+1disjoint sets, as desired.Since this holds for any arbitrary run of LCA,it holds for all runs of LCA.c.Suppose that the pair u and v have the least common ancestor w.Then,whenrunning LCA(w),u will be in the subtree rooted at one of w’s children,and v will be in another.WLOG,suppose that the subtree containing u runsfirst.So,when we are done with running that subtree,all of their ancestor values will point to w and their colors will be black,and their ancestor values will not change until LCA(w)returns.However,we run LCA(v)before LCA(w) returns,so in the for loop on line8of LCA(v),we will be considering the pair{u,v},since u.color==BLACK.Since u.ancestor is still w,that is what will be output,which is the correct answer for their LCA.d.The time complexity of lines1and2are just constant.Then,for each child,we have a call to the same procedure,a UNION operation which only takes constant time,and a FIND-SET operation which can take at most amortized inverse Ackerman’s time.Since we check each and every thing that is adjacent to u for being black,we are only checking each pair in P at most twice in lines8-10,among all the runs of LCA.This means that the total runtime is O(|T|α(|T|)+|P|).10。