The complexity theory distinguishes between problems that are known to be solved in polynomial time in the size of the data ( which can be described as reasonable ) , the NP- complete problems , which require ( in the present state of knowledge) resolution time exponential in the size of data ( which may be unreasonable ) . It is for this reason that the scientific community has turned to algorithms ( polynomial ) approximation which measure quality is most often due to report worse approximation case (for a minimization problem size , an algorithm has a approximation ratio k if the size of any solution can be returned by the algorithm is less than or equal to k times the size of the optimal solution). In the literature, we come to consider an algorithm is perform better than another when it has a smaller ratio approximation in the worst case . However, be aware that this measure now "classic" does not take into account the reality of all possible executions of an algorithm ( it only considers executions leading to the worst solution). My thesis aim to better " capture " behavior approximation algorithms going further than simply Report approximation in worst case , and on two separate problems : I. The problem of Vertex Cover Showing that the average performance of an algorithm can be décorélées performance in worst case . For example , we have shown in the class of graphs specially designed to trap in worst case , the greedy algorithm "Maximum Degree Greedy " returns in average solutions whose size tends to optimum when n tends to infinity. In evaluating the average performance of an algorithm . We proved the online algorithm proposed by Demange and Paschos in 2005 (including worst-case approximation ratio is equal to the maximum degree of the graph ) is 2 - to- average approached in any graph . this result , combined with other , shows that this algorithm is " practice " better than most 2- approximate algorithms known despite a bad worst case approximation ratio . In comparing the performance of different algorithms ( analytically and experimentally ) . We have proposed an algorithm list, and we have shown analytically that always returns better solution that was built by another algorithm recent list [ 2006 ENT ] when they treat the same list of vertices (in some particular graphs , the size difference can be arbitrarily large) . We also compared analytically ( using tools as the generating series ) the average performance of six algorithms on the roads. We then tested on a Many graphs of various well- selected families. It is observed in these studies that the 2 - approximate algorithms are studied those with the worst average performance and those who have the best average behavior have bad reports approximation ( depending on the degree max. graph ) . All these results show that the worst case approximation ratio is not always sufficient to characterize the entire quality of an algorithm and other analyzes ( such as average ) must be made to do the trick. II . The problem of the dynamic connection of the networks in groups We analyzed a tree connecting a process of up-to- date in a network group members can join or leave at any time. Our process has good properties: it is easy to implement and guarantees after each add operation or withdrawal , the shaft diameter is not more than 2 times the optimum . However, to obtain this guarantee , we must authorize the Total reconstruction of the tree when the member identified as its root leaves the group . These steps are very reconstruction expensive and therefore we seek to assess the number . Previous studies showed that in the worst case , it is necessary rebuild (almost) every step to maintain the warranty on diameter . We show in this thesis (using the steps random , etc. . ) that , depending on certain parameters of the problem ( as the probabilities associated with operations addition and removal ) , the expected number of reconstructions is either logarithmic in the number of events ( adding or removing ) is constant. this result shows that the average behavior is very good ( despite the very worst case unfavorable) and our process up-to- date can be a viable solution in practice.
