Teses / dissertações sobre o tema "Algorithmes online"
Crie uma referência precisa em APA, MLA, Chicago, Harvard, e outros estilos
Veja os 50 melhores trabalhos (teses / dissertações) para estudos sobre o assunto "Algorithmes online".
Ao lado de cada fonte na lista de referências, há um botão "Adicionar à bibliografia". Clique e geraremos automaticamente a citação bibliográfica do trabalho escolhido no estilo de citação de que você precisa: APA, MLA, Harvard, Chicago, Vancouver, etc.
Você também pode baixar o texto completo da publicação científica em formato .pdf e ler o resumo do trabalho online se estiver presente nos metadados.
Veja as teses / dissertações das mais diversas áreas científicas e compile uma bibliografia correta.
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.
Texto completo da fonteJin, Shendan. "Online computation beyond standard models". Electronic Thesis or Diss., Sorbonne université, 2020. http://www.theses.fr/2020SORUS152.
Texto completo da fonteIn 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
Liu, Ming Chu Chengbin. "Design and Evaluation of Algorithms for Online Machine Scheduling Problems". S. l. : S. n, 2009. http://theses.abes.fr/2009ECAP0028.
Texto completo da fonteNouinou, Hajar. "Ordonnancement semi-online sur machine unitaire pour l’industrie du futur". Thesis, Troyes, 2021. http://www.theses.fr/2021TROY0028.
Texto completo da fonteWe 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
Renault, Marc Paul. "Lower and upper bounds for online algorithms with advice". Paris 7, 2014. http://www.theses.fr/2014PA077196.
Texto completo da fonteOnline 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
Teiller, Alexandre. "Aspects algorithmiques de l'optimisation « multistage »". Electronic Thesis or Diss., Sorbonne université, 2020. http://www.theses.fr/2020SORUS471.
Texto completo da fonteN 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
Vallée, Sven. "Algorithmes d’optimisation pour un service de transport partagé à la demande". Thesis, Université de Lorraine, 2019. http://www.theses.fr/2019LORR0063.
Texto completo da fonteThe 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
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.
Texto completo da fonteBlack-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
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.
Texto completo da fonteCPUs / 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
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.
Texto completo da fonteWith 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
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.
Texto completo da fonteContent 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
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.
Texto completo da fonteThe 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
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.
Texto completo da fonteThe 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
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.
Texto completo da fonteThe 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
Frery, Jordan. "Ensemble Learning for Extremely Imbalced Data Flows". Thesis, Lyon, 2019. http://www.theses.fr/2019LYSES034.
Texto completo da fonteMachine 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
Aliou, Diallo Aoudi Mohamed Habib. "Local matching algorithms on the configuration model". Electronic Thesis or Diss., Compiègne, 2023. http://www.theses.fr/2023COMP2742.
Texto completo da fonteThe 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
Li, Le. "Online stochastic algorithms". Thesis, Angers, 2018. http://www.theses.fr/2018ANGE0031.
Texto completo da fonteThis 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
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.
Texto completo da fonteWith 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
López, Dawn Ricardo José. "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.
Texto completo da fonteInfluencer 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
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.
Texto completo da fonteResource 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
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.
Texto completo da fonteHarrington, Edward, e 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.
Texto completo da fonteShi, Tian. "Novel Algorithms for Understanding Online Reviews". Diss., Virginia Tech, 2021. http://hdl.handle.net/10919/104998.
Texto completo da fonteDoctor 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.
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.
Texto completo da fonteHung, Yee-shing Regant. "Scheduling online batching systems". Click to view the E-thesis via HKUTO, 2005. http://sunzi.lib.hku.hk/hkuto/record/B34624016.
Texto completo da fonteMak, Kin-sum. "Energy efficient online deadline scheduling". Click to view the E-thesis via HKUTO, 2007. http://sunzi.lib.hku.hk/HKUTO/record/B39558277.
Texto completo da fonte麥健心 e Kin-sum Mak. "Energy efficient online deadline scheduling". Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2007. http://hub.hku.hk/bib/B39558277.
Texto completo da fonteLi, Rongbin, e 李榕滨. "New competitive algorithms for online job scheduling". Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2014. http://hdl.handle.net/10722/197555.
Texto completo da fontepublished_or_final_version
Computer Science
Doctoral
Doctor of Philosophy
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.
Texto completo da fonteLinks 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.
Pasteris, S. U. "Efficient algorithms for online learning over graphs". Thesis, University College London (University of London), 2016. http://discovery.ucl.ac.uk/1516210/.
Texto completo da fonteBonifaci, Vincenzo. "Models and algorithms for online server routing". Doctoral thesis, La Sapienza, 2007. http://hdl.handle.net/11573/917056.
Texto completo da fonteCESARI, TOMMASO RENATO. "ALGORITHMS, LEARNING, AND OPTIMIZATION". Doctoral thesis, Università degli Studi di Milano, 2020. http://hdl.handle.net/2434/699354.
Texto completo da fonteZhu, Jianqiao, e 朱剑桥. "New results on online job scheduling". Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2013. http://hub.hku.hk/bib/B50662351.
Texto completo da fontepublished_or_final_version
Computer Science
Master
Master of Philosophy
Hung, Yee-shing Regant, e 洪宜成. "Scheduling online batching systems". Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2005. http://hub.hku.hk/bib/B34624016.
Texto completo da fonteFernández, Pérez Iñaki. "Distributed Embodied Evolutionary Adaptation of Behaviors in Swarms of Robotic Agents". Thesis, Université de Lorraine, 2017. http://www.theses.fr/2017LORR0300/document.
Texto completo da fonteRobot 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
Cunningham, James. "Efficient, Parameter-Free Online Clustering". The Ohio State University, 2020. http://rave.ohiolink.edu/etdc/view?acc_num=osu1606762403895603.
Texto completo da fonteKamphans, Thomas. "Models and algorithms for online exploration and search". [S.l.] : [s.n.], 2006. http://deposit.ddb.de/cgi-bin/dokserv?idn=980408121.
Texto completo da fonteBirks, Martin David. "Online algorithms for temperature aware job scheduling problems". Thesis, University of Leicester, 2012. http://hdl.handle.net/2381/27686.
Texto completo da fonteZadimoghaddam, Morteza. "Online allocation algorithms with applications in computational advertising". Thesis, Massachusetts Institute of Technology, 2014. http://hdl.handle.net/1721.1/87940.
Texto completo da fonteCataloged 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.
Packer, Heather S. "Evolving ontologies with online learning and forgetting algorithms". Thesis, University of Southampton, 2011. https://eprints.soton.ac.uk/194923/.
Texto completo da fonteMoon, Kyung Seob. "Consistency Maintenance Algorithms for Multiplayer Online Digital Games". Thesis, Griffith University, 2007. http://hdl.handle.net/10072/367081.
Texto completo da fonteThesis (PhD Doctorate)
Doctor of Philosophy (PhD)
School of Information and Communication Technology
Faculty of Engineering and Information Technology
Full Text
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.
Texto completo da fonteWe 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.
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.
Texto completo da fonteTese (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
Zhang, Lele. "On-line scheduling with constraints /". Connect to thesis, 2009. http://repository.unimelb.edu.au/10187/3538.
Texto completo da fonteHolmgren, Faghihi Josef, e 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.
Texto completo da fonteDen 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.
Murphy, Nicholas John. "An online learning algorithm for technical trading". Master's thesis, Faculty of Science, 2019. http://hdl.handle.net/11427/31048.
Texto completo da fonteBellas, Anastasios. "Détection d'anomalies à la volée dans des signaux vibratoires". Thesis, Paris 1, 2014. http://www.theses.fr/2014PA010020.
Texto completo da fonteThe 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
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.
Texto completo da fonteAs 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
Tripathi, Pushkar. "Allocation problems with partial information". Diss., Georgia Institute of Technology, 2012. http://hdl.handle.net/1853/44789.
Texto completo da fonteOkamoto, Kazuya. "Efficient Algorithms for Stable Matching and Online Scheduling Problems". 京都大学 (Kyoto University), 2009. http://hdl.handle.net/2433/123858.
Texto completo da fonte