Dissertations / Theses: 'Algorithmes online'

1

Liu, Ming. "Design and Evaluation of Algorithms for Online Machine Scheduling Problems." Phd thesis, Ecole Centrale Paris, 2009. http://tel.archives-ouvertes.fr/tel-00453316.

Full text

Abstract:

Dans cette thèse, nous proposons et évaluons des algorithmes pour résoudre des problèmes d'ordonnancement en ligne. Pendant des décennies, les études en ordonnancement considèrent des modèles déterministes où toutes les informations nécessaires pour la définition du problème sont supposées connues à l'avance. Cette hypothèse n'est généralement pas réaliste. Ceci a motivé les études sur l'ordonnancement en ligne. Dans un problème d'ordonnancement en ligne, un algorithme doit prendre des décisions sans connaissance du futur. L'analyse compétitive est généralement la méthode utilisée pour évaluer les performances de tels algorithmes. Dans cette analyse, la performance d'un algorithme en ligne est mesurée par le ratio compétitif qui est le ratio dans le pire cas entre la performance de la solution obtenue et celle d'une solution optimale hors ligne. Nous considérons principalement deux paradigmes en ligne: celui où les tâches se présentent dans la liste et celui où les tâches arrivent au fur et à mesure. Sur la base de ces deux paradigmes, nous considérons différents modèles : une seule machine, deux machines identiques parallèles, deux machines uniformes parallèles, batch machines et open shop. Pour chacun des problèmes, nous démontrons une borne inférieure de ratios compétitifs et proposons des algorithmes en ligne. Ensuite, nous évaluons la performance de ces algorithmes à l'aide de l'analyse compétitive. Pour certains problèmes, nous montrons que les algorithmes proposés sont optimaux dans le sens où le ratio compétitif est égal à la borne inférieure.

APA, Harvard, Vancouver, ISO, and other styles

2

Jin, Shendan. "Online computation beyond standard models." Electronic Thesis or Diss., Sorbonne université, 2020. http://www.theses.fr/2020SORUS152.

Full text

Abstract:

Dans le cadre standard du calcul en ligne, l’entrée de l’algorithme n’est pas entièrement connue à l’avance, mais elle est révélée progressivement sous forme d’une séquence de requêtes. Chaque fois qu'une requête arrive, l'algorithme en ligne doit prendre des décisions irrévocables pour servir la demande, sans connaissance des requêtes futures. Dans le domaine des algorithmes en ligne, le cadre standard utilisé pour évaluer les performances des algorithmes en ligne est l’analyse compétitive. De manière informelle, le concept d’analyse compétitive consiste à comparer les performances d’un algorithme en ligne dans le pire des cas à une solution optimale hors ligne qui aurait pu être calculée si toutes les données étaient connues d’avance. Dans cette thèse, nous étudierons de nouvelles façons d'approcher les problèmes en ligne. Dans un premier temps, nous étudions le calcul en ligne dans le modèle avec ré-optimisation, dans lequel l'irrévocabilité des décisions en ligne est relâchée. Autrement dit, l'algorithme en ligne est autorisé à revenir en arrière et changer les décisions précédemment prises. Plus précisément, nous montrons comment identifier le compromis entre le nombre de ré-optimisation et les performances des algorithmes en ligne pour le problème de couplage maximale en ligne. De plus, nous étudions des mesures autres que l'analyse compétitive pour évaluer les performances des algorithmes en ligne. Nous observons que parfois, l'analyse compétitive ne peut pas distinguer les performances de différents algorithmes en raison de la nature la plus défavorable du ratio de compétitivité. Nous démontrons qu'une situation similaire se pose dans le problème de la recherche linéaire. Plus précisément, nous revisitons le problème de la recherche linéaire et introduisons une mesure, qui peut être appliquée comme un raffinement du ratio de compétitivité. Enfin, nous étudions le calcul en ligne dans le modèle avec des conseils, dans lequel l'algorithme reçoit en entrée non seulement une séquence de requêtes, mais aussi quelques conseils sur la séquence de requêtes. Plus précisément, nous étudions un modèle récent avec des conseils non fiables, dans lequel les conseils peuvent être fiables ou non. Supposons que dans ce dernier cas, les conseils peuvent être générés à partir d'une source malveillante. Nous montrons comment identifier une stratégie optimale de Pareto pour le problème online bidding dans le modèle de conseil non fiable
In the standard setting of online computation, the input is not entirely available from the beginning, but is revealed incrementally, piece by piece, as a sequence of requests. Whenever a request arrives, the online algorithm has to make immediately irrevocable decisions to serve the request, without knowledge on the future requests. Usually, the standard framework to evaluate the performance of online algorithms is competitive analysis, which compares the worst-case performance of an online algorithm to an offline optimal solution. In this thesis, we will study some new ways of looking at online problems. First, we study the online computation in the recourse model, in which the irrevocability on online decisions is relaxed. In other words, the online algorithm is allowed to go back and change previously made decisions. More precisely, we show how to identify the trade-off between the number of re-optimization and the performance of online algorithms for the online maximum matching problem. Moreover, we study measures other than competitive analysis for evaluating the performance of online algorithms. We observe that sometimes, competitive analysis cannot distinguish the performance of different algorithms due to the worst-case nature of the competitive ratio. We demonstrate that a similar situation arises in the linear search problem. More precisely, we revisit the linear search problem and introduce a measure, which can be applied as a refinement of the competitive ratio. Last, we study the online computation in the advice model, in which the algorithm receives as input not only a sequence of requests, but also some advice on the request sequence. Specifically, we study a recent model with untrusted advice, in which the advice can be either trusted or untrusted. Assume that in the latter case, the advice can be generated from a malicious source. We show how to identify a Pareto optimal strategy for the online bidding problem in the untrusted advice model

APA, Harvard, Vancouver, ISO, and other styles

3

Liu, Ming Chu Chengbin. "Design and Evaluation of Algorithms for Online Machine Scheduling Problems." S. l. : S. n, 2009. http://theses.abes.fr/2009ECAP0028.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Nouinou, Hajar. "Ordonnancement semi-online sur machine unitaire pour l’industrie du futur." Thesis, Troyes, 2021. http://www.theses.fr/2021TROY0028.

Full text

Abstract:

Nous étudions la valeur de l’information dans des problèmes d’ordonnancement semi-online sur machine unitaire. Nous proposons ainsi des algorithmes semi-online pour résoudre ces problèmes et nous évaluons leurs performances. Contrairement aux problèmes d’ordonnancement classiques offline où le décideur connaît toutes les caractéristiques de l’instance à ordonnancer, dans les problèmes d’ordonnancement online ou semi-online la prise de décision est effectuée sans aucune information ou uniquement avec des informations partielles sur l’instance. Notre travail consiste à distinguer les informations qui peuvent améliorer la prise de décision dans un contexte d’ordonnancement semi-online des informations qui, même disponibles, n’apportent aucune amélioration. Nous traitons principalement les problèmes semi-online dont la fonction objective est la minimisation de la somme des dates de fin des tâches sur machine unitaire. Nous commençons par étudier plusieurs modèles semi-online avec des informations partielles sur les temps de traitement des tâches. Ensuite, nous considérons le problème avec une information sur les dates d’arrivée et finalement la combinaison de l’information sur les temps de traitements et les dates d’arrivée des tâches. Pour chaque problème étudié où l’information partielle est identifiée comme utile, nous proposons un algorithme semi-online intégrant l’information dans la prise de décision. Ensuite, nous évaluons sa performance à l’aide d’une analyse de compétitivité ou par étude expérimentale comparative
We study the value of information in semi-online single machine scheduling problems. We propose semi-online algorithms to solve these problems and evaluate their performances. Unlike the classical offline scheduling problems where the decision maker knows all characteristics of the instance to be scheduled, in online scheduling problems the decision-making is performed without previous information or only with partial information about the instance. Our work consists in distinguishing information that can improve the decision-making in a semi-online scheduling context from information that, even if available, does not bring any improvement. We mainly deal with semi-online problems for minimising the total completion time on a single machine. We start by studying several semi-online models with partial information on processing times of jobs. Then, we consider the problem with information on jobs release dates and finally the combination of information on processing times and jobs release dates. For each studied problem where partial information is identified as useful, we propose a semi-online algorithm integrating the information into the decision-making. We then evaluate its performance using a competitive analysis or a comparative experimental study

APA, Harvard, Vancouver, ISO, and other styles

5

Renault, Marc Paul. "Lower and upper bounds for online algorithms with advice." Paris 7, 2014. http://www.theses.fr/2014PA077196.

Full text

Abstract:

Les algorithmes en ligne fonctionnent dans un contexte où l'entrée est révélé au fur et à mesure du temps; chaque morceau révélé est appelé une demande. Après réception de chaque demahde, les algorithmes en ligne doivent prendre une action avant que la prochaine demande soit révélée, c'est-à-dire que les algorithmes en ligne doivent prendre une décision irrévocable basée sur les demandes déjà révélées sans aucune connaissance des demandes à venir. Le but est d'optimiser une fonction de coût dépendante de l'entrée. L'analyse compétitive est la méthode standard utilisée pour analyser la qualité des algorithmes en ligne. Le ratio compétitif est un ratio de pire cas, parmi toutes les séquences de demande finis, entre la performance de l'algorithme en ligne contre un algorithme optimal hors ligne pour la même séquence. Le ratio compétitif compare la performance d'un algorithme sans aucune connaissance de l'avenir contre un algorithme en pleine connaissance de l'avenir. Car l'absence totale de connaissance de l'avenir n'est souvent pas une hypothèse raisonnable, des modèles ont été proposés, appelés algorithmes en ligne avec conseil, qui donne les algorithmes en ligne l'accès à une quantité quantifiée des connaissances de l'avenir. L'intérêt de ce modèle est d'examiner comment le ratio compétitif change en fonction de la quantité de conseil. Dans cette thèse, il est présenté des bornes supérieures et inférieures dans ce modèle pour des problèmes en ligne classiques, tels que le problème de la k-serveur, de bin packing, de dual bin packing (sac à dos multiple), d'ordonnancement sur m machines identiques, du tampon de réordonnancement et de la mise à jour de la liste
Online algorithms operate in a setting where the input is revealed piece by piece; the pieces are called requests. After receiving each request, online algorithms must take an action before the next request is revealed, i. E. Online algorithms must make irrevocable decisions based on the input revealed so far without any knowledge of the future input. The goal is to optimize some cost function over the input. Competitive analysis is the standard method used to analyse the quality of online algorithms. The competitive ratio is the worst case ratio, over all valid finite request sequences, of the online algorithm's performance against an optimal offline algorithm for the same request sequence. The competitive ratio compares the performance of an algorithm with no knowledge about the future against an algorithm with full knowledge about the future. Since the complete absence of future knowledge is often not a reasonable assumption, models, termed online algorithms with advice, which give the online algorithms access to a quantified amount of future knowledge, have been proposed. The interest in this model is in examining how the competitive ratio changes as a function of the amount of advice. In this thesis, we present upper and lower bounds in the advice model for classical online problems such as the k-server problem, the bin packing problem, the dual bin packing (multiple knapsack) problem, scheduling problem on m identical machines, the reordering buffer management problem and the list update problem

APA, Harvard, Vancouver, ISO, and other styles

6

Teiller, Alexandre. "Aspects algorithmiques de l'optimisation « multistage »." Electronic Thesis or Diss., Sorbonne université, 2020. http://www.theses.fr/2020SORUS471.

Full text

Abstract:

En optimisation combinatoire classique, étant donné une instance d’un problème, il est demandé de trouver une bonne solution réalisable. Cependant, dans de nombreux cas, les données peuvent évoluer au cours du temps et il est demandé de résoudre une séquence d’instances. Gupta et al. (2014) et Eisenstat et al. (2014) ont proposé un modèle multistage où étant donné un horizon de temps, l’entrée est une séquence d’instances (une pour chaque pas de temps), et l’objectif est de trouver une séquence de solutions (une pour chaque pas de temps) qui atteindrait un compromis entre la qualité des solutions à chaque pas de temps et la stabilité/similarité des solutions pour des pas de temps consécutifs. Dans le Chapitre 1, nous présenterons un aperçu des problèmes d’optimisation prenant en compte des données évolutives. Dans le Chapitre 2, le problème du sac-à-dos est traité dans un contexte offline. La contribution principale est un schéma d’approximation polynomiale (PTAS). Dans le Chapitre 3, le cadre multistage est étudié pour des problèmes multistage dans un contexte online. La contribution principale est l’introduction d’une structure pour ces problèmes avec des bornes presque serrées supérieures et inférieures sur les meilleurs ratios compétitifs de ces modèles. Enfin, dans le Chapitre 4 est présenté une application directe du cadre multistage dans un contexte musical, i.e l’orchestration assistée par ordinateur avec son cible. Nous avons présenté une analyse théorique du problème, en montrant sa NP-difficulté, des résultats d’approximation ainsi que des expérimentations
N a classical combinatorial optimization setting, given an instance of a problem one needs to find a good feasible solution. However, in many situations, the data may evolve over time and one has to solve a sequence of instances. Gupta et al. (2014) and Eisenstat et al. (2014) proposed a multistage model where given a time horizon the input is a sequence of instances (one for each time step), and the goal is to find a sequence of solutions (one for each time step) reaching a trade-off between the quality of the solutions in each time step and the stability/similarity of the solutions in consecutive time steps. In Chapter 1 of the thesis, we will present an overview of optimization problems tackling evolving data. Then, in Chapter 2, the multistage knapsack problem is addressed in the offline setting. The main contribution is a polynomial time approximation scheme (PTAS) for the problem in the offline setting. In Chapter 3, the multistage framework is studied for multistage problems in the online setting. The main contribution of this chapter was the introduction of a structure for these problems and almost tight upper and lower bounds on the best-possible competitive ratio for these models. Finally in chapter 4 is presented a direct application of the multistage framework in a musical context i.e. the target-based computed-assisted orchestration problem. Is presented a theoretical analysis of the problem, with NP-hardness and approximation results as well as some experimentations

APA, Harvard, Vancouver, ISO, and other styles

7

Vallée, Sven. "Algorithmes d’optimisation pour un service de transport partagé à la demande." Thesis, Université de Lorraine, 2019. http://www.theses.fr/2019LORR0063.

Full text

Abstract:

L'objectif de cette thèse est de proposer des algorithmes d'optimisation efficaces pour un système de tranport en commun à la demande proposé par Padam Mobility, une start-up Parisienne. Après avoir modélisé le problème comme un DARP dynamique, trois modules d'optimisation sont présentés : un module online destiné à répondre aux requêtes en temps réel, un module de réinsertion pour insérer les requêtes rejetées par le module online et enfin un module offline basé sur une métaheuristique permettant d'optimiser en continue les itinéraires
The purpose of this thesis is to propose efficient optimization algorithms for an on-demand common transportation system operated by Padam Mobility, a Parisian company. Formalised as a dynamic DARP, we propose three optimisation modules to tackle the underlying problem : an online module to answer real-time requests, a reinsertion module to re-insert rejected requests and a metaheuristic-based offline module to continuously optimize the rides. The proposed methods are directly implemented in the company system and extensively tested on real instances

APA, Harvard, Vancouver, ISO, and other styles

8

Jankovic, Anja. "Towards Online Landscape-Aware Algorithm Selection in Numerical Black-Box Optimization." Electronic Thesis or Diss., Sorbonne université, 2021. http://www.theses.fr/2021SORUS302.

Full text

Abstract:

Les algorithmes d'optimisation de boîte noire (BBOA) sont conçus pour des scénarios où les formulations exactes de problèmes sont inexistantes, inaccessibles, ou trop complexes pour la résolution analytique. Les BBOA sont le seul moyen de trouver une bonne solution à un tel problème. En raison de leur applicabilité générale, les BBOA présentent des comportements différents lors de l'optimisation de différents types de problèmes. Cela donne un problème de méta-optimisation consistant à choisir l'algorithme le mieux adapté à un problème particulier, appelé problème de sélection d'algorithmes (AS). La vision d'automatiser cette sélection a vite gagné du terrain dans la communauté. Un moyen important de le faire est l'AS tenant compte du paysage, où le choix de l'algorithme est basé sur la prédiction de ses performances via des représentations numériques d'instances de problèmes appelées caractéristiques. Un défi clé auquel l'AS tenant compte du paysage est confrontée est le coût de calcul de l'extraction des caractéristiques, une étape qui précède l'optimisation. Dans cette thèse, nous proposons une approche d'AS tenant compte du paysage basée sur la trajectoire de recherche qui intègre cette étape d'extraction dans celle d'optimisation. Nous montrons que les caractéristiques calculées à l'aide de la trajectoire conduisent à des prédictions robustes et fiables des performances des algorithmes, et à de puissants modèles d'AS construits dessus. Nous présentons aussi plusieurs analyses préparatoires, y compris une perspective de combinaison de 2 stratégies de régression complémentaires qui surpasse des modèles classiques de régression simple et amplifie la qualité du sélecteur
Black-box optimization algorithms (BBOAs) are conceived for settings in which exact problem formulations are non-existent, inaccessible, or too complex for an analytical solution. BBOAs are essentially the only means of finding a good solution to such problems. Due to their general applicability, BBOAs can exhibit different behaviors when optimizing different types of problems. This yields a meta-optimization problem of choosing the best suited algorithm for a particular problem, called the algorithm selection (AS) problem. By reason of inherent human bias and limited expert knowledge, the vision of automating the selection process has quickly gained traction in the community. One prominent way of doing so is via so-called landscape-aware AS, where the choice of the algorithm is based on predicting its performance by means of numerical problem instance representations called features. A key challenge that landscape-aware AS faces is the computational overhead of extracting the features, a step typically designed to precede the actual optimization. In this thesis, we propose a novel trajectory-based landscape-aware AS approach which incorporates the feature extraction step within the optimization process. We show that the features computed using the search trajectory samples lead to robust and reliable predictions of algorithm performance, and to powerful algorithm selection models built atop. We also present several preparatory analyses, including a novel perspective of combining two complementary regression strategies that outperforms any of the classical, single regression models, to amplify the quality of the final selector

APA, Harvard, Vancouver, ISO, and other styles

9

Fersula, Jérémy. "Swarm Robotics : distributed Online Learning in the realm of Active Matter." Electronic Thesis or Diss., Sorbonne université, 2023. http://www.theses.fr/2023SORUS494.

Full text

Abstract:

Avec la miniaturisation des composants électroniques et l’augmentation des performances des CPU / GPU modernes, il devient techniquement possible de développer de petits robots capables de travailler en essaims de centaines ou de milliers d’unités. Lorsque l’on considère des systèmes composés d’un grand nombre de robots indépendants en interaction, l’individualité s’efface devant le collectif, et le comportement global de l’ensemble doit émerger de règles locales. Comprendre la dynamique d’un grand nombre d’unités en interaction devient une connaissance clé pour concevoir des essaims robotiques contrôlables et efficaces. Ce sujet est au cœur du domaine de la matière active, dans lequel les systèmes d’intérêt présentent des effets collectifs émergeant d’interactions physiques sans calcul. Cette thèse vise à utiliser des éléments de la matière active pour concevoir et comprendre des collectifs robotiques, interagissant à la fois au niveau physique et au niveau logiciel par le biais d’algorithmes d’apprentissage distribués. Nous commençons par étudier expérimentalement la dynamique d’agrégation d’un essaim de petits robots vibrants effectuant la phototaxie (c’est-à-dire la recherche de lumière). Les expériences sont déclinées dans différentes configurations, soit ad-hoc, soit mettant en œuvre un algorithme d’apprentissage distribué en ligne. Cette série d’expériences sert de référence pour l’algorithme, en montrant ses capacités et ses limites dans une situation réelle. Ces expériences sont approfondies en changeant la forme extérieure des robots, ce qui modifie les interactions physiques en ajoutant une réponse en orientation aux forces extérieures. Cet effet supplémentaire modifie la dynamique globale de l’essaim, montrant que le computation morphologique est en jeu. La nouvelle dynamique est comprise grâce à un modèle physique d’auto-alignement, ce qui permet d’étendre le travail expérimental in sillico et de suggérer de nouveaux effet à grande échelle dans les essaims de robots qui se réorientent. Enfin, nous présentons un modèle d’apprentissage distribué par le biais d’équations différentielles stochastiques. Ce modèle est basé sur l’échange de degrés de liberté internes qui s’associent à la dynamique des particules, qui sont les équivalents dans le contexte de l’apprentissage à un ensemble de paramètres et à un contrôleur. Le modèle donne des résultats similaires en simulation à ceux des expériences réelles et ouvre la voie à une analyse théorique à grande échelle de la dynamique produite par l’apprentissage distribué en ligne
CPUs / GPUs, it becomes technically possible to develop small robots able to work in swarms of hundreds or thousands of units. When considering systems comprised of a large number of in- dependent robots in interaction, the individuality vanishes before the collective, and the global behavior of the ensemble has to emerge from local rules. Understanding the dynamics of large number of interacting units becomes a knowledge key to design controllable and efficient robotic swarms. This topic happens to be at the core of the field of active matter, in which the sys- tems of interest display collective effects emerging from physical interactions without computation. This thesis aims at using elements of active matter to design and understand robotic collectives, interacting both at the physical level and the software level through distributed learning algorithms. We start by studying experimentally the aggregation dynamics of a swarm of small vibrating robots performing phototaxis (i.e. search of light). The experiments are declined in different confi- gurations, either ad-hoc or implementing a distributed and online learning algorithm. This series of experiments act as a benchmark for the algorithm, showing its capabilities and limits in a real world situation. These experiments are further expanded by changing the outer shape of the robots, modifying the physical interactions by adding a force re-orientation response. This additional effect changes the global dynamics of the swarm, showing Morphological Computation at play. The new dynamics is understood through a physical model of self-alignment, allowing to extend the experimental work in sillico and hint for unseen global effects in swarms of re-orienting robots. Finally, we introduce a model of distributed learning through stochastic ODEs. This model is based on the exchange of internal degrees of freedom that couples to the dynamics of the particles, equivalents in the context of learning as a set of parameters and a controller. It shows similar results in simulation as the real-world experiments and opens up a way to a large-scale analysis of distributed and online learning dynamics

APA, Harvard, Vancouver, ISO, and other styles

10

Alinia, Bahram. "Optimal resource allocation strategies for electric vehicles in smart grids." Thesis, Evry, Institut national des télécommunications, 2018. http://www.theses.fr/2018TELE0012/document.

Full text

Abstract:

Avec les préoccupations environnementales croissantes liées aux émissions de carbone et la chute rapide des prix des batteries, la part de marché des véhicules électriques (EV) augmente rapidement. Le nombre croissant de EV ainsi que les progrès sans précédent dans la capacité de la batterie et de la technologie entraîne une augmentation drastique de la demande totale d'énergie destinée aux véhicules électriques. Cette forte demande de charge rend complexe le problème de planification de la charge. Même en prenant avantage de la propriété reportable des demandes de charge et d'une planification adéquate, la demande globale pourrait dépasser le taux de charge tolérable des stations, étant donné les contraintes physiques des dispositifs de charge et des transformateurs. Le principal défi est la nécessité de concevoir des solutions en ligne puisque, dans la pratique, l'ordonnanceur ne dispose d'aucune information sur les arrivées futures d'EV. Cette thèse étudie le problème d'ordonnancement des EV en ligne et fournit trois contributions principales. Premièrement, nous démontrons que le problème classique de la programmation en ligne des tâches sensibles aux échéances avec des valeurs partielles est similaire au problème d'ordonnancement EV et étudions l'extension de la programmation des charges EV en prenant en compte de la limite de traitement des travaux. Le problème réside dans la catégorie des problèmes d'ordonnancement en ligne couplés dans le temps sans disponibilité d'informations futures. Le premier algorithme proposé est déterministe, tandis que le second est randomisé et bénéficie d'une complexité de calcul plus faible. Deuxièmement, nous formulons un problème de maximisation du bien-être social pour la planification de la charge des EV avec une contrainte de capacité de charge. Nous avons conçu des algorithmes d'ordonnancement de charge qui non seulement fonctionnent dans un scénario en ligne, mais aussi qui répondent aux deux principaux défis suivants : (i) fournir un engagement à l'arrivée ; (ii) garantir la résistance aux stratégies (de groupe). Des simulations approfondies utilisant des traces réelles démontrent l'efficacité de nos algorithmes d'ordonnancement en ligne par rapport à la solution hors-ligne optimale non-engagée. La troisième contribution concerne la planification en ligne des véhicules électriques dans un réseau de recharge adaptatif (ACN) avec des contraintes de pics locaux et globaux. Nous avons conçu un algorithme d'ordonnancement primal-dual de faible complexité qui atteint un rapport d'approximation borné. Des résultats expérimentaux détaillés basés sur des traces montrent que les performances des algorithmes en ligne proposés sont proches de l'optimum hors ligne et surpassent les solutions existantes
With the increased environmental concerns related to carbon emission, and rapid drop in battery prices (e.g., 35% drop in 2017), the market share of Electric Vehicles (EVs) is rapidly growing. The growing number of EVs along with the unprecedented advances in battery capacity and technology results in drastic increase in the total energy demand of EVs. This large charging demand makes the EV charging scheduling problem challenging. The critical challenge is the need for online solution design since in practical scenario the scheduler has no information of future arrivals of EVs in a time-coupled underlying problem. This thesis studies online EV scheduling problem and provides three main contributions. First, we demonstrate that the classical problem of online scheduling of deadlinesensitive jobs with partial values is similar to the EV scheduling problem and study the extension to EV charging scheduling by taking into account the processing rate limit of jobs as an additional constraint to the original problem. The problem lies in the category of time-coupled online scheduling problems without availability of future information. Using competitive ratio, as a well-established performance metric, two online algorithms, both of which are shown to be (2 − 1/U)-competitive are proposed, where U is the maximum scarcity level, a parameter that indicates demand-to-supply ratio. Second, we formulate a social welfare maximization problem for EV charging scheduling with charging capacity constraint. We devise charging scheduling algorithms that not only work in online scenario, but also they address the following two key challenges: (i) to provide on-arrival commitment; respecting the capacity constraint may hinder fulfilling charging requirement of deadline-constrained EVs entirely. Therefore, committing a guaranteed charging amount upon arrival of each EV is highly required; (ii) to guarantee (group)-strategy-proofness as a salient feature to promote EVs to reveal their true type and do not collude with other EVs. Third, we tackle online scheduling of EVs in an adaptive charging network (ACN) with local and global peak constraints. Two alternatives in resource-limited scenarios are to maximize the social welfare by partially charging the EVs (fractional model) or selecting a subset of EVs and fully charge them (integral model). For the fractional model, both offline and online algorithms are devised. We prove that the offline algorithm is optimal. We prove the online algorithm achieves a competitive ratio of 2. The integral model, however, is more challenging since the underlying problem is NP-hard due to 0/1 selection criteria of EVs. Hence, efficient solution design is challenging even in offline setting. We devise a low-complexity primal-dual scheduling algorithm that achieves a bounded approximation ratio. Built upon the offline approximate algorithm, we propose an online algorithm and analyze its competitive ratio in special cases

APA, Harvard, Vancouver, ISO, and other styles

11

Jégou, Arnaud. "Réseaux sociaux implicites et explicites, exploiter leur puissance grâce à la décentralisation." Thesis, Rennes 1, 2014. http://www.theses.fr/2014REN1S069/document.

Full text

Abstract:

La personnalisation de contenu est devenu une fonctionnalité cruciale sur Internet, car elle aide les utilisateurs à filtrer le contenu qu'ils ne trouvent pas intéressant. Ces systèmes collectent une grande quantité de données pour fournir un service efficace. Cela implique que les utilisateurs perdent le contrôle sur leurs données, ce qui pose un problème de respect de la vie privée. Les systèmes pair-à-pair (P2P) offrent une intéressante alternative aux services centralisés. Dans ces systèmes, chaque utilisateur est responsable de ses données et contrôle lesquelles sont utilisées par le système. Néanmoins, ces systèmes ne règlent que partiellement le problème de respect de la vie privée car, en général, tous les utilisateurs du système peuvent accéder aux données des autres utilisateur. De plus il est difficile de s'assurer de l'identité des utilisateurs, et donc de leur faire confiance. C'est un problème dans un contexte comme une place de marché en ligne, comme par exemple eBay. Dans un contexte P2P, il est difficile de s'assurer qu'un utilisateur est bien qui il dit être, et qu'il remplira sa part du marché. Malgré ces défauts nous pensons que le P2P est le meilleur moyen de résoudre le problème de vie privée. Il faut néanmoins améliorer les systèmes P2P afin de mieux protéger les données utilisateur et augmenter la confiance entre les utilisateurs. Dans cette thèse nous présentons quatre contributions allant dans ce sens. La première, TAPS, fournit aux utilisateurs une estimation de la fiabilité des autres utilisateurs en fonction d'informations extraites d'un réseau social, ainsi que chemin reliant les deux utilisateurs sur le réseau. Par exemple, TAPS informera un utilisateur, Bob, qu'un autre utilisateur, Carole, est la sœur d'un collègue de sa femme Alice. Ainsi, Bob connaît l'identité de Carole et sait si il peut lui faire confiance. La seconde, PTAPS, est une alternative à TAPS préservant la vie privée des utilisateurs. Dans TAPS, les utilisateurs fournissent au système la liste de leurs amis. Dans PTAPS ces informations sont masqué et ne sont accessibles qu'aux amis de l'utilisateur. La troisième, FreeRec, est un système de personnalisation assurant l'anonymat des utilisateurs. Les problèmes de vie privée touchant les réseaux P2P sont dû en grande partie au fait qu'il est possible d'associer les actions d'un utilisateur à son identité . Une solution est de masquer l'identité de l'utilisateur aux autres utilisateurs. FreeRec fournit des recommandations tout en assurant l'anonymat des utilisateurs grâce à du routage en ognon. La dernière, DPPC, est un algorithme masquant les données des utilisateurs dans un système de recommandation. Les données des utilisateurs peuvent contenir des informations précises sur l'utilisateur. Il a été démontré que ces données sont parfois suffisantes pour découvrir l'identité de l'utilisateur. DPPC masques ces données tout en permettant à l'utilisateur de bénéficier du système de recommandation
Content personalization became an important functionality on the Internet, as it helps users to filter out uninteresting content. These systems collect a lot of data to provide accurate recommendations. This implies that the users loose control over their data, which causes a problem of privacy. Peer-to-peer (P2P) systems offer an interesting alternative to centralized services. In these systems, each user is responsible for her own data and control which ones are used by the system. Nevertheless, these systems solve only partially the privacy issue as, in general, all users of the system can access the data of the other users. In addition, it is difficult to know the true identity of users, and thus it is difficult to trust them. Thus is a problem in a context such as an online marketplace, such as eBay. In a P2P context, it is difficult to ensure that a user is really who she says she is, and that she will do her part of the job. Despites these weaknesses, we believe that P2P is the best way to solve the privacy issue. It is however necessary to improve P2P systems in order to better protect the users data and increase the trust between users. In this thesis we present four contributions going in that direction. The first one, TAPS, provides users with an estimation of the trustworthiness of other users based on information extracted from a social network, as well as a path linking the two users in this network. For example, TAPS will inform a user, Bob, that another user, Carol, is the sister of a colleague of his wife, Alice. Thus, Bob knows the identity of Carole and knows if he can trust her. The second one, PTAPS, is an alternative version of TAPS preserving the users' privacy. In TAPS, users provide the system with their list of friends. In PTAPS this information is hidden and only accessible by the user's friends. The third one, FreeRec, is a personalization system ensuring the users' anonymity. Privacy issues in P2P systems are mainly caused by the fact that it is possible to associate the action of a user with her identity. A solution is to hide the user's identity to the other users. FreeRec provides recommendations while ensuring users's anonymity thanks to onion routing. The last contribution, DPPC, is an algorithm hiding users' data in a recommendation system. Users data can contain precise information about the user. It has been showed that these data are sometimes enough to discover the user's true identity. DPPC hides these data while allowing the user to receive recommendations

APA, Harvard, Vancouver, ISO, and other styles

12

Cure, Morgane. "Concurrence à l'ère du numérique : exemples dans l'industrie hôtelière." Electronic Thesis or Diss., Institut polytechnique de Paris, 2020. http://www.theses.fr/2020IPPAG013.

Full text

Abstract:

La numérisation croissante de l’économie bouleverse les canaux de distribution des vendeurs et favorise l’émergence de nouveaux acteurs : les plateformes d’intermédiation. Avec elles, le modèle traditionnel de revente laisse place à un modèle d’agence et crée un terrain fertile à différents cas de restrictions verticales. La numérisation grandissante des marchés pousse les autorités de concurrence à questionner et adapter leur analyse économique des pratiques. Cette thèse se concentre sur l’industrie hôtelière qui fait l’objet de plusieurs cas d’espèces. Les pratiques contractuelles telles que les clauses de parité de prix imposées par les agences de voyages en ligne aux hôteliers ont fait l’objet de nombreuses investigations, principalement en Europe. Le premier chapitre de cette thèse développe un modèle d’estimation structurelle de la demande permettant d’évaluer le degré de substitution entre les canaux de distribution en en ligne d'une chaîne d'hôtels, élément crucial retenu dans la définition des marchés. A l’issue des différents cas de concurrence, les clauses de parité de prix ont partiellement ou totalement été interdites dans plusieurs pays. En réponse, les plateformes d’intermédiation ont développé de nouveaux programmes offrant aux hôteliers une visibilité accrue en l’échange d’une application volontaire de la clause de parité de prix. Le second chapitre de cette thèse étudie l’effet de l’adoption de ce type de programme sur les prix fixés par les hôteliers en différenciant l’effet lié à l’accroissement de la demande, permis par les gains de visibilité, de ceux liés à l’auto-application de la clause et à la hausse des commissions inhérentes au programme. Cette thèse porte également sur le lien entre les agences de voyage en ligne et un autre type de plateforme sur ce marché, les sites de comparaison de prix. Ces derniers promettent aux consommateurs l'affichage des offres les plus compétitives du marché mais les critères utilisés dans les algorithmes de classement font désormais débat. D'autre part, l'intégration verticale des certaines de ces plateformes à de plus grands groupes, en possédant déjà plusieurs, interroge leur impartialité. Le troisième chapitre de cette thèse étudie l’impact de l'intégration de Kayak et plusieurs agences de voyage en ligne (comme Booking.com) au sein du groupe Booking Holding sur les classements des hôtels et des canaux de vente affichés sur le site de comparaison de prix
The growing digitalization of the economy has been disrupting the sellers distribution channels and has been favoring the emergence of new players: intermediation platforms. Meanwhile the traditional resale model gives way to an agency model and creates fertile ground for different cases of vertical restraints. The increasing digitalization of markets therefore pushes competition authorities to question and adapt their economic analysis of practices. This thesis focuses on the hotel industry which has been the subject of several specific cases, especially in Europe. Contractual practices such as price parity clauses imposed by online travel agencies to hotels have been the subject of numerous investigations. The first chapter of this thesis develops a model of structural demand estimation, allowing to assess the degree of substitution between the online distribution channels of a hotel chain, a crucial element in the market definition. Following the various competition cases, price parity clauses were partially or completely prohibited in several countries. In response, the platforms have developed new programs offering hotels an increased visibility in exchange of the voluntary compliance of price parity clauses. The second chapter of this thesis studies the effect of the adoption of this program on the prices set by the hotels separating the effects linked to the demand increase, thanks to visibility gains, from those linked to the clause compliance and fee increase linked to the program. This thesis also deals with the link between online travel agencies and another type of platforms: price comparison websites. The latter promise consumers the display of the most competitive offers on the market but the criteria used in the ranking algorithms are now debated. Moreover, their vertical integration into larger groups, which also have online travel agencies, raises questions about their impartiality. The third chapter studies the impact of the integration of Kayak and several online travel agencies (such as Booking.com) within the Booking Holding group on the ranking of hotels and sales channels displayed on the price comparison website

APA, Harvard, Vancouver, ISO, and other styles

13

Labernia, Fabien. "Algorithmes efficaces pour l’apprentissage de réseaux de préférences conditionnelles à partir de données bruitées." Thesis, Paris Sciences et Lettres (ComUE), 2018. http://www.theses.fr/2018PSLED018/document.

Full text

Abstract:

La croissance exponentielle des données personnelles, et leur mise à disposition sur la toile, a motivé l’émergence d’algorithmes d’apprentissage de préférences à des fins de recommandation, ou d’aide à la décision. Les réseaux de préférences conditionnelles (CP-nets) fournissent une structure compacte et intuitive pour la représentation de telles préférences. Cependant, leur nature combinatoire rend leur apprentissage difficile : comment apprendre efficacement un CP-net au sein d’un milieu bruité, tout en supportant le passage à l’échelle ?Notre réponse prend la forme de deux algorithmes d’apprentissage dont l’efficacité est soutenue par de multiples expériences effectuées sur des données réelles et synthétiques.Le premier algorithme se base sur des requêtes posées à des utilisateurs, tout en prenant en compte leurs divergences d’opinions. Le deuxième algorithme, composé d’une version hors ligne et en ligne, effectue une analyse statistique des préférences reçues et potentiellement bruitées. La borne de McDiarmid est en outre utilisée afin de garantir un apprentissage en ligne efficace
The rapid growth of personal web data has motivated the emergence of learning algorithms well suited to capture users’ preferences. Among preference representation formalisms, conditional preference networks (CP-nets) have proven to be effective due to their compact and explainable structure. However, their learning is difficult due to their combinatorial nature.In this thesis, we tackle the problem of learning CP-nets from corrupted large datasets. Three new algorithms are introduced and studied on both synthetic and real datasets.The first algorithm is based on query learning and considers the contradictions between multiple users’ preferences by searching in a principled way the variables that affect the preferences. The second algorithm relies on information-theoretic measures defined over the induced preference rules, which allow us to deal with corrupted data. An online version of this algorithm is also provided, by exploiting the McDiarmid's bound to define an asymptotically optimal decision criterion for selecting the best conditioned variable and hence allowing to deal with possibly infinite data streams

APA, Harvard, Vancouver, ISO, and other styles

14

Peel, Thomas. "Algorithmes de poursuite stochastiques et inégalités de concentration empiriques pour l'apprentissage statistique." Thesis, Aix-Marseille, 2013. http://www.theses.fr/2013AIXM4769/document.

Full text

Abstract:

La première partie de cette thèse introduit de nouveaux algorithmes de décomposition parcimonieuse de signaux. Basés sur Matching Pursuit (MP) ils répondent au problème suivant : comment réduire le temps de calcul de l'étape de sélection de MP, souvent très coûteuse. En réponse, nous sous-échantillonnons le dictionnaire à chaque itération, en lignes et en colonnes. Nous montrons que cette approche fondée théoriquement affiche de bons résultats en pratique. Nous proposons ensuite un algorithme itératif de descente de gradient par blocs de coordonnées pour sélectionner des caractéristiques en classification multi-classes. Celui-ci s'appuie sur l'utilisation de codes correcteurs d'erreurs transformant le problème en un problème de représentation parcimonieuse simultanée de signaux. La deuxième partie expose de nouvelles inégalités de concentration empiriques de type Bernstein. En premier, elles concernent la théorie des U-statistiques et sont utilisées pour élaborer des bornes en généralisation dans le cadre d'algorithmes de ranking. Ces bornes tirent parti d'un estimateur de variance pour lequel nous proposons un algorithme de calcul efficace. Ensuite, nous présentons une version empirique de l'inégalité de type Bernstein proposée par Freedman [1975] pour les martingales. Ici encore, la force de notre borne réside dans l'introduction d'un estimateur de variance calculable à partir des données. Cela nous permet de proposer des bornes en généralisation pour l'ensemble des algorithmes d'apprentissage en ligne améliorant l'état de l'art et ouvrant la porte à une nouvelle famille d'algorithmes d'apprentissage tirant parti de cette information empirique
The first part of this thesis introduces new algorithms for the sparse encoding of signals. Based on Matching Pursuit (MP) they focus on the following problem : how to reduce the computation time of the selection step of MP. As an answer, we sub-sample the dictionary in line and column at each iteration. We show that this theoretically grounded approach has good empirical performances. We then propose a bloc coordinate gradient descent algorithm for feature selection problems in the multiclass classification setting. Thanks to the use of error-correcting output codes, this task can be seen as a simultaneous sparse encoding of signals problem. The second part exposes new empirical Bernstein inequalities. Firstly, they concern the theory of the U-Statistics and are applied in order to design generalization bounds for ranking algorithms. These bounds take advantage of a variance estimator and we propose an efficient algorithm to compute it. Then, we present an empirical version of the Bernstein type inequality for martingales by Freedman [1975]. Again, the strength of our result lies in the variance estimator computable from the data. This allows us to propose generalization bounds for online learning algorithms which improve the state of the art and pave the way to a new family of learning algorithms taking advantage of this empirical information

APA, Harvard, Vancouver, ISO, and other styles

15

Frery, Jordan. "Ensemble Learning for Extremely Imbalced Data Flows." Thesis, Lyon, 2019. http://www.theses.fr/2019LYSES034.

Full text

Abstract:

L'apprentissage machine est l'étude de la conception d'algorithmes qui apprennent à partir des données d'apprentissage pour réaliser une tâche spécifique. Le modèle résultant est ensuite utilisé pour prédire de nouveaux points de données (invisibles) sans aucune aide extérieure. Ces données peuvent prendre de nombreuses formes telles que des images (matrice de pixels), des signaux (sons,...), des transactions (âge, montant, commerçant,...), des journaux (temps, alertes, ...). Les ensembles de données peuvent être définis pour traiter une tâche spécifique telle que la reconnaissance d'objets, l'identification vocale, la détection d'anomalies, etc. Dans ces tâches, la connaissance des résultats escomptés encourage une approche d'apprentissage supervisé où chaque donnée observée est assignée à une étiquette qui définit ce que devraient être les prédictions du modèle. Par exemple, dans la reconnaissance d'objets, une image pourrait être associée à l'étiquette "voiture" qui suggère que l'algorithme d'apprentissage doit apprendre qu'une voiture est contenue dans cette image, quelque part. Cela contraste avec l'apprentissage non supervisé où la tâche à accomplir n'a pas d'étiquettes explicites. Par exemple, un sujet populaire dans l'apprentissage non supervisé est de découvrir les structures sous-jacentes contenues dans les données visuelles (images) telles que les formes géométriques des objets, les lignes, la profondeur, avant d'apprendre une tâche spécifique. Ce type d'apprentissage est évidemment beaucoup plus difficile car il peut y avoir un nombre infini de concepts à saisir dans les données. Dans cette thèse, nous nous concentrons sur un scénario spécifique du cadre d'apprentissage supervisé : 1) l'étiquette d'intérêt est sous-représentée (p. ex. anomalies) et 2) l'ensemble de données augmente avec le temps à mesure que nous recevons des données d'événements réels (p. ex. transactions par carte de crédit). En fait, ces deux problèmes sont très fréquents dans le domaine industriel dans lequel cette thèse se déroule
Machine learning is the study of designing algorithms that learn from trainingdata to achieve a specific task. The resulting model is then used to predict overnew (unseen) data points without any outside help. This data can be of manyforms such as images (matrix of pixels), signals (sounds,...), transactions (age,amount, merchant,...), logs (time, alerts, ...). Datasets may be defined to addressa specific task such as object recognition, voice identification, anomaly detection,etc. In these tasks, the knowledge of the expected outputs encourages a supervisedlearning approach where every single observed data is assigned to a label thatdefines what the model predictions should be. For example, in object recognition,an image could be associated with the label "car" which suggests that the learningalgorithm has to learn that a car is contained in this picture, somewhere. This is incontrast with unsupervised learning where the task at hand does not have explicitlabels. For example, one popular topic in unsupervised learning is to discoverunderlying structures contained in visual data (images) such as geometric formsof objects, lines, depth, before learning a specific task. This kind of learning isobviously much harder as there might be potentially an infinite number of conceptsto grasp in the data. In this thesis, we focus on a specific scenario of thesupervised learning setting: 1) the label of interest is under represented (e.g.anomalies) and 2) the dataset increases with time as we receive data from real-lifeevents (e.g. credit card transactions). In fact, these settings are very common inthe industrial domain in which this thesis takes place

APA, Harvard, Vancouver, ISO, and other styles

16

Aliou, Diallo Aoudi Mohamed Habib. "Local matching algorithms on the configuration model." Electronic Thesis or Diss., Compiègne, 2023. http://www.theses.fr/2023COMP2742.

Full text

Abstract:

Nous proposons une alternative à l’approche prévalente dans les algorithmes de mariage en ligne. Basés sur le choix d’un critère de mariage, nous construisons des algorithmes dits locaux. Ces algorithmes sont locaux dans le sens où chacun des individus est tour à tour soumis au critère de mariage choisi. Ce qui nous amène à démontrer que le nombre de sommets qui finissent mariés lorsque chaque individu adopte une stratégie prédéfinie est solution d’une équation différentielle ordinaire. Grâce à cette approche nous prédisons les performances et comparons deux algorithmes/stratégies. Pour émuler l'asymptotique des graphes, nous utilisons le modèle de configuration basé sur un échantillonnage de la distribution de degré du graphe d'intérêt. Et globalement notre méthode peut être vue comme une généralisation de la Differential Equation Method de Wormald. Il est à noter que l’approche en ligne se concentre principalement sur les graphes bipartis
The present thesis constructs an alternative framework to online matching algorithms on large graphs. Using the configuration model to mimic the degree distributions of large networks, we are able to build algorithms based on local matching policies for nodes. Thus, we are allowed to predict and approximate the performances of a class of matching policies given the degree distributions of the initial network. Towards this goal, we use a generalization of the differential equation method to measure valued processes. Through-out the text, we provide simulations and a comparison to the seminal work of Karp, Vazirani and Vazirani based on the prevailing viewpoint in online bipartite matching

APA, Harvard, Vancouver, ISO, and other styles

17

Li, Le. "Online stochastic algorithms." Thesis, Angers, 2018. http://www.theses.fr/2018ANGE0031.

Full text

Abstract:

Cette thèse travaille principalement sur trois sujets. Le premier concentre sur le clustering en ligne dans lequel nous présentons un nouvel algorithme stochastique adaptatif pour regrouper des ensembles de données en ligne. Cet algorithme repose sur l'approche quasi-bayésienne, avec une estimation dynamique (i.e., dépendant du temps) du nombre de clusters. Nous prouvons que cet algorithme atteint une borne de regret de l'ordre et que cette borne est asymptotiquement minimax sous la contrainte sur le nombre de clusters. Nous proposons aussi une implémentation par RJMCMC. Le deuxième sujet est lié à l'apprentissage séquentiel des courbes principales qui cherche à résumer une séquence des données par une courbe continue. Pour ce faire, nous présentons une procédure basée sur une approche maximum a posteriori pour le quasi-posteriori de Gibbs. Nous montrons que la borne de regret de cet algorithme et celui de sa version adaptative est sous-linéaire en l'horizon temporel T. En outre, nous proposons une implémentation par un algorithme glouton local qui intègre des éléments de sleeping experts et de bandit à plusieurs bras. Le troisième concerne les travaux qui visent à accomplir des tâches pratiques au sein d'iAdvize, l'entreprise qui soutient cette thèse. Il inclut l'analyse des sentiments pour les messages textuels et l'implémentation de chatbot dans lesquels la première est réalisé par les méthodes classiques dans la fouille de textes et les statistiques et la seconde repose sur le traitement du langage naturel et les réseaux de neurones artificiels
This thesis works mainly on three subjects. The first one is online clustering in which we introduce a new and adaptive stochastic algorithm to cluster online dataset. It relies on a quasi-Bayesian approach, with a dynamic (i.e., time-dependent) estimation of the (unknown and changing) number of clusters. We prove that this algorithm has a regret bound of the order of and is asymptotically minimax under the constraint on the number of clusters. A RJMCMC-flavored implementation is also proposed. The second subject is related to the sequential learning of principal curves which seeks to represent a sequence of data by a continuous polygonal curve. To this aim, we introduce a procedure based on the MAP of Gibbs-posterior that can give polygonal lines whose number of segments can be chosen automatically. We also show that our procedure is supported by regret bounds with sublinear remainder terms. In addition, a greedy local search implementation that incorporates both sleeping experts and multi-armed bandit ingredients is presented. The third one concerns about the work which aims to fulfilling practical tasks within iAdvize, the company which supports this thesis. It includes sentiment analysis for textual messages by using methods in both text mining and statistics, and implementation of chatbot based on nature language processing and neural networks

APA, Harvard, Vancouver, ISO, and other styles

18

Alinia, Bahram. "Optimal resource allocation strategies for electric vehicles in smart grids." Electronic Thesis or Diss., Evry, Institut national des télécommunications, 2018. http://www.theses.fr/2018TELE0012.

Full text

Abstract:

Avec les préoccupations environnementales croissantes liées aux émissions de carbone et la chute rapide des prix des batteries, la part de marché des véhicules électriques (EV) augmente rapidement. Le nombre croissant de EV ainsi que les progrès sans précédent dans la capacité de la batterie et de la technologie entraîne une augmentation drastique de la demande totale d'énergie destinée aux véhicules électriques. Cette forte demande de charge rend complexe le problème de planification de la charge. Même en prenant avantage de la propriété reportable des demandes de charge et d'une planification adéquate, la demande globale pourrait dépasser le taux de charge tolérable des stations, étant donné les contraintes physiques des dispositifs de charge et des transformateurs. Le principal défi est la nécessité de concevoir des solutions en ligne puisque, dans la pratique, l'ordonnanceur ne dispose d'aucune information sur les arrivées futures d'EV. Cette thèse étudie le problème d'ordonnancement des EV en ligne et fournit trois contributions principales. Premièrement, nous démontrons que le problème classique de la programmation en ligne des tâches sensibles aux échéances avec des valeurs partielles est similaire au problème d'ordonnancement EV et étudions l'extension de la programmation des charges EV en prenant en compte de la limite de traitement des travaux. Le problème réside dans la catégorie des problèmes d'ordonnancement en ligne couplés dans le temps sans disponibilité d'informations futures. Le premier algorithme proposé est déterministe, tandis que le second est randomisé et bénéficie d'une complexité de calcul plus faible. Deuxièmement, nous formulons un problème de maximisation du bien-être social pour la planification de la charge des EV avec une contrainte de capacité de charge. Nous avons conçu des algorithmes d'ordonnancement de charge qui non seulement fonctionnent dans un scénario en ligne, mais aussi qui répondent aux deux principaux défis suivants : (i) fournir un engagement à l'arrivée ; (ii) garantir la résistance aux stratégies (de groupe). Des simulations approfondies utilisant des traces réelles démontrent l'efficacité de nos algorithmes d'ordonnancement en ligne par rapport à la solution hors-ligne optimale non-engagée. La troisième contribution concerne la planification en ligne des véhicules électriques dans un réseau de recharge adaptatif (ACN) avec des contraintes de pics locaux et globaux. Nous avons conçu un algorithme d'ordonnancement primal-dual de faible complexité qui atteint un rapport d'approximation borné. Des résultats expérimentaux détaillés basés sur des traces montrent que les performances des algorithmes en ligne proposés sont proches de l'optimum hors ligne et surpassent les solutions existantes
With the increased environmental concerns related to carbon emission, and rapid drop in battery prices (e.g., 35% drop in 2017), the market share of Electric Vehicles (EVs) is rapidly growing. The growing number of EVs along with the unprecedented advances in battery capacity and technology results in drastic increase in the total energy demand of EVs. This large charging demand makes the EV charging scheduling problem challenging. The critical challenge is the need for online solution design since in practical scenario the scheduler has no information of future arrivals of EVs in a time-coupled underlying problem. This thesis studies online EV scheduling problem and provides three main contributions. First, we demonstrate that the classical problem of online scheduling of deadlinesensitive jobs with partial values is similar to the EV scheduling problem and study the extension to EV charging scheduling by taking into account the processing rate limit of jobs as an additional constraint to the original problem. The problem lies in the category of time-coupled online scheduling problems without availability of future information. Using competitive ratio, as a well-established performance metric, two online algorithms, both of which are shown to be (2 − 1/U)-competitive are proposed, where U is the maximum scarcity level, a parameter that indicates demand-to-supply ratio. Second, we formulate a social welfare maximization problem for EV charging scheduling with charging capacity constraint. We devise charging scheduling algorithms that not only work in online scenario, but also they address the following two key challenges: (i) to provide on-arrival commitment; respecting the capacity constraint may hinder fulfilling charging requirement of deadline-constrained EVs entirely. Therefore, committing a guaranteed charging amount upon arrival of each EV is highly required; (ii) to guarantee (group)-strategy-proofness as a salient feature to promote EVs to reveal their true type and do not collude with other EVs. Third, we tackle online scheduling of EVs in an adaptive charging network (ACN) with local and global peak constraints. Two alternatives in resource-limited scenarios are to maximize the social welfare by partially charging the EVs (fractional model) or selecting a subset of EVs and fully charge them (integral model). For the fractional model, both offline and online algorithms are devised. We prove that the offline algorithm is optimal. We prove the online algorithm achieves a competitive ratio of 2. The integral model, however, is more challenging since the underlying problem is NP-hard due to 0/1 selection criteria of EVs. Hence, efficient solution design is challenging even in offline setting. We devise a low-complexity primal-dual scheduling algorithm that achieves a bounded approximation ratio. Built upon the offline approximate algorithm, we propose an online algorithm and analyze its competitive ratio in special cases

APA, Harvard, Vancouver, ISO, and other styles

19

López, Dawn Ricardo José. "Modélisation stochastique et analyse des données pour la diffusion d'information dans les plateformes sociales en ligne." Electronic Thesis or Diss., Sorbonne université, 2023. https://accesdistant.sorbonne-universite.fr/login?url=https://theses-intra.sorbonne-universite.fr/2023SORUS036.pdf.

Full text

Abstract:

Le marketing d'influenceurs est devenu une industrie florissante dont la valeur du marché mondial devrait atteindre 15 milliards de dollars d'ici 2022. Le problème publicitaire auquel ces agences sont confrontées est le suivant : compte tenu d'un budget monétaire, trouver un ensemble d'influenceurs appropriés qui peuvent créer et publier des posts de différents types (par exemple, texte, image, vidéo) pour la promotion d'un produit cible. L'objectif de la campagne est de maximiser à travers une ou plusieurs plateformes sociales en ligne une certaine mesure d'impact d'intérêt, par exemple le nombre d'impressions, les ventes (ROI), ou la portée de l'audience. Dans cette thèse, nous créons des formulations continues originales du problème du marketing d'influence budgétisé par deux cadres, un statique et un dynamique, basés sur la connaissance de l'annonceur de la métrique d'impact, et la nature des décisions de l'annonceur sur un horizon temporel. Le modèle statique est formulé comme un programme convexe, et nous proposons un algorithme itératif efficace basé sur la méthode de Frank-Wolfe, qui converge vers l'optimum global et présente une faible complexité de calcul. Nous suggérons également une règle empirique quasi-optimale plus simple, qui peut donner de bons résultats dans de nombreux scénarios pratiques. En raison de la nature du modèle dynamique, nous ne pouvons plus résoudre un problème de maximisation de l'utilité du réseau, puisque le retour sur investissement est inconnu, éventuellement bruyant, continu et coûteux à évaluer pour l'annonceur. Cette approche implique une exploration et nous cherchons donc à nous assurer qu'il n'y a pas d'exploration destructive, et que chaque décision séquentielle de l'annonceur améliore le résultat du ROI au fil du temps. Dans cette approche, nous proposons un nouvel algorithme et une nouvelle implémentation, basés sur le cadre d'optimisation bayésienne pour résoudre notre problème de marketing d'influence budgétisé sous des décisions séquentielles de l'annonceur sur un horizon temporel. En outre, nous proposons une observation empirique pour éviter la malédiction de la dimensionnalité. Nous testons notre modèle statique, l'algorithme et l'heuristique contre plusieurs alternatives de la littérature d'optimisation ainsi que des méthodes de sélection de graines standard et nous validons la performance supérieure de Frank-Wolfe en temps d'exécution et en mémoire, ainsi que sa capacité à s'adapter à des problèmes avec un très grand nombre (millions) d'utilisateurs sociaux. Enfin, nous évaluons notre modèle dynamique sur une trace réelle de données et nous concluons à la faisabilité de notre modèle et au soutien empirique de notre observation formulée
Influencer marketing has become a thriving industry with a global market value expected to reach 15 billion dollars by 2022. The advertising problem that such agencies face is the following: given a monetary budget find a set of appropriate influencers that can create and publish posts of various types (e.g. text, image, video) for the promotion of a target product. The campaign's objective is to maximize across one or multiple online social platforms some impact metric of interest, e.g. number of impressions, sales (ROI), or audience reach. In this thesis, we create original continuous formulations of the budgeted influence marketing problem by two frameworks, a static and a dynamic one, based on the advertiser's knowledge of the impact metric, and the nature of the advertiser's decisions over a time horizon. The static model is formulated as a convex program, and we further propose an efficient iterative algorithm based on the Frank-Wolfe method, that converges to the global optimum and has low computational complexity. We also suggest a simpler near-optimal rule of thumb, which can perform well in many practical scenarios. Due to the nature of the dynamic model we cannot solve any more a Network Utility Maximisation problem since that the ROI is unknown, possibly noisy, continuous and costly to evaluate for the advertiser. This approach involves exploration and so, we seek to ensure that there is no destructive exploration, and that each sequential decision by the advertiser improves the outcome of the ROI over time. In this approach, we propose a new algorithm and a new implementation, based on the Bayesian optimization framework to solve our budgeted influence marketing problem under sequential advertiser's decisions over a time horizon. Besides, we propose an empirical observation to avoid the curse of dimensionality. We test our static model, algorithm and the heuristic against several alternatives from the optimization literature as well as standard seed selection methods and validate the superior performance of Frank-Wolfe in execution time and memory, as well as its capability to scale well for problems with very large number (millions) of social users. Finally, we evaluate our dynamic model on a real Twitter data trace and we conclude the feasibility of our model and empirical support of our formulated observation

APA, Harvard, Vancouver, ISO, and other styles

20

Vu, Dong Quan. "Models and solutions of strategic resource allocation problems : approximate equilibrium and online learning in Blotto games." Electronic Thesis or Diss., Sorbonne université, 2020. https://accesdistant.sorbonne-universite.fr/login?url=https://theses-intra.sorbonne-universite.fr/2020SORUS120.pdf.

Full text

Abstract:

Les problèmes d'allocation des ressources sont définis comme les situations concernant les décisions sur la distribution d’un budget limité afin d’optimiser un objectif. Beaucoup d'entre eux impliquent des interactions entre des décideurs compétitifs ; ils peuvent être bien capturés par des modèles de théorie des jeux. Dans cette thèse, nous choisissons d'étudier les jeux d'allocation de ressources. Nous nous concentrons principalement sur le jeu de Colonel Blotto (CB). Dans le jeu CB, deux joueurs compétitifs, chacun ayant un budget fixe, distribuent simultanément leurs ressources vers n champs de bataille. Chaque joueur évalue chaque champ de bataille avec une certaine valeur. Dans chaque champ de bataille, le joueur qui a l'allocation la plus élevée gagne la valeur correspondante tandis que l'autre obtient zéro. Le gain de chaque joueur est à ses gains cumulés sur tous les champs de bataille. Tout d'abord, nous modélisons plusieurs variantes et extensions du jeu CB comme jeux d'informations complètes à un coup. Notre première contribution est une classe d'équilibres approximatifs dans ces jeux et nous prouvons que l'erreur d'approximation est bien contrôlée. Deuxièmement, nous modélisons les jeux d'allocation de ressources avec des structures combinatoires comme des problèmes d'apprentissage en ligne pour étudier des situations impliquant des jeux séquentiels et des informations incomplètes. Nous établissons une connexion entre ces jeux et les problèmes de chemin le plus court en ligne (OSP). Notre deuxième contribution est un ensemble de nouveaux algorithmes d’OSP sous plusieurs paramètres de feedback qui améliorent des garanties de regret et du temps d'exécution
Resource allocation problems are broadly defined as situations involving decisions on distributing a limited budget of resources in order to optimize an objective. In particular, many of them involve interactions between competitive decision-makers which can be well captured by game-theoretic models. In this thesis, we choose to investigate resource allocation games. We primarily focus on the Colonel Blotto game (CB game). In the CB game, two competitive players, each having a fixed budget of resources, simultaneously distribute their resources toward n battlefields. Each player evaluates each battlefield with a certain value. In each battlefield, the player who has the higher allocation wins and gains the corresponding value while the other loses and gains zero. Each player's payoff is her aggregate gains from all the battlefields. First, we model several prominent variants of the CB game and their extensions as one-shot complete-information games and analyze players' strategic behaviors. Our first main contribution is a class of approximate (Nash) equilibria in these games for which we prove that the approximation error can be well-controlled. Second, we model resource allocation games with combinatorial structures as online learning problems to study situations involving sequential plays and incomplete information. We make a connection between these games and online shortest path problems (OSP). Our second main contribution is a set of novel regret-minimization algorithms for generic instances of OSP under several restricted feedback settings that provide significant improvements in regret guarantees and running time in comparison with existing solutions

APA, Harvard, Vancouver, ISO, and other styles

21

Trippen, Gerhard Wolfgang. "Online exploration and search in graphs /." View abstract or full-text, 2006. http://library.ust.hk/cgi/db/thesis.pl?COMP%202006%20TRIPPE.

Full text

APA, Harvard, Vancouver, ISO, and other styles

22

Harrington, Edward, and edwardharrington@homemail com au. "Aspects of Online Learning." The Australian National University. Research School of Information Sciences and Engineering, 2004. http://thesis.anu.edu.au./public/adt-ANU20060328.160810.

Full text

Abstract:

Online learning algorithms have several key advantages compared to their batch learning algorithm counterparts: they are generally more memory efficient, and computationally mor efficient; they are simpler to implement; and they are able to adapt to changes where the learning model is time varying. Online algorithms because of their simplicity are very appealing to practitioners. his thesis investigates several online learning algorithms and their application. The thesis has an underlying theme of the idea of combining several simple algorithms to give better performance. In this thesis we investigate: combining weights, combining hypothesis, and (sort of) hierarchical combining.¶ Firstly, we propose a new online variant of the Bayes point machine (BPM), called the online Bayes point machine (OBPM). We study the theoretical and empirical performance of the OBPm algorithm. We show that the empirical performance of the OBPM algorithm is comparable with other large margin classifier methods such as the approximately large margin algorithm (ALMA) and methods which maximise the margin explicitly, like the support vector machine (SVM). The OBPM algorithm when used with a parallel architecture offers potential computational savings compared to ALMA. We compare the test error performance of the OBPM algorithm with other online algorithms: the Perceptron, the voted-Perceptron, and Bagging. We demonstrate that the combinationof the voted-Perceptron algorithm and the OBPM algorithm, called voted-OBPM algorithm has better test error performance than the voted-Perceptron and Bagging algorithms. We investigate the use of various online voting methods against the problem of ranking, and the problem of collaborative filtering of instances. We look at the application of online Bagging and OBPM algorithms to the telecommunications problem of channel equalization. We show that both online methods were successful at reducing the effect on the test error of label flipping and additive noise.¶ Secondly, we introduce a new mixture of experts algorithm, the fixed-share hierarchy (FSH) algorithm. The FSH algorithm is able to track the mixture of experts when the switching rate between the best experts may not be constant. We study the theoretical aspects of the FSH and the practical application of it to adaptive equalization. Using simulations we show that the FSH algorithm is able to track the best expert, or mixture of experts, in both the case where the switching rate is constant and the case where the switching rate is time varying.

APA, Harvard, Vancouver, ISO, and other styles

23

Shi, Tian. "Novel Algorithms for Understanding Online Reviews." Diss., Virginia Tech, 2021. http://hdl.handle.net/10919/104998.

Full text

Abstract:

This dissertation focuses on the review understanding problem, which has gained attention from both industry and academia, and has found applications in many downstream tasks, such as recommendation, information retrieval and review summarization. In this dissertation, we aim to develop machine learning and natural language processing tools to understand and learn structured knowledge from unstructured reviews, which can be investigated in three research directions, including understanding review corpora, understanding review documents, and understanding review segments. For the corpus-level review understanding, we have focused on discovering knowledge from corpora that consist of short texts. Since they have limited contextual information, automatically learning topics from them remains a challenging problem. We propose a semantics-assisted non-negative matrix factorization model to deal with this problem. It effectively incorporates the word-context semantic correlations into the model, where the semantic relationships between the words and their contexts are learned from the skip-gram view of a corpus. We conduct extensive sets of experiments on several short text corpora to demonstrate the proposed model can discover meaningful and coherent topics. For document-level review understanding, we have focused on building interpretable and reliable models for the document-level multi-aspect sentiment analysis (DMSA) task, which can help us to not only recover missing aspect-level ratings and analyze sentiment of customers, but also detect aspect and opinion terms from reviews. We conduct three studies in this research direction. In the first study, we collect a new DMSA dataset in the healthcare domain and systematically investigate reviews in this dataset, including a comprehensive statistical analysis and topic modeling to discover aspects. We also propose a multi-task learning framework with self-attention networks to predict sentiment and ratings for given aspects. In the second study, we propose corpus-level and concept-based explanation methods to interpret attention-based deep learning models for text classification, including sentiment classification. The proposed corpus-level explanation approach aims to capture causal relationships between keywords and model predictions via learning importance of keywords for predicted labels across a training corpus based on attention weights. We also propose a concept-based explanation method that can automatically learn higher level concepts and their importance to model predictions. We apply these methods to the classification task and show that they are powerful in extracting semantically meaningful keywords and concepts, and explaining model predictions. In the third study, we propose an interpretable and uncertainty aware multi-task learning framework for DMSA, which can achieve competitive performance while also being able to interpret the predictions made. Based on the corpus-level explanation method, we propose an attention-driven keywords ranking method, which can automatically discover aspect terms and aspect-level opinion terms from a review corpus using the attention weights. In addition, we propose a lecture-audience strategy to estimate model uncertainty in the context of multi-task learning. For the segment-level review understanding, we have focused on the unsupervised aspect detection task, which aims to automatically extract interpretable aspects and identify aspect-specific segments from online reviews. The existing deep learning-based topic models suffer from several problems such as extracting noisy aspects and poorly mapping aspects discovered by models to the aspects of interest. To deal with these problems, we propose a self-supervised contrastive learning framework in order to learn better representations for aspects and review segments. We also introduce a high-resolution selective mapping method to efficiently assign aspects discovered by the model to the aspects of interest. In addition, we propose using a knowledge distillation technique to further improve the aspect detection performance.
Doctor of Philosophy
Nowadays, online reviews are playing an important role in our daily lives. They are also critical to the success of many e-commerce and local businesses because they can help people build trust in brands and businesses, provide insights into products and services, and improve consumers' confidence. As a large number of reviews accumulate every day, a central research problem is to build an artificial intelligence system that can understand and interact with these reviews, and further use them to offer customers better support and services. In order to tackle challenges in these applications, we first have to get an in-depth understanding of online reviews. In this dissertation, we focus on the review understanding problem and develop machine learning and natural language processing tools to understand reviews and learn structured knowledge from unstructured reviews. We have addressed the review understanding problem in three directions, including understanding a collection of reviews, understanding a single review, and understanding a piece of a review segment. In the first direction, we proposed a short-text topic modeling method to extract topics from review corpora that consist of primary complaints of consumers. In the second direction, we focused on building sentiment analysis models to predict the opinions of consumers from their reviews. Our deep learning models can provide good prediction accuracy as well as a human-understandable explanation for the prediction. In the third direction, we develop an aspect detection method to automatically extract sentences that mention certain features consumers are interested in, from reviews, which can help customers efficiently navigate through reviews and help businesses identify the advantages and disadvantages of their products.

APA, Harvard, Vancouver, ISO, and other styles

24

Harrington, Edward Francis. "Aspects of online learning /." View thesis entry in Australian Digital Theses Program, 2004. http://thesis.anu.edu.au/public/adt-ANU20060328.160810/index.html.

Full text

APA, Harvard, Vancouver, ISO, and other styles

25

Hung, Yee-shing Regant. "Scheduling online batching systems." Click to view the E-thesis via HKUTO, 2005. http://sunzi.lib.hku.hk/hkuto/record/B34624016.

Full text

APA, Harvard, Vancouver, ISO, and other styles

26

Mak, Kin-sum. "Energy efficient online deadline scheduling." Click to view the E-thesis via HKUTO, 2007. http://sunzi.lib.hku.hk/HKUTO/record/B39558277.

Full text

APA, Harvard, Vancouver, ISO, and other styles

27

麥健心 and Kin-sum Mak. "Energy efficient online deadline scheduling." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2007. http://hub.hku.hk/bib/B39558277.

Full text

APA, Harvard, Vancouver, ISO, and other styles

28

Li, Rongbin, and 李榕滨. "New competitive algorithms for online job scheduling." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2014. http://hdl.handle.net/10722/197555.

Full text

Abstract:

Job scheduling, which greatly impacts on the system performance, is a fundamental problem in computer science. In this thesis, we study three kinds of scheduling problems, that is, deadline scheduling, due date scheduling, and flow time scheduling. Traditionally, the major concern for scheduling problems is the system performance, i.e. the “Quality of Service" (QoS). Different scheduling problems use different QoS measurements. For deadline scheduling, the most common QoS to optimize is the throughput; for due date scheduling, it is the total quoted lead time; and for flow time scheduling, it is the total (weighted) flow time. Recently, energy efficiency is becoming more and more important. Many modern processors adopt technologies like dynamic speed scaling and sleep management to reduce energy usage. Much work is done on energy efficient scheduling. In this thesis, we study this topic for all three kinds of scheduling mentioned above. Meanwhile, we also revisit the traditional flow time scheduling problem to optimize the QoS. However, we consider the problem in a more realistic model that makes the problem much more challenging. Below is the summary of the problems studied in the thesis. First, we consider the tradeoff between energy and throughput for deadline scheduling. Specifically, each job is associated with a value (or importance) and a deadline. A scheduling algorithm is allowed to discard some of the jobs, and the objective is to minimize total energy usage plus total value of discarded jobs. When processor's maximum speed is unbounded, we propose an O(1)-competitive algorithm. When processor's maximum speed is bounded, we show a strong lower bound and give an algorithm with a competitive ratio close to that lower bound. Second, we study energy efficient due date scheduling. Jobs arrive online with different sizes and weights. An algorithm needs to assign a due date to each job once it arrives, and complete the job by the due date. The quoted lead time of a job equals its due date minus its arrival time, multiplied by its weight. We propose a competitive algorithm for minimizing the sum of the total quoted lead time and energy usage. Next, we consider flow time scheduling with power management on multiple machines. Jobs with arbitrary sizes and weights arrive online. Each machine consumes different amount of energy when processing a job, idling or sleeping. A scheduler has to maintain a good balance of the states of the machines to avoid energy wastage and, meanwhile, guarantee high QoS. Our result is an O(1)-competitive algorithm to minimize total weighted flow time plus energy usage. Finally, we consider the traditional preemptive scheduling to minimize total flow time. Previous theoretical results often assume preemption is free, which is not true for most systems. We investigate the complexity of the problem when a processor has to perform a certain amount of overhead before it resumes the execution of a job preempted before. We first show an Ω(n^(1/4)) lower bound, and then, propose a (1+ε)-speed (1+ 1/ε )-competitive algorithm in resource augmentation model.
published_or_final_version
Computer Science
Doctoral
Doctor of Philosophy

APA, Harvard, Vancouver, ISO, and other styles

29

ALBUQUERQUE, LUIZ FERNANDO FERNANDES DE. "ONLINE ALGORITHMS ANALYSIS FOR SPONSORED LINKS SELECTION." PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO, 2009. http://www.maxwell.vrac.puc-rio.br/Busca_etds.php?strSecao=resultado&nrSeq=16088@1.

Full text

Abstract:

PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO
Links patrocinados são aqueles que aparecem em destaque nos resultados de pesquisas em máquinas de busca na Internet e são grande fonte de receita para seus provedores. Para os anunciantes, que fazem ofertas por palavras-chave para aparecerem em destaque nas consultas dos usuários, são uma oportunidade de divulgação da marca, conquista e manutenção de clientes. Um dos desafios das máquinas de busca neste modelo de negócio é selecionar os anunciantes que serão exibidos a cada consulta de modo a maximizar sua receita em determinado período. Este é um problema tipicamente online, onde a cada consulta é tomada uma decisão sem o conhecimento prévio das próximas consultas. Após uma decisão ser tomada, esta não pode mais ser alterada. Nesta dissertação avaliamos experimentalmente algoritmos propostos na literatura para solução deste problema, comparando-os à solução ótima offline, em simulações com dados sintéticos. Supondo que o conjunto das consultas diárias obedeça a uma determinada distribuição, propomos dois algoritmos baseados em informações estocásticas que são avaliados nos mesmos cenários que os outros algoritmos.
Sponsored links are those that appear highlighted at Internet search engine results. They are responsible for a large amount of their providers’ revenue. To advertisers, that place bids for keywords in large auctions at Internet, these links are the opportunity of brand exposing and achieving more clients. To search engine companies, one of the main challenges in this business model is selecting which advertisers should be allocated to each new query to maximize their total revenue in the end of the day. This is a typical online problem, where for each query is taken a decision without previous knowledge of future queries. Once the decision is taken, it can not be modified anymore. In this work, using synthetically generated data, we do experimental evaluation of three algorithms proposed in the literature for this problem and compare their results with the optimal offline solution. Considering that daily query set obeys some well known distribution, we propose two algorithms based on stochastic information, those are evaluated in the same scenarios of the others.

APA, Harvard, Vancouver, ISO, and other styles

30

Pasteris, S. U. "Efficient algorithms for online learning over graphs." Thesis, University College London (University of London), 2016. http://discovery.ucl.ac.uk/1516210/.

Full text

Abstract:

In this thesis we consider the problem of online learning with labelled graphs, in particular designing algorithms that can perform this problem quickly and with low memory requirements. We consider the tasks of Classification (in which we are asked to predict the labels of vertices) and Similarity Prediction (in which we are asked to predict whether two given vertices have the same label). The first half of the thesis considers non- probabilistic online learning, where there is no probability distribution on the labelling and we bound the number of mistakes of an algorithm by a function of the labelling's complexity (i.e. its "naturalness"), often the cut- size. The second half of the thesis considers probabilistic machine learning in which we have a known probability distribution on the labelling. Before considering probabilistic online learning we first analyse the junction tree algorithm, on which we base our online algorithms, and design a new ver- sion of it, superior to the otherwise current state of the art. Explicitly, the novel contributions of this thesis are as follows: • A new algorithm for online prediction of the labelling of a graph which has better performance than previous algorithms on certain graph and labelling families. • Two algorithms for online similarity prediction on a graph (a novel problem solved in this thesis). One performs very well whilst the other not so well but which runs exponentially faster. • A new (better than before, in terms of time and space complexity) state of the art junction tree algorithm, as well as an application of it to the problem of online learning in an Ising model. • An algorithm that, in linear time, finds the optimal junction tree for online inference in tree-structured Ising models, the resulting online junction tree algorithm being far superior to the previous state of the art. All claims in this thesis are supported by mathematical proofs.

APA, Harvard, Vancouver, ISO, and other styles

31

Bonifaci, Vincenzo. "Models and algorithms for online server routing." Doctoral thesis, La Sapienza, 2007. http://hdl.handle.net/11573/917056.

Full text

APA, Harvard, Vancouver, ISO, and other styles

32

CESARI, TOMMASO RENATO. "ALGORITHMS, LEARNING, AND OPTIMIZATION." Doctoral thesis, Università degli Studi di Milano, 2020. http://hdl.handle.net/2434/699354.

Full text

Abstract:

This thesis covers some algorithmic aspects of online machine learning and optimization. In Chapter 1 we design algorithms with state-of-the-art regret guarantees for the problem dynamic pricing. In Chapter 2 we move on to an asynchronous online learning setting in which only some of the agents in the network are active at each time step. We show that when information is shared among neighbors, knowledge about the graph structure might have a significantly different impact on learning rates depending on how agents are activated. In Chapter 3 we investigate the online problem of multivariate non-concave maximization under weak assumptions on the regularity of the objective function. In Chapter 4 we introduce a new performance measure and design an efficient algorithm to learn optimal policies in repeated A/B testing.

APA, Harvard, Vancouver, ISO, and other styles

33

Zhu, Jianqiao, and 朱剑桥. "New results on online job scheduling." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2013. http://hub.hku.hk/bib/B50662351.

Full text

Abstract:

This thesis presents several new results on online job scheduling. Job scheduling is a basic requirement of many practical computer systems, and the scheduling behavior directly affects a system’s performance. In theoretical aspect, scheduling scenarios are abstracted into scheduling models, which are studied mathematically. In this thesis, we look into a variety of scheduling models which are under active research. We incorporate these models and organize them into generalized pictures. We first study non-clairvoyant scheduling to minimize weighted flow time on two different multi-processor models. In the first model, processors are all identical and jobs can possibly be speeded up by running on several processors in parallel. Under the non-clairvoyant model, the online scheduler has no information about the actual job size and degree of speed-up due to parallelism during the execution of a job, yet it has to determine dynamically when and how many processors to run the jobs. The literature contains several O(1)-competitive algorithms for this problem under the unit-weight multi-processor setting [13, 14] as well as the weighted single-processor setting [5]. This thesis shows the first O(1)-competitive algorithm for weighted flow time in the multi-processor setting. In the second model, we consider processors with different functionalities and only processors of the same functionality can work on the same job in parallel to achieve some degree of speed up. Here a job is modeled as a sequence of non-clairvoyant demands of different functionalities. This model is derived naturally from the classical job shop scheduling; but as far as we know, there is no previous work on scheduling to minimize flow time under this multi-processor model. In this thesis we take a first step to study non-clairvoyant scheduling on this multi-processor model. Motivated by the literature on 2-machine job shop scheduling, we focus on the special case when processors are divided into two types of functionalities, and we show a non-clairvoyant algorithm that is O(1)-competitive for weighted flow time. This thesis also initiates the study of online scheduling with rejection penalty in the non-clairvoyant setting. In the rejection penalty model, jobs can be rejected with a penalty, and the user cost of a job is defined as the weighted flow time of the job plus the penalty if it is rejected before completion. Previous work on minimizing the total user cost focused on the clairvoyant single-processor setting [3, 10] and has produced O(1)-competitive online algorithm for jobs with arbitrary weights and penalties. This thesis gives the first non-clairvoyant algorithms that are O(1)-competitive for minimizing the total user cost on a single processor and multi-processors, when using slightly faster (i.e., (1 + ∈)-speed for any ∈> 0) processors. Note that if no extra speed is allowed, no online algorithm can be O(1)-competitive even for minimizing (unweighted) flow time alone. The above results assume a processor running at a fixed speed. This thesis shows more interesting results on extending the above study to the dynamic speed scaling model, where the processor can vary the speed dynamically and the rate of energy consumption is an arbitrary increasing function of speed. A scheduling algorithm has to decide job rejection and determine the order and speed of job execution. It is interesting to study the tradeoff between the above-mentioned user cost and energy. This thesis gives two O(1)-competitive non-clairvoyant algorithms for minimizing the user cost plus energy on a single processor and multi-processors, respectively.
published_or_final_version
Computer Science
Master
Master of Philosophy

APA, Harvard, Vancouver, ISO, and other styles

34

Hung, Yee-shing Regant, and 洪宜成. "Scheduling online batching systems." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2005. http://hub.hku.hk/bib/B34624016.

Full text

APA, Harvard, Vancouver, ISO, and other styles

35

Fernández, Pérez Iñaki. "Distributed Embodied Evolutionary Adaptation of Behaviors in Swarms of Robotic Agents." Thesis, Université de Lorraine, 2017. http://www.theses.fr/2017LORR0300/document.

Full text

Abstract:

Les essaims de robots sont des systèmes composés d’un grand nombre de robots relativement simples. Du fait du grand nombre d’unités, ces systèmes ont de bonnes propriétés de robustesse et de passage à l’échelle. Néanmoins, il reste en général difficile de concevoir manuellement des contrôleurs pour les essaims de robots, à cause de la grande complexité des interactions inter-robot. Par conséquent, les approches automatisées pour l’apprentissage de comportements d’essaims de robots constituent une alternative attrayante. Dans cette thèse, nous étudions l’adaptation de comportements d’essaim de robots avec des méthodes de Embodied Evolutionary Robotics (EER) distribuée. Ainsi, nous fournissons trois contributions principales : (1) Nous étudions l’influence de la pression à la sélection dirigée vers une tâche dans un essaim d’agents robotiques qui utilisent une approche d’EER distribuée. Nous évaluons l’impact de différents opérateurs de sélection dans un algorithme d’EER distribuée pour un essaim de robots. Nos résultats montrent que le plus forte la pression à la sélection est, les meilleures performances sont atteintes lorsque les robots doivent s’adapter à des tâches particulières. (2) Nous étudions l’évolution de comportements collaboratifs pour une tâche de récolte d’objets dans un essaim d’agents robotiques qui utilisent une approche d’EER distribuée. Nous réalisons un ensemble d’expériences où un essaim de robots s’adapte à une tâche collaborative avec un algorithme d’EER distribuée. Nos résultats montrent que l’essaim s’adapte à résoudre la tâche, et nous identifions des limitations concernant le choix d’action. (3) Nous proposons et validons expérimentalement un mécanisme complètement distribué pour adapter la structure des neurocontrôleurs des robots dans un essaim qui utilise une approche d’EER distribuée, ce qui permettrait aux neurocontrôleurs d’augmenter leur expressivité. Nos expériences montrent que notre mécanisme, qui est complètement décentralisé, fournit des résultats similaires à un mécanisme qui dépend d’une information globale
Robot swarms are systems composed of a large number of rather simple robots. Due to the large number of units, these systems, have good properties concerning robustness and scalability, among others. However, it remains generally difficult to design controllers for such robotic systems, particularly due to the complexity of inter-robot interactions. Consequently, automatic approaches to synthesize behavior in robot swarms are a compelling alternative. In this thesis, we focus on online behavior adaptation in a swarm of robots using distributed Embodied Evolutionary Robotics (EER) methods. To this end, we provide three main contributions: (1) We investigate the influence of task-driven selection pressure in a swarm of robotic agents using a distributed EER approach. We evaluate the impact of a range of selection pressure strength on the performance of a distributed EER algorithm. The results show that the stronger the task-driven selection pressure, the better the performances obtained when addressing given tasks. (2) We investigate the evolution of collaborative behaviors in a swarm of robotic agents using a distributed EER approach. We perform a set of experiments for a swarm of robots to adapt to a collaborative item collection task that cannot be solved by a single robot. Our results show that the swarm learns to collaborate to solve the task using a distributed approach, and we identify some inefficiencies regarding learning to choose actions. (3) We propose and experimentally validate a completely distributed mechanism that allows to learn the structure and parameters of the robot neurocontrollers in a swarm using a distributed EER approach, which allows for the robot controllers to augment their expressivity. Our experiments show that our fully-decentralized mechanism leads to similar results as a mechanism that depends on global information

APA, Harvard, Vancouver, ISO, and other styles

36

Cunningham, James. "Efficient, Parameter-Free Online Clustering." The Ohio State University, 2020. http://rave.ohiolink.edu/etdc/view?acc_num=osu1606762403895603.

Full text

APA, Harvard, Vancouver, ISO, and other styles

37

Kamphans, Thomas. "Models and algorithms for online exploration and search." [S.l.] : [s.n.], 2006. http://deposit.ddb.de/cgi-bin/dokserv?idn=980408121.

Full text

APA, Harvard, Vancouver, ISO, and other styles

38

Birks, Martin David. "Online algorithms for temperature aware job scheduling problems." Thesis, University of Leicester, 2012. http://hdl.handle.net/2381/27686.

Full text

Abstract:

Temperature is an important consideration when designing microprocessors. When exposed to high temperatures component reliability can be reduced, while some components completely fail over certain temperatures. We consider the design and analysis of online algorithms; in particular algorithms that use knowledge of the amount of heat a job will generate. We consider algorithms with two main objectives. The first is maximising job throughput. We show upper and lower bounds for the case where jobs are unit length, both when jobs are weighted and unweighted. Many of these bounds are matching for all cooling factors in the single and multiple machine case. We extend this to consider the single machine case where jobs have longer than unit length. When all jobs are equal length we show matching bounds for the case without preemption. We also show that both models of pre-emption enable at most a slight reduction in the competitive ratio of algorithms. We then consider when jobs have variable lengths. We analyse both the models of unweighted jobs and the jobs with weights proportional to their length. We show bounds that match within constant factors, in the non-preemptive and both preemptive models. The second objective we consider is minimising flow time. We consider the objective of minimising the total flow time of a schedule. We show NP-hardness and inapproximability results for the offline case, as well as giving an approximation algorithm for the case where all release times are equal. For the online case we give some negative results for the case where maximum job heats are bounded. We also give some results for a resource augmentation model that include a 1-competitive algorithm when the extra power for the online algorithm is high enough. Finally we consider the objective of minimising the maximum flow time of any job in a schedule.

APA, Harvard, Vancouver, ISO, and other styles

39

Zadimoghaddam, Morteza. "Online allocation algorithms with applications in computational advertising." Thesis, Massachusetts Institute of Technology, 2014. http://hdl.handle.net/1721.1/87940.

Full text

Abstract:

Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2014.
Cataloged from PDF version of thesis.
Includes bibliographical references (pages 99-107).
Over the last few decades, a wide variety of allocation markets emerged from the Internet and introduced interesting algorithmic challenges, e.g., ad auctions, online dating markets, matching skilled workers to jobs, etc. I focus on the use of allocation algorithms in computational advertising as it is the quintessential application of my research. I will also touch on the classic secretary problem with submodular utility functions, and show that how it is related to advertiser's optimization problem in computational advertising applications. In all these practical situations, we should focus on solving the allocation problems in an online setting since the input is being revealed during the course of the algorithm, and at the same time we should make irrevocable decisions. We can formalize these types of computational advertising problems as follows. We are given a set of online items, arriving one by one, and a set of advertisers where each advertiser specifies how much she wants to pay for each of the online items. The goal is to allocate online items to advertisers to maximize some objective function like the total revenue, or the total quality of the allocation. There are two main classes of extensively studied problems in this context: budgeted allocation (a.k.a. the adwords problem) and display ad problems. Each advertiser is constrained by an overall budget limit, the maximum total amount she can pay in the first class, and by some positive integer capacity, the maximum number of online items we can assign to her in the second class.
by Morteza Zadimoghaddam.
Ph. D.

APA, Harvard, Vancouver, ISO, and other styles

40

Packer, Heather S. "Evolving ontologies with online learning and forgetting algorithms." Thesis, University of Southampton, 2011. https://eprints.soton.ac.uk/194923/.

Full text

Abstract:

Agents that require vocabularies to complete tasks can be limited by static vocabularies which cannot evolve to meet unforeseen domain tasks, or reflect its changing needs or environment. However, agents can benefit from using evolution algorithms to evolve their vocabularies, namely the ability to support new domain tasks. While an agent can capitalise on being able support more domain tasks, using existing techniques can hinder them because they do not consider the associated costs involved with evolving an agent's ontology. With this motivation, we explore the area of ontology evolution in agent systems, and focus on the reduction of the costs associated with an evolving ontology. In more detail, we consider how an agent can reduce the costs of evolving an ontology, these include costs associated with: the acquisition of new concepts; processing new concepts; the increased memory usage from storing new concepts; and the removal of unnecessary concepts. Previous work reported in the literature has largely failed to analyse these costs in the context of evolving an agent's ontology. Against this background, we investigate and develop algorithms to enable agents to evolve their ontologies. More specifically, we present three online evolution algorithms that enable agents to: i) augment domain related concepts, ii) use prediction to select concepts to learn, and iii) prune unnecessary concepts from their ontology, with the aim to reduce the costs associated with the acquisition, processing and storage of acquired concepts. In order to evaluate our evolution algorithms, we developed an agent framework which enables agents to use these algorithms and measure an agent's performance. Finally, our empirical evaluation shows that our algorithms are successful in reducing the costs associated with evolving an agent's ontology.

APA, Harvard, Vancouver, ISO, and other styles

41

Moon, Kyung Seob. "Consistency Maintenance Algorithms for Multiplayer Online Digital Games." Thesis, Griffith University, 2007. http://hdl.handle.net/10072/367081.

Full text

Abstract:

Multiplayer Online Digital Games (MODIGs) are gaining in popularity because of the strategic sophistication added when games are played against other humans, as opposed to computer artificial intelligence (AI) opponents. However, the actualisation of multiplayer games is not easy, due to their complexity. Multiplayer games are the combined applications of various areas, such as networking, graphics, AI, sound, and process optimisation. Among them, problems related to networking -- such as limitations in data transfer rate, latency, and jitter -- are the most difficult to resolve. Network latency cannot be avoided completely and introduces various problems such as inconsistency of player status, recognisable responsiveness, and irregular network lag. Generally, the network architectures of MODIGs can be categorized into three groups: Client-Server (C/S), Peer-to-Peer (P2P), and hybrid. In general, MODIG designers prefer the C/S network architecture to the P2P system. The main reason for this is that the C/S model enjoys certain advantages, such as simplicity of consistency maintenance, improved security, efficient authentification, and ease of billing system management. However, the C/S architecture can cause network latency and often servers do become network bottlenecks. To solve this problem, server clustering methods are used, but these solutions may not be cost effective. This is why a number of games use the P2P network architecture, but in this structure the total number of players in any one game session is often limited, because of the network’s bandwidth constraints. In addition, the consistency maintenance issue becomes critical within this architecture. There are two main approaches for maintaining consistency in MODIGs: conservative and optimistic. The former approach involves a send-and-wait philosophy, requiring acknowledgement frames and resulting in packet transfer delay, such that players may experience network latency. In the latter approach, the processes do not wait for other players' packets and advance to their own frames, thus no network latency occurs. However, when there is inconsistency between players, the processes must roll back to correct mis-ordered operations due to packet transfer delay. These can cause irritation and confusion to players, and thus the quality of game deteriorates. Overall, the optimistic approaches may not be suitable for network games. To alleviate network latency and reduce bandwidth requirements in conservative consistency maintenance algorithms and the P2P-based approaches, a new system is proposed and designed. To reduce network latency, a conservative consistency maintenance algorithm named Locked Bucket Synchronisation (LBS) is proposed to mask latency and maintain perfect consistency among players. In addition, a distributed network architecture is adopted and a tree-based P2P system is proposed, to remove additional packet transfer delays between server and client. To reduce network latency caused by packet drop and delay, a smart transmission scheme (STS) is proposed. To alleviate the bandwidth problem, a packet aggregation method is introduced. These approaches are thoroughly examined and analysed. To evaluate the efficiency of the proposed system, a network simulator, COMP2P, and a real network game, Duel-X, are implemented. The efficiency of the proposed consistency algorithm, LBS is compared with that of other approaches such as Lockstep (LS) and Frequent State Regeneration (FSR). The system architectures of COMP2P and Duel-X as well as the results of experiments are fully documented. The experimental results from COMP2P show that the proposed LBS algorithm outperforms the LS algorithm under all tested circumstances, in terms of game execution speed. The LBS algorithm with the tree-based P2P system achieves almost optimal frame rate under the condition of a 10% packet drop rate, while the LS algorithm with the tree-base P2P system performs at approximately 40% of optimal frame rate. The efficiency of the Smart Transmission Scheme (STS) with the LBS algorithm is compared with the Blind Transmission Scheme (BTS) and the experimental results indicate that the BTS increases the bandwidth requirement of players by 100% while the STS raises by only 10% the optimal value of the bandwidth requirement without degrading game execution speed significantly. Finally, the proposed packet aggregation method together with the LBS algorithm reduce by 50% the bandwidth requirement of players, without lowering game execution speed, when compared with the case of using the LBS algorithm only. To verify and validate the efficiency of the LBS algorithm, various experiments are performed on Duel-X. The experimental results show that the LBS algorithm masks network latency without harming consistency between players. When the LBS algorithm is adopted, the rate of frame interval approaches the optimal values that can be achieved under the FSR algorithm. This implies that the LBS algorithm improves the playability of MODIGs without degrading consistency between players. The overall experimental results show that actualisation of reliable and robust MODIGs is achievable with a combination of P2P-based architecture and conservative consistency maintenance algorithms.
Thesis (PhD Doctorate)
Doctor of Philosophy (PhD)
School of Information and Communication Technology
Faculty of Engineering and Information Technology
Full Text

APA, Harvard, Vancouver, ISO, and other styles

42

Chowuraya, Tawanda. "Online content clustering using variant K-Means Algorithms." Thesis, Cape Peninsula University of Technology, 2019. http://hdl.handle.net/20.500.11838/3089.

Full text

Abstract:

Thesis (MTech)--Cape Peninsula University of Technology, 2019
We live at a time when so much information is created. Unfortunately, much of the information is redundant. There is a huge amount of online information in the form of news articles that discuss similar stories. The number of articles is projected to grow. The growth makes it difficult for a person to process all that information in order to update themselves on a subject matter. There is an overwhelming amount of similar information on the internet. There is need for a solution that can organize this similar information into specific themes. The solution is a branch of Artificial intelligence (AI) called machine learning (ML) using clustering algorithms. This refers to clustering groups of information that is similar into containers. When the information is clustered people can be presented with information on their subject of interest, grouped together. The information in a group can be further processed into a summary. This research focuses on unsupervised learning. Literature has it that K-Means is one of the most widely used unsupervised clustering algorithm. K-Means is easy to learn, easy to implement and is also efficient. However, there is a horde of variations of K-Means. The research seeks to find a variant of K-Means that can be used with an acceptable performance, to cluster duplicate or similar news articles into correct semantic groups. The research is an experiment. News articles were collected from the internet using gocrawler. gocrawler is a program that takes Universal Resource Locators (URLs) as an argument and collects a story from a website pointed to by the URL. The URLs are read from a repository. The stories come riddled with adverts and images from the web page. This is referred to as a dirty text. The dirty text is sanitized. Sanitization is basically cleaning the collected news articles. This includes removing adverts and images from the web page. The clean text is stored in a repository, it is the input for the algorithm. The other input is the K value. All K-Means based variants take K value that defines the number of clusters to be produced. The stories are manually classified and labelled. The labelling is done to check the accuracy of machine clustering. Each story is labelled with a class to which it belongs. The data collection process itself was not unsupervised but the algorithms used to cluster are totally unsupervised. A total of 45 stories were collected and 9 manual clusters were identified. Under each manual cluster there are sub clusters of stories talking about one specific event. The performance of all the variants is compared to see the one with the best clustering results. Performance was checked by comparing the manual classification and the clustering results from the algorithm. Each K-Means variant is run on the same set of settings and same data set, that is 45 stories. The settings used are, • Dimensionality of the feature vectors, • Window size, • Maximum distance between the current and predicted word in a sentence, • Minimum word frequency, • Specified range of words to ignore, • Number of threads to train the model. • The training algorithm either distributed memory (PV-DM) or distributed bag of words (PV-DBOW), • The initial learning rate. The learning rate decreases to minimum alpha as training progresses, • Number of iterations per cycle, • Final learning rate, • Number of clusters to form, • The number of times the algorithm will be run, • The method used for initialization. The results obtained show that K-Means can perform better than K-Modes. The results are tabulated and presented in graphs in chapter six. Clustering can be improved by incorporating Named Entity (NER) recognition into the K-Means algorithms. Results can also be improved by implementing multi-stage clustering technique. Where initial clustering is done then you take the cluster group and further cluster it to achieve finer clustering results.

APA, Harvard, Vancouver, ISO, and other styles

43

San, Felice Mário César 1985. "Online facility location and Steiner problems = Problemas online de localização de instalações e de Steiner." [s.n.], 2015. http://repositorio.unicamp.br/jspui/handle/REPOSIP/275552.

Full text

Abstract:

Orientador: Orlando Lee
Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação
Made available in DSpace on 2018-08-27T12:18:11Z (GMT). No. of bitstreams: 1 SanFelice_MarioCesar_D.pdf: 1457706 bytes, checksum: 4813f4ed44c52462656d56537d73d5dc (MD5) Previous issue date: 2015
Resumo: Nesta tese estudamos problemas online das famílias de localização de instalações e de Steiner, através da abordagem de análise competitiva. O objetivo nestes problemas é construir uma rede de custo mínimo para atender a uma determinada demanda. Nós apresentamos resultados conhecidos para o problema Online da Localização de Instalações (OFL), o problema Online da Árvore de Steiner (OST) e o problema Online Single-Source Rent-or-Buy (OSRoB). O OFL consiste em atender a um conjunto de clientes, através da abertura de algumas instalações e da conexão de cada cliente com uma instalação aberta. O OST tem por objetivo conectar um conjunto de terminais utilizando uma árvore, que pode conter vértices não terminais, chamados vértices de Steiner. O OSRoB é uma versão rent-or-buy do OST, onde todos os terminais devem ser conectados a um nó especial chamado raíz. Os algoritmos e técnicas que apresentamos para estes problemas são importantes no desenvolvimento dos nossos algoritmos para os problemas que consideramos. Apresentamos novos resultados para o problema Online da Localização de Instalações com Coleta de Prêmios (OPFL), o problema Online da Árvore Estrela de Steiner (OSTS), e o problema Online da Localização de Instalações Conectadas (OCFL). O OPFL é uma generalização do OFL, em que alguns clientes podem ficar desconectados mediante o pagamento de penalidades. O OSTS é uma variante do OST, em que os vértices possuem custos não negativos. O OCFL é uma combinação do OFL e do OST, em que um conjunto de clientes precisa ser atendido através da abertura de algumas instalações, da conexão de cada cliente com uma instalação aberta, e da construção de uma árvore, mais custosa, que conecta as instalações abertas
Abstract: In this thesis we study online problems from the facility location and Steiner families, through the point of view of competitive analysis. The goal in these problems is to build a minimum cost network to attend a certain demand. We present known results for the Online Facility Location problem (OFL), the Online Steiner Tree problem (OST) and the Online Single-Source Rent-or-Buy problem (OSRoB). The OFL consists of serving a set of clients by opening some facilities and by connecting each client to a facility. The OST aims to connect a set of terminals in order to create a tree network, that may contain nonterminals, called Steiner nodes. The OSRoB is a rent-or-buy version of the OST, in which all terminals must be connected to a special node called root. The algorithms and techniques that we present for these problems play an important role in the design of our algorithms for the problems we consider. We present new results for the Online Prize-Collecting Facility Location problem (OPFL), the Online Steiner Tree Star problem (OSTS), and the Online Connected Facility Location problem (OCFL). The OPFL is a generalization of the OFL, in which some clients may be left unconnected by paying a penalty. The OSTS is a variant of the OST, in which the nodes have non-negative costs. The OCFL is a combination of the OFL and the OST, in which a set of clients needs to be served by opening some facilities, by connecting each client to a facility, and by creating a more expensive tree network that connects the open facilities
Doutorado
Ciência da Computação
Doutor em Ciência da Computação

APA, Harvard, Vancouver, ISO, and other styles

44

Zhang, Lele. "On-line scheduling with constraints /." Connect to thesis, 2009. http://repository.unimelb.edu.au/10187/3538.

Full text

APA, Harvard, Vancouver, ISO, and other styles

45

Holmgren, Faghihi Josef, and Paul Gorgis. "Time efficiency and mistake rates for online learning algorithms : A comparison between Online Gradient Descent and Second Order Perceptron algorithm and their performance on two different data sets." Thesis, KTH, Skolan för elektroteknik och datavetenskap (EECS), 2019. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-260087.

Full text

Abstract:

This dissertation investigates the differences between two different online learning algorithms: Online Gradient Descent (OGD) and Second-Order Perceptron (SOP) algorithm, and how well they perform on different data sets in terms of mistake rate, time cost and number of updates. By studying different online learning algorithms and how they perform in different environments will help understand and develop new strategies to handle further online learning tasks. The study includes two different data sets, Pima Indians Diabetes and Mushroom, together with the LIBOL library for testing. The results in this dissertation show that Online Gradient Descent performs overall better concerning the tested data sets. In the first data set, Online Gradient Descent recorded a notably lower mistake rate. For the second data set, although it recorded a slightly higher mistake rate, the algorithm was remarkably more time efficient compared to Second-Order Perceptron. Future work would include a wider range of testing with more, and different, data sets as well as other relative algorithms. This will lead to better result and higher credibility.
Den här avhandlingen undersöker skillnaden mellan två olika “online learning”-algoritmer: Online Gradient Descent och Second-Order Perceptron, och hur de presterar på olika datasets med fokus på andelen felklassificeringar, tidseffektivitet och antalet uppdateringar. Genom att studera olika “online learning”-algoritmer och hur de fungerar i olika miljöer, kommer det hjälpa till att förstå och utveckla nya strategier för att hantera vidare “online learning”-problem. Studien inkluderar två olika dataset, Pima Indians Diabetes och Mushroom, och använder biblioteket LIBOL för testning. Resultatet i denna avhandling visar att Online Gradient Descent presterar bättre överlag på de testade dataseten. För det första datasetet visade Online Gradient Descent ett betydligt lägre andel felklassificeringar. För det andra datasetet visade OGD lite högre andel felklassificeringar, men samtidigt var algoritmen anmärkningsvärt mer tidseffektiv i jämförelse med Second-Order Perceptron. Framtida studier inkluderar en bredare testning med mer, och olika, datasets och andra relaterade algoritmer. Det leder till bättre resultat och höjer trovärdigheten.

APA, Harvard, Vancouver, ISO, and other styles

46

Murphy, Nicholas John. "An online learning algorithm for technical trading." Master's thesis, Faculty of Science, 2019. http://hdl.handle.net/11427/31048.

Full text

Abstract:

We use an adversarial expert based online learning algorithm to learn the optimal parameters required to maximise wealth trading zero-cost portfolio strategies. The learning algorithm is used to determine the relative population dynamics of technical trading strategies that can survive historical back-testing as well as form an overall aggregated portfolio trading strategy from the set of underlying trading strategies implemented on daily and intraday Johannesburg Stock Exchange data. The resulting population time-series are investigated using unsupervised learning for dimensionality reduction and visualisation. A key contribution is that the overall aggregated trading strategies are tested for statistical arbitrage using a novel hypothesis test proposed by Jarrow et al. [31] on both daily sampled and intraday time-scales. The (low frequency) daily sampled strategies fail the arbitrage tests after costs, while the (high frequency) intraday sampled strategies are not falsified as statistical arbitrages after costs. The estimates of trading strategy success, cost of trading and slippage are considered along with an offline benchmark portfolio algorithm for performance comparison. In addition, the algorithms generalisation error is analysed by recovering a probability of back-test overfitting estimate using a nonparametric procedure introduced by Bailey et al. [19]. The work aims to explore and better understand the interplay between different technical trading strategies from a data-informed perspective.

APA, Harvard, Vancouver, ISO, and other styles

47

Bellas, Anastasios. "Détection d'anomalies à la volée dans des signaux vibratoires." Thesis, Paris 1, 2014. http://www.theses.fr/2014PA010020.

Full text

Abstract:

Le thème principal de cette thèse est d’étudier la détection d’anomalies dans des flux de données de grande dimension avec une application spécifique au Health Monitoring des moteurs d’avion. Dans ce travail, on considère que le problème de la détection d’anomalies est un problème d’apprentissage non supervisée. Les données modernes, notamment celles issues de la surveillance des systèmes industriels sont souvent des flux d’observations de grande dimension, puisque plusieurs mesures sont prises à de hautes fréquences et à un horizon de temps qui peut être infini. De plus, les données peuvent contenir des anomalies (pannes) du système surveillé. La plupart des algorithmes existants ne peuvent pas traiter des données qui ont ces caractéristiques. Nous introduisons d’abord un algorithme de clustering probabiliste offline dans des sous-espaces pour des données de grande dimension qui repose sur l’algorithme d’espérance-maximisation (EM) et qui est, en plus, robuste aux anomalies grâce à la technique du trimming. Ensuite, nous nous intéressons à la question du clustering probabiliste online de flux de données de grande dimension en développant l’inférence online du modèle de mélange d’analyse en composantes principales probabiliste. Pour les deux méthodes proposées, nous montrons leur efficacité sur des données simulées et réelles, issues par exemple des moteurs d’avion. Enfin, nous développons une application intégrée pour le Health Monitoring des moteurs d’avion dans le but de détecter des anomalies de façon dynamique. Le système proposé introduit des techniques originales de détection et de visualisation d’anomalies reposant sur les cartes auto-organisatrices. Des résultats de détection sont présentés et la question de l’identification des anomalies est aussi discutée
The subject of this Thesis is to study anomaly detection in high-dimensional data streams with a specific application to aircraft engine Health Monitoring. In this work, we consider the problem of anomaly detection as an unsupervised learning problem. Modern data, especially those is-sued from industrial systems, are often streams of high-dimensional data samples, since multiple measurements can be taken at a high frequency and at a possibly infinite time horizon. More-over, data can contain anomalies (malfunctions, failures) of the system being monitored. Most existing unsupervised learning methods cannot handle data which possess these features. We first introduce an offline subspace clustering algorithm for high-dimensional data based on the expectation-maximization (EM) algorithm, which is also robust to anomalies through the use of the trimming technique. We then address the problem of online clustering of high-dimensional data streams by developing an online inference algorithm for the popular mixture of probabilistic principal component analyzers (MPPCA) model. We show the efficiency of both methods on synthetic and real datasets, including aircraft engine data with anomalies. Finally, we develop a comprehensive application for the aircraft engine Health Monitoring domain, which aims at detecting anomalies in aircraft engine data in a dynamic manner and introduces novel anomaly detection visualization techniques based on Self-Organizing Maps. Detection results are presented and anomaly identification is also discussed

APA, Harvard, Vancouver, ISO, and other styles

48

Brégère, Margaux. "Stochastic bandit algorithms for demand side management Simulating Tariff Impact in Electrical Energy Consumption Profiles with Conditional Variational Autoencoders Online Hierarchical Forecasting for Power Consumption Data Target Tracking for Contextual Bandits : Application to Demand Side Management." Thesis, université Paris-Saclay, 2020. http://www.theses.fr/2020UPASM022.

Full text

Abstract:

L'électricité se stockant difficilement à grande échelle, l'équilibre entre la production et la consommation doit être rigoureusement maintenu. Une gestion par anticipation de la demande se complexifie avec l'intégration au mix de production des énergies renouvelables intermittentes. Parallèlement, le déploiement des compteurs communicants permet d'envisager un pilotage dynamique de la consommation électrique. Plus concrètement, l'envoi de signaux - tels que des changements du prix de l'électricité – permettrait d'inciter les usagers à moduler leur consommation afin qu'elle s'ajuste au mieux à la production d'électricité. Les algorithmes choisissant ces signaux devront apprendre la réaction des consommateurs face aux envois tout en les optimisant (compromis exploration-exploitation). Notre approche, fondée sur la théorie des bandits, a permis de formaliser ce problème d'apprentissage séquentiel et de proposer un premier algorithme pour piloter la demande électrique d'une population homogène de consommateurs. Une borne supérieure d'ordre T⅔ a été obtenue sur le regret de cet algorithme. Des expériences réalisées sur des données de consommation de foyers soumis à des changements dynamiques du prix de l'électricité illustrent ce résultat théorique. Un jeu de données en « information complète » étant nécessaire pour tester un algorithme de bandits, un simulateur de données de consommation fondé sur les auto-encodeurs variationnels a ensuite été construit. Afin de s'affranchir de l'hypothèse d'homogénéité de la population, une approche pour segmenter les foyers en fonction de leurs habitudes de consommation est aussi proposée. Ces différents travaux sont finalement combinés pour proposer et tester des algorithmes de bandits pour un pilotage personnalisé de la consommation électrique
As electricity is hard to store, the balance between production and consumption must be strictly maintained. With the integration of intermittent renewable energies into the production mix, the management of the balance becomes complex. At the same time, the deployment of smart meters suggests demand response. More precisely, sending signals - such as changes in the price of electricity - would encourage users to modulate their consumption according to the production of electricity. The algorithms used to choose these signals have to learn consumer reactions and, in the same time, to optimize them (exploration-exploration trade-off). Our approach is based on bandit theory and formalizes this sequential learning problem. We propose a first algorithm to control the electrical demand of a homogeneous population of consumers and offer T⅔ upper bound on its regret. Experiments on a real data set in which price incentives were offered illustrate these theoretical results. As a “full information” dataset is required to test bandit algorithms, a consumption data generator based on variational autoencoders is built. In order to drop the assumption of the population homogeneity, we propose an approach to cluster households according to their consumption profile. These different works are finally combined to propose and test a bandit algorithm for personalized demand side management

APA, Harvard, Vancouver, ISO, and other styles

49

Tripathi, Pushkar. "Allocation problems with partial information." Diss., Georgia Institute of Technology, 2012. http://hdl.handle.net/1853/44789.

Full text

Abstract:

Allocation problems have been central to the development of the theory of algorithms and also find applications in several realms of computer science and economics. In this thesis we initiate a systematic study of these problems in situations with limited information. Towards this end we explore several modes by which data may be obfuscated from the algorithm. We begin by investigating temporal constraints where data is revealed to the algorithm over time. Concretely, we consider the online bipartite matching problem in the unknown distribution model and present the first algorithm that breaches the 1-1/e barrier for this problem. Next we study issues arising from data acquisition costs that are prevalent in ad-systems and kidney exchanges. Motivated by these constraints we introduce the query-commit model and present constant factor algorithms for the maximum matching and the adwords problem in this model. Finally we assess the approximability of several classical allocation problems with multiple agents having complex non-linear cost functions. This presents an additional obstacle since the support for the cost functions may be extremely large entailing oracle access. We show tight information theoretic lower bounds for the general class of submodular functions and also extend these results to get lower bounds for a subclass of succinctly representable non-linear cost functions.

APA, Harvard, Vancouver, ISO, and other styles

50

Okamoto, Kazuya. "Efficient Algorithms for Stable Matching and Online Scheduling Problems." 京都大学 (Kyoto University), 2009. http://hdl.handle.net/2433/123858.

Full text

APA, Harvard, Vancouver, ISO, and other styles

Dissertations / Theses on the topic 'Algorithmes online'

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles