@prefix dcat: . @prefix dct: . @prefix foaf: . @prefix vcard: . @prefix xsd: . a dcat:Dataset ; dct:description """ 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. """ ; dct:identifier "tel-00927315" ; dct:issued "2026-05-07T13:11:05.986342"^^xsd:dateTime ; dct:language "fr" ; dct:modified "2026-05-07T13:11:05.986347"^^xsd:dateTime ; dct:publisher ; dct:title "Beyond the worst case evaluation: Comparison and average evaluation of optimization processes in the case of the vertex cover problem and trees connecting groups." ; dcat:contactPoint [ a vcard:Organization ; vcard:fn "CCSD" ] ; dcat:distribution ; dcat:keyword "algorithm", "algorithme", "analyse-en-moyenne", "approximation", "average-analysis", "connecting-structure", "dynamic-groups", "generating-functions", "graph", "graphe", "groupes-dynamiques", "independent-set", "infoeu-reposemanticsdoctoralthesis", "infoinfo-rocomputer-science-csoperations-research-mathoc", "marches-aleatoires", "online", "optimisation", "optimization", "random-walks", "series-generatrices", "structure-de-connexion", "theses", "vertex-cover" ; dcat:landingPage . a dcat:Distribution ; dct:format "HTML" ; dct:issued "2026-05-07T13:11:05.993857"^^xsd:dateTime ; dct:modified "2026-05-07T13:11:05.965229"^^xsd:dateTime ; dct:title "Beyond the worst case evaluation: Comparison and average evaluation of optimization processes in the case of the vertex cover problem and trees connecting groups." ; dcat:accessURL . a foaf:Agent ; foaf:name "test_moissonnage_selune" . a foaf:Document .