In this thesis we introduce and evaluate several new models for the analysis of online algorithms. In an online problem, the algorithm does not know the entire input from the beginning; the input is revealed in a sequence of steps. At each step the algorithm should make its decisions based on the past and without any knowledge about the future. Many important real-life problems such as paging and routing are intrinsically online and thus the design and analysis of online algorithms is one of the main research areas in theoretical computer science. Competitive analysis is the standard measure for analysis of online algorithms. It has been applied to many online problems in diverse areas ranging from robot navigation, to network routing, to scheduling, to online graph coloring. While in several instances competitive analysis gives satisfactory results, for certain problems it results in unrealistically pessimistic ratios and/or fails to distinguish between algorithms that have vastly differing performance under any practical characterization. Addressing these shortcomings has been the subject of intense research by many of the best minds in the field. In this thesis, building upon recent advances of others we introduce some new models for analysis of online algorithms, namely Bijective Analysis, Average Analysis, Parameterized Analysis, and Relative Interval Analysis. We show that they lead to good results when applied to paging and list update algorithms. Paging and list update are two well known online problems. Paging is one of the main examples of poor behavior of competitive analysis. We show that LRU is the unique optimal online paging algorithm according to Average Analysis on sequences with locality of reference. Recall that in practice input sequences for paging have high locality of reference. It has been empirically long established that LRU is the best paging algorithm. Yet, Average Analysis is the first model that gives strict separation of LRU from all other online paging algorithms, thus solving a long standing open problem. We prove a similar result for the optimality of MTF for list update on sequences with locality of reference. A technique for the analysis of online algorithms has to be effective to be useful in day-to-day analysis of algorithms. While Bijective and Average Analysis succeed at providing fine separation, their application can be, at times, cumbersome. Thus we apply a parameterized or adaptive analysis framework to online algorithms. We show that this framework is effective, can be applied more easily to a larger family of problems and leads to finer analysis than the competitive ratio. The conceptual innovation of parameterizing the performance of an algorithm by something other than the input size was first introduced over three decades ago [124, 125]. By now it has been extensively studied and understood in the context of adaptive analysis (for problems in P) and parameterized algorithms (for NP-hard problems), yet to our knowledge this thesis is the first systematic application of this technique to the study of online algorithms. Interestingly, competitive analysis can be recast as a particular form of parameterized analysis in which the performance of opt is the parameter. In general, for each problem we can choose the parameter/measure that best reflects the difficulty of the input. We show that in many instances the performance of opt on a sequence is a coarse approximation of the difficulty or complexity of a given input sequence. Using a finer, more natural measure we can separate paging and list update algorithms which were otherwise indistinguishable under the classical model. This creates a performance hierarchy of algorithms which better reflects the intuitive relative strengths between them. Lastly, we show that, surprisingly, certain randomized algorithms which are superior to MTF in the classical model are not so in the parameterized case, which matches experimental results. We test list update algorithms in the context of a data compression problem known to have locality of reference. Our experiments show MTF outperforms other list update algorithms in practice after BWT. This is consistent with the intuition that BWT increases locality of reference.

In this thesis we introduce and evaluate several new models for the analysis of online algorithms. In an online problem, the algorithm does not know the entire input from the beginning; the input is revealed in a sequence of steps. At each step the algorithm should make its decisions based on the past and without any knowledge about the future. Many important real-life problems such as paging and routing are intrinsically online and thus the design and analysis of online algorithms is one of the main research areas in theoretical computer science. Competitive analysis is the standard measure for analysis of online algorithms. It has been applied to many online problems in diverse areas ranging from robot navigation, to network routing, to scheduling, to online graph coloring. While in several instances competitive analysis gives satisfactory results, for certain problems it results in unrealistically pessimistic ratios and/or fails to distinguish between algorithms that have vastly differing performance under any practical characterization. Addressing these shortcomings has been the subject of intense research by many of the best minds in the field. In this thesis, building upon recent advances of others we introduce some new models for analysis of online algorithms, namely Bijective Analysis, Average Analysis, Parameterized Analysis, and Relative Interval Analysis. We show that they lead to good results when applied to paging and list update algorithms. Paging and list update are two well known online problems. Paging is one of the main examples of poor behavior of competitive analysis. We show that LRU is the unique optimal online paging algorithm according to Average Analysis on sequences with locality of reference. Recall that in practice input sequences for paging have high locality of reference. It has been empirically long established that LRU is the best paging algorithm. Yet, Average Analysis is the first model that gives strict separation of LRU from all other online paging algorithms, thus solving a long standing open problem. We prove a similar result for the optimality of MTF for list update on sequences with locality of reference. A technique for the analysis of online algorithms has to be effective to be useful in day-to-day analysis of algorithms. While Bijective and Average Analysis succeed at providing fine separation, their application can be, at times, cumbersome. Thus we apply a parameterized or adaptive analysis framework to online algorithms. We show that this framework is effective, can be applied more easily to a larger family of problems and leads to finer analysis than the competitive ratio. The conceptual innovation of parameterizing the performance of an algorithm by something other than the input size was first introduced over three decades ago [124, 125]. By now it has been extensively studied and understood in the context of adaptive analysis (for problems in P) and parameterized algorithms (for NP-hard problems), yet to our knowledge this thesis is the first systematic application of this technique to the study of online algorithms. Interestingly, competitive analysis can be recast as a particular form of parameterized analysis in which the performance of opt is the parameter. In general, for each problem we can choose the parameter/measure that best reflects the difficulty of the input. We show that in many instances the performance of opt on a sequence is a coarse approximation of the difficulty or complexity of a given input sequence. Using a finer, more natural measure we can separate paging and list update algorithms which were otherwise indistinguishable under the classical model. This creates a performance hierarchy of algorithms which better reflects the intuitive relative strengths between them. Lastly, we show that, surprisingly, certain randomized algorithms which are superior to MTF in the classical model are not so in the parameterized case, which matches experimental results. We test list update algorithms in the context of a data compression problem known to have locality of reference. Our experiments show MTF outperforms other list update algorithms in practice after BWT. This is consistent with the intuition that BWT increases locality of reference.

Le projet FUI12 RLDO – dans le cadre duquel s’inscrit cette thèse – préconise une solution de réseau de topologie en étoile passive pour la montée en débit des réseaux domestiques. Cette solution de réseau rencontre des difficultés dans son implémentation avec la non-uniformité des puissances des ports de sortie des coupleurs multimodes. L’analyse de ce point nous a permis de comprendre que les propriétés des modes de propagation dans les éléments du réseau jouent un rôle clé dans les problèmes rencontrés. Pour caractériser la propagation dans le réseau, nous avons développé un banc de réflectométrie optique complexe dans le domaine fréquentiel. Les phénomènes limitant la sensibilité à la phase – liés en particulier à la non-linéarité du balayage en fréquence de la source laser – sont étudiés pour contribuer à une meilleure compréhension des mécanismes. Puis les performances de la mesure en intensité et en phase de l’instrument que nous avons mis en place sont testées. Nous avons aussi étudié les conditions de résolution optimales pour caractériser les modes d’un guide multimode et analysé l’incertitude sur la dispersion chromatique dans le cas où il est impossible de déterminer si on a accès à un mode ou plusieurs modes dans un diagramme de dispersion donné. Nous introduisons par la suite une méthode d’analyse temps-fréquence adaptative, permettant d’obtenir les courbes de dispersions avec une résolution optimale. Cette méthode nous a permis de montrer le caractère quasi-monomode, en condition d’excitation monomode, de la fibre multimode spéciale RLDO à 1310 nm et à 1550 nm. L’analyse de la propagation dans les fibres optiques, associée au modèle que nous avons développé pour comprendre le fonctionnement des coupleurs multimodes, a permis d’expliquer les difficultés rencontré avec les premières expérimentations de la topologie de réseau en étoile passive multimode et d’envisager des pistes de réalisation d’un prototype de réseau fonctionnel / In order to develop high capacity future-proof home network, the FUI 12 RLDO project suggests passive star network topology using multimode couplers. This topology encounters implementation difficulties due to the non-uniformity of the power distribution in the output ports of multimode couplers. Analyzing this problem shows that the properties of modes propagating in the network elements plays a key role in this non-uniform characteristics of multimode couplers. In order to characterize these modes propagating in the network, we have developed a complex optical frequency domain reflectometry (OFDR) setup. The phenomena limiting the sensitivity to the phase in OFDR – in fact, those related to the non-linear frequency tuning of the laser source - are investigated to contribute to a better understanding of the limiting mechanisms. Then we have tested the intensity and phase measurement performance of the developed setup. Later, we studied the optimal resolution conditions to characterize the modes in a multimode waveguide. We have also analyzed the uncertainty of the measurement of the chromatic dispersion of modes in case where it is impossible to determine whether one or several modes are present in a given dispersion curve. Additionally, we have introduced an adaptive time-frequency method, to obtain the dispersion curves with optimal resolution. This method allows us to show the versatility of the special RLDO multimode fiber (single-mode behavior under single-mode excitation at 1310 nm and 1550 nm). The analysis of the propagation in the optical fibers, associated with a model we have developed to study the behavior of multimode couplers, has permitted to explain encountered difficulties with the experiments of the multimode passive star network topology. This also gives insights to develop a functional prototype of network