Literatura académica sobre el tema "Algorithmes online"
Crea una cita precisa en los estilos APA, MLA, Chicago, Harvard y otros
Consulte las listas temáticas de artículos, libros, tesis, actas de conferencias y otras fuentes académicas sobre el tema "Algorithmes online".
Junto a cada fuente en la lista de referencias hay un botón "Agregar a la bibliografía". Pulsa este botón, y generaremos automáticamente la referencia bibliográfica para la obra elegida en el estilo de cita que necesites: APA, MLA, Harvard, Vancouver, Chicago, etc.
También puede descargar el texto completo de la publicación académica en formato pdf y leer en línea su resumen siempre que esté disponible en los metadatos.
Artículos de revistas sobre el tema "Algorithmes online"
1
Tornede, Alexander, Viktor Bengs, and Eyke Hüllermeier. "Machine Learning for Online Algorithm Selection under Censored Feedback." Proceedings of the AAAI Conference on Artificial Intelligence 36, no. 9 (2022): 10370–80. http://dx.doi.org/10.1609/aaai.v36i9.21279.
Texto completoResumen
In online algorithm selection (OAS), instances of an algorithmic problem class are presented to an agent one after another, and the agent has to quickly select a presumably best algorithm from a fixed set of candidate algorithms. For decision problems such as satisfiability (SAT), quality typically refers to the algorithm's runtime. As the latter is known to exhibit a heavy-tail distribution, an algorithm is normally stopped when exceeding a predefined upper time limit. As a consequence, machine learning methods used to optimize an algorithm selection strategy in a data-driven manner need to deal with right-censored samples, a problem that has received little attention in the literature so far. In this work, we revisit multi-armed bandit algorithms for OAS and discuss their capability of dealing with the problem. Moreover, we adapt them towards runtime-oriented losses, allowing for partially censored data while keeping a space- and time-complexity independent of the time horizon. In an extensive experimental evaluation on an adapted version of the ASlib benchmark, we demonstrate that theoretically well-founded methods based on Thompson sampling perform specifically strong and improve in comparison to existing methods.
2
Lange, Tomer, Joseph (Seffi) Naor, and Gala Yadgar. "Offline and Online Algorithms for SSD Management." ACM SIGMETRICS Performance Evaluation Review 50, no. 1 (2022): 89–90. http://dx.doi.org/10.1145/3547353.3522630.
Texto completoResumen
The abundance of system-level optimizations for reducing SSD write amplification, which are usually based on experimental evaluation, stands in contrast to the lack of theoretical algorithmic results in this problem domain. To bridge this gap, we explore the problem of reducing write amplification from an algorithmic perspective, considering it in both offline and online settings. In the offline setting, we present a near-optimal algorithm. In the online setting, we first consider algorithms that have no prior knowledge about the input. We present a worst case lower bound and show that the greedy algorithm is optimal in this setting. Then we design an online algorithm that uses predictions about the input. We show that when predictions are pretty accurate, our algorithm circumvents the above lower bound. We complement our theoretical findings with an empirical evaluation of our algorithms, comparing them with the state-of-the-art scheme. The results confirm that our algorithms exhibit an improved performance for a wide range of input traces.
3
Putri, Salsa Della Guitara, Eko Priyo Purnomo, and Tiara Khairunissa. "Echo Chambers and Algorithmic Bias: The Homogenization of Online Culture in a Smart Society." SHS Web of Conferences 202 (2024): 05001. http://dx.doi.org/10.1051/shsconf/202420205001.
Texto completoResumen
The rise of smart societies, characterized by extensive use of technology and data-driven algorithms, promises to improve our lives. However, this very technology presents a potential threat to the richness and diversity of online culture. This thesis explores the phenomenon of echo chambers and algorithmic bias, examining how they contribute to the homogenization of online experiences. Social media algorithms personalize content feeds, presenting users with information that reinforces their existing beliefs. This creates echo chambers, where users are isolated from diverse viewpoints. Algorithmic bias, stemming from the data used to train these algorithms, can further exacerbate this issue. The main data in this study were sourced from previous studies (secondary data) which focused on research related homogenizing on online culture. The thesis investigates the impact of echo chambers and algorithmic bias on online culture within smart societies. It explores how these factors limit exposure to a variety of ideas and perspectives, potentially leading to a homogenized online experience. By examining the interplay between echo chambers, algorithmic bias, and the homogenization of online culture in smart societies, this thesis aims to contribute to a more nuanced understanding of the impact of technology on our online experiences.
4
Xu, Chenyang, and Benjamin Moseley. "Learning-Augmented Algorithms for Online Steiner Tree." Proceedings of the AAAI Conference on Artificial Intelligence 36, no. 8 (2022): 8744–52. http://dx.doi.org/10.1609/aaai.v36i8.20854.
Texto completoResumen
This paper considers the recently popular beyond-worst-case algorithm analysis model which integrates machine-learned predictions with online algorithm design. We consider the online Steiner tree problem in this model for both directed and undirected graphs. Steiner tree is known to have strong lower bounds in the online setting and any algorithm’s worst-case guarantee is far from desirable. This paper considers algorithms that predict which terminal arrives online. The predictions may be incorrect and the algorithms’ performance is parameterized by the number of incorrectly predicted terminals. These guarantees ensure that algorithms break through the online lower bounds with good predictions and the competitive ratio gracefully degrades as the prediction error grows. We then observe that the theory is predictive of what will occur empirically. We show on graphs where terminals are drawn from a distribution, the new online algorithms have strong performance even with modestly correct predictions.
5
Smale, Steve, and Yuan Yao. "Online Learning Algorithms." Foundations of Computational Mathematics 6, no. 2 (2005): 145–70. http://dx.doi.org/10.1007/s10208-004-0160-z.
Texto completo
6
BARBAKH, WESAM, and COLIN FYFE. "ONLINE CLUSTERING ALGORITHMS." International Journal of Neural Systems 18, no. 03 (2008): 185–94. http://dx.doi.org/10.1142/s0129065708001518.
Texto completoResumen
We introduce a set of clustering algorithms whose performance function is such that the algorithms overcome one of the weaknesses of K-means, its sensitivity to initial conditions which leads it to converge to a local optimum rather than the global optimum. We derive online learning algorithms and illustrate their convergence to optimal solutions which K-means fails to find. We then extend the algorithm by underpinning it with a latent space which enables a topology preserving mapping to be found. We show visualisation results on some standard data sets.
7
Sharma, Vishal, Kirsten E. Bray, Neha Kumar, and Rebecca E. Grinter. "Romancing the Algorithm." Proceedings of the ACM on Human-Computer Interaction 6, CSCW2 (2022): 1–29. http://dx.doi.org/10.1145/3555651.
Texto completoResumen
Many romance novelists have shifted to self-publishing mediated through online technologies, such as online retailer platforms for selling novels and social media for marketing. However, engagement with such complex algorithmic systems has posed challenges, including understanding continually changing algorithms, frequently changing silently, impacting novelists' successful professionalization and monetization. We conducted surveys and interviews with romance novelists to examine how they experience, interpret, and navigate algorithms. Our findings detail interviewees' efforts to comprehend algorithms, both individually and collectively, and leverage that comprehension to navigate and manipulate algorithms. We discuss how our interviewees constructed literacy of precarious algorithms on their work platforms, suggesting implications for designing algorithmic systems supporting digital work.
8
K, Kousalya, and Balasubramanie P. "Online Grid Scheduling Using Ant Algorithm." International Journal of Engineering and Technology 1, no. 1 (2009): 21–26. http://dx.doi.org/10.7763/ijet.2009.v1.4.
Texto completo
9
Möhlmann, Mareike, Lior Zalmanson, Ola Henfridsson, and Robert Wayne Gregory. "Algorithmic Management of Work on Online Labor Platforms: When Matching Meets Control." MIS Quarterly 45, no. 4 (2021): 1999–2022. http://dx.doi.org/10.25300/misq/2021/15333.
Texto completoResumen
Online labor platforms (OLPs) can use algorithms along two dimensions: matching and control. While previous research has paid considerable attention to how OLPs optimize matching and accommodate market needs, OLPs can also employ algorithms to monitor and tightly control platform work. In this paper, we examine the nature of platform work on OLPs, and the role of algorithmic management in organizing how such work is conducted. Using a qualitative study of Uber drivers’ perceptions, supplemented by interviews with Uber executives and engineers, we present a grounded theory that captures the algorithmic management of work on OLPs. In the context of both algorithmic matching and algorithmic control, platform workers experience tensions relating to work execution, compensation, and belonging. We show that these tensions trigger market-like and organization-like response behaviors by platform workers. Our research contributes to the emerging literature on OLPs.
10
Lange, Tomer, Joseph (Seffi) Naor, and Gala Yadgar. "Offline and Online Algorithms for SSD Management." Communications of the ACM 66, no. 7 (2023): 129–37. http://dx.doi.org/10.1145/3596205.
Texto completoResumen
Flash-based solid-state drives (SSDs) are a key component in most computer systems, thanks to their ability to support parallel I/O at sub-millisecond latency and consistently high throughput. At the same time, due to the limitations of the flash media, they perform writes out-of-place, often incurring a high internal overhead which is referred to as write amplification. Minimizing this overhead has been the focus of numerous studies by the systems research community for more than two decades. The abundance of system-level optimizations for reducing SSD write amplification, which is typically based on experimental evaluation, stands in stark contrast to the lack of theoretical algorithmic results in this problem domain. To bridge this gap, we explore the problem of reducing write amplification from an algorithmic perspective, considering it in both offline and online settings. In the offline setting, we present a near-optimal algorithm. In the online setting, we first consider algorithms that have no prior knowledge about the input and show that in this case, the greedy algorithm is optimal. Then, we design an online algorithm that uses predictions about the input. We show that when predictions are relatively accurate, our algorithm significantly improves over the greedy algorithm. We complement our theoretical findings with an empirical evaluation of our algorithms, comparing them with the state-of-the-art scheme. The results confirm that our algorithms exhibit an improved performance for a wide range of input traces.
Tesis sobre el tema "Algorithmes online"
1
Sentenac, Flore. "Learning and Algorithms for Online Matching." Electronic Thesis or Diss., Institut polytechnique de Paris, 2023. http://www.theses.fr/2023IPPAG005.
Texto completoResumen
Cette thèse se concentre principalement sur les problèmes d'appariement en ligne, où des ensembles de ressources sont alloués séquentiellement à des flux de demandes. Nous les traitons à la fois du point de vue de l'apprentissage en ligne et de l'analyse compétitive, toujours lorsqueEn ce qui concerne l'apprentissage en ligne, nous étudions comment la structure spécifique de l'appariement influence l'apprentissage dans la première partie, puis comment les effets de report dans le système affectent ses performances.En ce qui concerne l'analyse compétitive, nous étudions le problème de l'appariement en ligne dans des classes spécifiques de graphes aléatoires, dans un effort pour s'éloigner de l'analyse du pire cas.Enfin, nous explorons la manière dont l'apprentissage peut être exploité dans le problème d'ordonnancement des machines<br>This thesis focuses mainly on online matching problems, where sets of resources are sequentially allocated to demand streams. We treat them both from an online learning and a competitive analysis perspective, always in the case when the input is stochastic.On the online learning side, we study how the specific matching structure influences learning in the first part, then how carry-over effects in the system affect its performance.On the competitive analysis side, we study the online matching problem in specific classes of random graphs, in an effort to move away from worst-case analysis.Finally, we explore how learning can be leveraged in the scheduling problem
2
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 completoResumen
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.
3
Jin, Shendan. "Online computation beyond standard models." Electronic Thesis or Diss., Sorbonne université, 2020. http://www.theses.fr/2020SORUS152.
Texto completoResumen
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<br>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
4
Ben, Mazziane Younes. "Analyse probabiliste pour le caching." Electronic Thesis or Diss., Université Côte d'Azur, 2024. http://www.theses.fr/2024COAZ4014.
Texto completoResumen
Les caches sont de petites mémoires qui accélèrent la récupération des données. L'un des objectifs des politiques de mise en cache est de sélectionner le contenu du cache afin de minimiser le temps de réponse aux requêtes d'objets. Un problème plus général permet de répondre approximativement à la requête d'un objet par un objet similaire mis en cache. Ce concept, appelé "mise en cache par similarité", s'avère utile pour les systèmes de recommandation. L'objectif est de minimiser le temps de latence tout en fournissant des réponses satisfaisantes. La compréhension théorique des algorithmes de gestion de la mémoire cache, sous des hypothèses spécifiques sur les requêtes, aide à choisir un algorithme approprié. Les politiques d'éviction du cache les plus répandues sont celles de l'utilisation la moins fréquente (LFU) et de l'utilisation la moins récente (LRU). LFU est efficace lorsque le processus requêtes est stationnaire, et LRU s'adapte aux changements dans les processus de requêtes. Les algorithmes d'apprentissage séquentiel, tels que l'algorithme aléatoire Follow-the-Perturbed Leader (FPL), appliqués à la mise en cache, bénéficient de garanties théoriques même dans le pire des cas.LFU et FPL s'appuient sur le nombre de requêtes d'objets. Cependant, le comptage est un défi dans les scénarios à mémoire limitée. Pour y remédier, les politiques de mise en cache utilisent des schémas de comptage approximatifs, tels que la structure de données Count-Min Sketch avec mises à jour conservatrices (CMS-CU), afin d'équilibrer la précision des comptages et l'utilisation de la mémoire. Dans le cadre de la mise en cache par similarité, RND-LRU est une stratégie LRU modifiée. Malheureusement, il reste difficile de quantifier théoriquement à la fois la performance d'un cache LFU utilisant CMS-CU, celle d'un cache FPL avec un algorithme de comptage approximatif, ainsi que celle de RND-LRU.Cette thèse explore trois algorithmes probabilistes : CMS-CU, FPL avec des estimations bruitées des nombres de requêtes d'objets (NFPL) et RND-LRU. Pour CMS-CU, nous proposons une approche novatrice pour trouver de nouvelles bornes supérieures sur l'espérance et le complémentaire de la fonction de répartition de l'erreur d'estimation sous un processus de requêtes i.i.d. De plus, nous démontrons que NFPL se comporte aussi bien que la politique de mise en cache statique, optimale et omnisciente, quelle que soit la séquence de requêtes (sous certaines conditions sur les comptages bruités). Enfin, nous introduisons une nouvelle politique de mise en cache qui est analytiquement résoluble. Nous montrons alors que cette politique approxime RND-LRU<br>Caches are small memories that speed up data retrieval. Caching policies may aim to choose cache content to minimize latency in responding to item requests. A more general problem permits an item's request to be approximately answered by a similar cached item. This concept, referred to as "similarity caching," proves valuable for content-based image retrieval and recommendation systems. The objective is to further minimize latency while delivering satisfactory answers.Theoretical understanding of cache memory management algorithms under specific assumptions on the requests provides guidelines for choosing a suitable algorithm. The Least-Frequently-Used (LFU) and the Least-Recently-Used (LRU) are popular caching eviction policies. LFU is efficient when the requests process is stationary, while LRU adapts to changes in the patterns of the requests. Online learning algorithms, such as the randomized Follow-the-Perturbed Leader (FPL) algorithm, applied for caching, enjoy worst-case guarantees. Both LFU and FPL rely on items' request count. However, counting is challenging in memory-constrained scenarios. To overcome this problem, caching policies operate with approximate counting schemes, such as the Count-Min Sketch with Conservative Updates (CMS-CU), to balance counts' accuracy and memory usage. In the similarity caching setting, RND-LRU is a modified LRU where a request is probabilistically answered by the most similar cached item. Unfortunately, a theoretical analysis of an LFU cache utilizing CMS-CU, an FPL cache with an approximate counting algorithm, and RND-LRU remains difficult.This thesis investigates three randomized algorithms: CMS-CU, FPL with noisy items' request counts estimations (NFPL), and RND-LRU. For CMS-CU, we propose a novel approach to derive new upper bounds on the expected value and the complementary cumulative distribution function of the estimation error under a renewal request process. Additionally, we prove that NFPL behaves as well as the optimal omniscient static caching policy for any request sequence under specific conditions on the noisy counts. Finally, we introduce a new analytically tractable similarity caching policy and show that it can approximate RND-LRU
5
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
6
Nouinou, Hajar. "Ordonnancement semi-online sur machine unitaire pour l’industrie du futur." Thesis, Troyes, 2021. http://www.theses.fr/2021TROY0028.
Texto completoResumen
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<br>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
7
Renault, Marc Paul. "Lower and upper bounds for online algorithms with advice." Paris 7, 2014. http://www.theses.fr/2014PA077196.
Texto completoResumen
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<br>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
8
Teiller, Alexandre. "Aspects algorithmiques de l'optimisation « multistage »." Electronic Thesis or Diss., Sorbonne université, 2020. http://www.theses.fr/2020SORUS471.
Texto completoResumen
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<br>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
9
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 completoResumen
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<br>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
10
Lu, Wei. "Μéthοdes stοchastiques du secοnd οrdre pοur le traitement séquentiel de dοnnées massives". Electronic Thesis or Diss., Normandie, 2024. http://www.theses.fr/2024NORMIR13.
Texto completoResumen
Avec le développement rapide des technologies et l'acquisition de données de plus en plus massives, les méthodes capables de traiter les données de manière séquentielle (en ligne) sont devenues indispensables. Parmi ces méthodes, les algorithmes de gradient stochastique se sont imposés pour estimer le minimiseur d'une fonction exprimée comme l'espérance d'une fonction aléatoire. Bien qu'ils soient devenus incontournables, ces algorithmes rencontrent des difficultés lorsque le problème est mal conditionné. Dans cette thèse, nous nous intéressons sur les algorithmes stochastiques du second ordre, tels que ceux de type Newton, et leurs applications à diverses problématiques statistiques et d'optimisation. Après avoir établi des bases théoriques et exposé les motivations qui nous amènent à explorer les algorithmes de Newton stochastiques, nous développons les différentes contributions de cette thèse. La première contribution concerne l'étude et le développement d'algorithmes de Newton stochastiques pour la régression linéaire ridge et la régression logistique ridge. Ces algorithmes sont basés sur la formule de Riccati (Sherman-Morrison) pour estimer récursivement l'inverse de la Hessienne. Comme l'acquisition de données massives s'accompagne généralement d'une contamination de ces dernières, on s'intéresse, dans une deuxième contribution, à l'estimation en ligne de la médiane géométrique, qui est un indicateur robuste, i.e. peu sensible à la présence de données atypiques. Plus précisément, nous proposons un nouvel estimateur de Newton stochastique pour estimer la médiane géométrique. Dans les deux premières contributions, les estimateurs des inverses de Hessienne sont construits à l'aide de la formule de Riccati, mais cela n'est possible que pour certaines fonctions. Ainsi, notre troisième contribution introduit une nouvelle méthode de type Robbins-Monro pour l'estimation en ligne de l'inverse de la Hessienne, nous permettant ensuite de développer des algorithmes de Newton stochastiques dits universels. Enfin, notre dernière contribution se focalise sur des algorithmes de type Full Adagrad, où la difficulté réside dans le fait que l'on a un pas adaptatif basé sur la racine carré de l'inverse de la variance du gradient. On propose donc un algorithme de type Robbins-Monro pour estimer cette matrice, nous permettant ainsi de proposer une approche récursive pour Full AdaGrad et sa version streaming, avec des coûts de calcul réduits. Pour tous les nouveaux estimateurs que nous proposons, nous établissons leurs vitesses de convergence ainsi que leur efficacité asymptotique. De plus, nous illustrons l'efficacité de ces algorithmes à l'aide de simulations numériques et en les appliquant à des données réelles<br>With the rapid development of technologies and the acquisition of big data, methods capable of processing data sequentially (online) have become indispensable. Among these methods, stochastic gradient algorithms have been established for estimating the minimizer of a function expressed as the expectation of a random function. Although they have become essential, these algorithms encounter difficulties when the problem is ill-conditioned. In this thesis, we focus on second-order stochastic algorithms, such as those of the Newton type, and their applications to various statistical and optimization problems. After establishing theoretical foundations and exposing the motivations that lead us to explore stochastic Newton algorithms, we develop the various contributions of this thesis. The first contribution concerns the study and development of stochastic Newton algorithms for ridge linear regression and ridge logistic regression. These algorithms are based on the Riccati formula (Sherman-Morrison) to recursively estimate the inverse of the Hessian. As the acquisition of big data is generally accompanied by a contamination of the latter, in a second contribution, we focus on the online estimation of the geometric median, which is a robust indicator, i.e., not very sensitive to the presence of atypical data. More specifically, we propose a new stochastic Newton estimator to estimate the geometric median. In the first two contributions, the estimators of the Hessians' inverses are constructed using the Riccati formula, but this is only possible for certain functions. Thus, our third contribution introduces a new Robbins-Monro type method for online estimation of the Hessian's inverse, allowing us then to develop universal stochastic Newton algorithms. Finally, our last contribution focuses on Full Adagrad type algorithms, where the difficulty lies in the fact that there is an adaptive step based on the square root of the inverse of the gradient's covariance. We thus propose a Robbins-Monro type algorithm to estimate this matrix, allowing us to propose a recursive approach for Full AdaGrad and its streaming version, with reduced computational costs. For all the new estimators we propose, we establish their convergence rates as well as their asymptotic efficiency. Moreover, we illustrate the efficiency of these algorithms using numerical simulations and by applying them to real data
Libros sobre el tema "Algorithmes online"
1
Evripidis, Bampis, Jansen Klaus, and Kenyon Claire, eds. Efficient approximation and online algorithms: Recent progress on classical combinatorical optimization problems and new applications. Springer, 2006.
Buscar texto completo
2
Evripidis, Bampis, Jansen Klaus, and Kenyon Claire, eds. Efficient approximation and online algorithms: Recent progress on classical combinatorical optimization problems and new applications. Springer, 2006.
Buscar texto completo
3
Fiat, Amos, and Gerhard J. Woeginger, eds. Online Algorithms. Springer Berlin Heidelberg, 1998. http://dx.doi.org/10.1007/bfb0029561.
Texto completo
4
WAOA 2008 (2008 Karlesruhe, Germany). Approximation and online algorithms: 6th international workshop, WAOA 2008, Karlsruhe, Germany, September 18-19, 2008 : revised papers. Springer, 2009.
Buscar texto completo
5
Kaklamanis, Christos, and Asaf Levin, eds. Approximation and Online Algorithms. Springer International Publishing, 2021. http://dx.doi.org/10.1007/978-3-030-80879-2.
Texto completo
6
Koenemann, Jochen, and Britta Peis, eds. Approximation and Online Algorithms. Springer International Publishing, 2021. http://dx.doi.org/10.1007/978-3-030-92702-8.
Texto completo
7
Chalermsook, Parinya, and Bundit Laekhanukit, eds. Approximation and Online Algorithms. Springer International Publishing, 2022. http://dx.doi.org/10.1007/978-3-031-18367-6.
Texto completo
8
Bampis, Evripidis, and Ola Svensson, eds. Approximation and Online Algorithms. Springer International Publishing, 2015. http://dx.doi.org/10.1007/978-3-319-18263-6.
Texto completo
9
Sanità, Laura, and Martin Skutella, eds. Approximation and Online Algorithms. Springer International Publishing, 2015. http://dx.doi.org/10.1007/978-3-319-28684-6.
Texto completo
10
Erlebach, Thomas, and Giuseppe Persiano, eds. Approximation and Online Algorithms. Springer Berlin Heidelberg, 2013. http://dx.doi.org/10.1007/978-3-642-38016-7.
Texto completoCapítulos de libros sobre el tema "Algorithmes online"
1
Fiat, Amos, and Gerhard J. Woeginger. "Competitive analysis of algorithms." In Online Algorithms. Springer Berlin Heidelberg, 1998. http://dx.doi.org/10.1007/bfb0029562.
Texto completo
2
Albers, Susanne, and Jeffery Westbrook. "Self-organizing data structures." In Online Algorithms. Springer Berlin Heidelberg, 1998. http://dx.doi.org/10.1007/bfb0029563.
Texto completo
3
Irani, Sandy. "Competitive analysis of paging." In Online Algorithms. Springer Berlin Heidelberg, 1998. http://dx.doi.org/10.1007/bfb0029564.
Texto completo
4
Chrobak, Marek, and Lawrence L. Larmore. "Metrical task systems, the server problem and the work function algorithm." In Online Algorithms. Springer Berlin Heidelberg, 1998. http://dx.doi.org/10.1007/bfb0029565.
Texto completo
5
Bartal, Yair. "Distributed paging." In Online Algorithms. Springer Berlin Heidelberg, 1998. http://dx.doi.org/10.1007/bfb0029566.
Texto completo
6
Aspnes, James. "Competitive analysis of distributed algorithms." In Online Algorithms. Springer Berlin Heidelberg, 1998. http://dx.doi.org/10.1007/bfb0029567.
Texto completo
7
Csirik, János, and Gerhard J. Woeginger. "On-line packing and covering problems." In Online Algorithms. Springer Berlin Heidelberg, 1998. http://dx.doi.org/10.1007/bfb0029568.
Texto completo
8
Azar, Yossi. "On-line load balancing." In Online Algorithms. Springer Berlin Heidelberg, 1998. http://dx.doi.org/10.1007/bfb0029569.
Texto completo
9
Sgall, JiŘí. "On-line scheduling." In Online Algorithms. Springer Berlin Heidelberg, 1998. http://dx.doi.org/10.1007/bfb0029570.
Texto completo
10
Berman, Piotr. "On-line searching and navigation." In Online Algorithms. Springer Berlin Heidelberg, 1998. http://dx.doi.org/10.1007/bfb0029571.
Texto completoActas de conferencias sobre el tema "Algorithmes online"
1
Degroote, Hans. "Online Algorithm Selection." In Twenty-Sixth International Joint Conference on Artificial Intelligence. International Joint Conferences on Artificial Intelligence Organization, 2017. http://dx.doi.org/10.24963/ijcai.2017/746.
Texto completoResumen
Algorithm selection approaches have achieved impressive performance improvements in many areas of AI. Most of the literature considers the offline algorithm selection problem, where the initial selection model is never updated after training. However, new data from running algorithms on instances becomes available while an algorithm selection method is in use. In this extended abstract, the online algorithm selection problem is considered. In online algorithm selection, additional data can be processed, and the selection model can change over time. This abstract details the online algorithm setting, shows that it is a contextual multi-armed bandit, proposes a solution methodology, and empirically validates it.
2
Soma, Tasuku, and Yuichi Yoshida. "Online Risk-Averse Submodular Maximization." In Thirtieth International Joint Conference on Artificial Intelligence {IJCAI-21}. International Joint Conferences on Artificial Intelligence Organization, 2021. http://dx.doi.org/10.24963/ijcai.2021/411.
Texto completoResumen
We present a polynomial-time online algorithm for maximizing the conditional value at risk (CVaR) of a monotone stochastic submodular function. Given T i.i.d. samples from an underlying distribution arriving online, our algorithm produces a sequence of solutions that converges to a (1−1/e)-approximate solution with a convergence rate of O(T −1/4 ) for monotone continuous DR-submodular functions. Compared with previous offline algorithms, which require Ω(T) space, our online algorithm only requires O( √ T) space. We extend our on- line algorithm to portfolio optimization for mono- tone submodular set functions under a matroid constraint. Experiments conducted on real-world datasets demonstrate that our algorithm can rapidly achieve CVaRs that are comparable to those obtained by existing offline algorithms.
3
Sardarmehni, Tohid, and Ali Heydari. "Approximate Solution for Optimal Control of Continuous-Time Switched Systems." In ASME 2016 Dynamic Systems and Control Conference. American Society of Mechanical Engineers, 2016. http://dx.doi.org/10.1115/dscc2016-9745.
Texto completoResumen
Two approximate solutions for optimal control of switched systems with autonomous subsystems and continuous-time dynamics are developed. The proposed solutions consist of online training algorithms with recursive least squares training laws. The first solution is the classic policy iteration algorithm which imposes heavy computational burden (full back-up). In order to relax the computational burden in the policy iteration algorithm, the second algorithm is presented. The convergence of the proposed algorithms to the optimal solution in online training is investigated. Simulation results are presented to illustrate the effectiveness of the discussed algorithms.
4
Banerjee, Siddhartha, Vasilis Gkatzelis, Safwan Hossain, Billy Jin, Evi Micha, and Nisarg Shah. "Proportionally Fair Online Allocation of Public Goods with Predictions." In Thirty-Second International Joint Conference on Artificial Intelligence {IJCAI-23}. International Joint Conferences on Artificial Intelligence Organization, 2023. http://dx.doi.org/10.24963/ijcai.2023/3.
Texto completoResumen
We design online algorithms for fair allocation of public goods to a set of N agents over a sequence of T rounds and focus on improving their performance using predictions. In the basic model, a public good arrives in each round, and every agent reveals their value for it upon arrival. The algorithm must irrevocably decide the investment in this good without exceeding a total budget of B across all rounds. The algorithm can utilize (potentially noisy) predictions of each agent’s total value for all remaining goods. The algorithm's performance is measured using a proportional fairness objective, which informally demands that every group of agents be rewarded proportional to its size and the cohesiveness of its preferences. We show that no algorithm can achieve better than Θ(T/B) proportional fairness without predictions. With reasonably accurate predictions, the situation improves significantly, and Θ(log(T/B)) proportional fairness is achieved. We also extend our results to a general setting wherein a batch of L public goods arrive in each round and O(log(min(N,L)T/B)) proportional fairness is achieved. Our exact bounds are parameterized as a function of the prediction error, with performance degrading gracefully with increasing errors.
5
Hao, Shuji, Peilin Zhao, Yong Liu, Steven C. H. Hoi, and Chunyan Miao. "Online Multitask Relative Similarity Learning." In Twenty-Sixth International Joint Conference on Artificial Intelligence. International Joint Conferences on Artificial Intelligence Organization, 2017. http://dx.doi.org/10.24963/ijcai.2017/253.
Texto completoResumen
Relative similarity learning~(RSL) aims to learn similarity functions from data with relative constraints. Most previous algorithms developed for RSL are batch-based learning approaches which suffer from poor scalability when dealing with real-world data arriving sequentially. These methods are often designed to learn a single similarity function for a specific task. Therefore, they may be sub-optimal to solve multiple task learning problems. To overcome these limitations, we propose a scalable RSL framework named OMTRSL (Online Multi-Task Relative Similarity Learning). Specifically, we first develop a simple yet effective online learning algorithm for multi-task relative similarity learning. Then, we also propose an active learning algorithm to save the labeling cost. The proposed algorithms not only enjoy theoretical guarantee, but also show high efficacy and efficiency in extensive experiments on real-world datasets.
6
Yang, Zhengchen, and Jiping Zheng. "Online Submodular Maximization via Adaptive Thresholds." In Thirty-Third International Joint Conference on Artificial Intelligence {IJCAI-24}. International Joint Conferences on Artificial Intelligence Organization, 2024. http://dx.doi.org/10.24963/ijcai.2024/781.
Texto completoResumen
Submodular function maximization has been studied extensively in recent years due to its numerous applications in machine learning and artificial intelligence. We study a natural online variant of this problem on massive streaming data in which elements arrive one-by-one and the algorithm has to maintain a solution under cardinality constraint, i.e., k. Upon arrival of an element, the algorithm to maximize a monotone submodular function has to decide whether to accept the element and may replace a previously chosen element. Existing algorithms cannot simultaneously achieve optimal performance in terms of competitive ratio, memory complexity and running time. Also, the algorithm with best competitive ratio performs poorly in practice. In this paper, we propose a new algorithm OnlineAdaptive with optimal performance by exploiting adaptive thresholds to decide the acceptance of arriving elements by replacement. We prove that the competitive ratio of OnlineAdaptive is at least 1/4, and the ratio is about 0.2959 when k>=4 and approaches 0.3178 when k tends to infinity. In addition, OnlineAdaptive only needs O(k) memory and just performs one oracle per element. Experiments on diverse datasets confirm that OnlineAdaptive outperforms existing algorithms in both quality and efficiency.
7
Yang, Peng, Peilin Zhao, and Xin Gao. "Bandit Online Learning on Graphs via Adaptive Optimization." In Twenty-Seventh International Joint Conference on Artificial Intelligence {IJCAI-18}. International Joint Conferences on Artificial Intelligence Organization, 2018. http://dx.doi.org/10.24963/ijcai.2018/415.
Texto completoResumen
Traditional online learning on graphs adapts graph Laplacian into ridge regression, which may not guarantee reasonable accuracy when the data are adversarially generated. To solve this issue, we exploit an adaptive optimization framework for online classification on graphs. The derived model can achieve a min-max regret under an adversarial mechanism of data generation. To take advantage of the informative labels, we propose an adaptive large-margin update rule, which enjoys a lower regret than the algorithms using error-driven update rules. However, this algorithm assumes that the full information label is provided for each node, which is violated in many practical applications where labeling is expensive and the oracle may only tell whether the prediction is correct or not. To address this issue, we propose a bandit online algorithm on graphs. It derives per-instance confidence region of the prediction, from which the model can be learned adaptively to minimize the online regret. Experiments on benchmark graph datasets show that the proposed bandit algorithm outperforms state-of-the-art competitors, even sometimes beats the algorithms using full information label feedback.
8
Lintzmayer, Carla Negri, Flávio Keidi Miyazawa, and Eduardo Candido Xavier. "Online Circle and Sphere Packing∗." In III Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2018. http://dx.doi.org/10.5753/etc.2018.3158.
Texto completoResumen
In the Online Circle Packing in Squares, circles arrive one at a time and we need to pack them into the minimum number of unit square bins. We improve the previous best-known competitive ratio for the bounded space version from 2.439 to 2.3536 and we also give an unbounded space algorithm. Our algorithms also apply to the Online Circle Packing in Isosceles Right Triangles and Online Sphere Packing in Cubes, for which no previous results were known.
9
Banas, Ryan, Andrew McDonald, and Tegwyn Perkins. "NOVEL METHODOLOGY FOR AUTOMATION OF BAD WELL LOG DATA IDENTIFICATION AND REPAIR." In 2021 SPWLA 62nd Annual Logging Symposium Online. Society of Petrophysicists and Well Log Analysts, 2021. http://dx.doi.org/10.30632/spwla-2021-0070.
Texto completoResumen
Subsurface analysis-driven field development requires quality data as input into analysis, modelling, and planning. In the case of many conventional reservoirs, pay intervals are often well consolidated and maintain integrity under drilling and geological stresses providing an ideal logging environment. Consequently, editing well logs is often overlooked or dismissed entirely. Petrophysical analysis however is not always constrained to conventional pay intervals. When developing an unconventional reservoir, pay sections may be comprised of shales. The requirement for edited and quality checked logs becomes crucial to accurately assess storage volumes in place. Edited curves can also serve as inputs to engineering studies, geological and geophysical models, reservoir evaluation, and many machine learning models employed today. As an example, hydraulic fracturing model inputs may span over adjacent shale beds around a target reservoir, which are frequently washed out. These washed out sections may seriously impact logging measurements of interest, such as bulk density and acoustic compressional slowness, which are used to generate elastic properties and compute geomechanical curves. Two classifications of machine learning algorithms for identifying outliers and poor-quality data due to bad hole conditions are discussed: supervised and unsupervised learning. The first allows the expert to train a model from existing and categorized data, whereas unsupervised learning algorithms learn from a collection of unlabeled data. Each classification type has distinct advantages and disadvantages. Identifying outliers and conditioning well logs prior to a petrophysical analysis or machine learning model can be a time-consuming and laborious process, especially when large multi-well datasets are considered. In this study, a new supervised learning algorithm is presented that utilizes multiple-linear regression analysis to repair well log data in an iterative and automated routine. This technique allows outliers to be identified and repaired whilst improving the efficiency of the log data editing process without compromising accuracy. The algorithm uses sophisticated logic and curve predictions derived via multiple linear regression in order to systematically repair various well logs. A clear improvement in efficiency is observed when the algorithm is compared to other currently used methods. These include manual processing by a petrophysicist and unsupervised outlier detection methods. The algorithm can also be leveraged over multiple wells to produce more generalized predictions. Through a platform created to quickly identify and repair invalid log data, the results are controlled through input and supervision by the user. This methodology is not a direct replacement of an expert interpreter, but complementary by allowing the petrophysicist to leverage computing power, improve consistency, reduce error and improve turnaround time.
10
Sviridov, Mikhail, Anton Mosin, Sergey Lebedev, and Ron Thompson. "VENDOR-NEUTRAL STOCHASTIC INVERSION OF LWD DEEP AZIMUTHAL RESISTIVITY DATA AS A STEP TOWARD EFFICIENCY STANDARDIZATION OF GEOSTEERING SERVICES." In 2021 SPWLA 62nd Annual Logging Symposium Online. Society of Petrophysicists and Well Log Analysts, 2021. http://dx.doi.org/10.30632/spwla-2021-0103.
Texto completoResumen
While proactive geosteering, special inversion algorithms are used to process the readings of logging-while-drilling resistivity tools in real-time and provide oil field operators with formation models to make informed steering decisions. Currently, there is no industry standard for inversion deliverables and corresponding quality indicators because major tool vendors develop their own device-specific algorithms and use them internally. This paper presents the first implementation of vendor-neutral inversion approach applicable for any induction resistivity tool and enabling operators to standardize the efficiency of various geosteering services. The necessity of such universal inversion approach was inspired by the activity of LWD Deep Azimuthal Resistivity Services Standardization Workgroup initiated by SPWLA Resistivity Special Interest Group in 2016. Proposed inversion algorithm utilizes a 1D layer-cake formation model and is performed interval-by-interval. The following model parameters can be determined: horizontal and vertical resistivities of each layer, positions of layer boundaries, and formation dip. The inversion can support arbitrary deep azimuthal induction resistivity tool with coaxial, tilted, or orthogonal transmitting and receiving antennas. The inversion is purely data-driven; it works in automatic mode and provides fully unbiased results obtained from tool readings only. The algorithm is based on statistical reversible-jump Markov chain Monte Carlo method that does not require any predefined assumptions about the formation structure and enables searching of models explaining the data even if the number of layers in the model is unknown. To globalize search, the algorithm runs several Markov chains capable of exchanging their states between one another to move from the vicinity of local minimum to more perspective domain of model parameter space. While execution, the inversion keeps all models it is dealing with to estimate the resolution accuracy of formation parameters and generate several quality indicators. Eventually, these indicators are delivered together with recovered resistivity models to help operators with the evaluation of inversion results reliability. To ensure high performance of the inversion, a fast and accurate semi-analytical forward solver is employed to compute required responses of a tool with specific geometry and their derivatives with respect to any parameter of multi-layered model. Moreover, the reliance on the simultaneous evolution of multiple Markov chains makes the algorithm suitable for parallel execution that significantly decreases the computational time. Application of the proposed inversion is shown on a series of synthetic examples and field case studies such as navigating the well along the reservoir roof or near the oil-water-contact in oil sands. Inversion results for all scenarios confirm that the proposed algorithm can successfully evaluate formation model complexity, recover model parameters, and quantify their uncertainty within a reasonable computational time. Presented vendor-neutral stochastic approach to data processing leads to the standardization of the inversion output including the resistivity model and its quality indicators that helps operators to better understand capabilities of tools from different vendors and eventually make more confident geosteering decisions.
Informes sobre el tema "Algorithmes online"
1
Ur, Shmuel. Analysis of Online Algorithms for Organ Allocation. Defense Technical Information Center, 1990. http://dx.doi.org/10.21236/ada249361.
Texto completo
2
Santesson, S., and P. Hallam-Baker. Online Certificate Status Protocol Algorithm Agility. RFC Editor, 2011. http://dx.doi.org/10.17487/rfc6277.
Texto completo
3
Harriss, Lydia, and Katie Raymer. Online Information and Fake News. Parliamentary Office of Science and Technology, 2017. http://dx.doi.org/10.58248/pn559.
Texto completoResumen
Internet search engines and social media platforms are an increasingly popular way of accessing news and information. In 2017, the proportion of UK adults consuming news online exceeded those who watched news on TV (74% versus 69%). This note considers how people access news online, how algorithms (sequences of instructions) and social networks influence the content that users see, and options for mitigating any negative impact.
4
Labrindis, Alexandros, and Nick Roussopoulos. A Performance Evaluation of Online Warehouse Update Algorithms. Defense Technical Information Center, 1998. http://dx.doi.org/10.21236/ada441038.
Texto completo
5
Streeter, Matthew, and Daniel Golovin. An Online Algorithm for Maximizing Submodular Functions. Defense Technical Information Center, 2007. http://dx.doi.org/10.21236/ada476748.
Texto completo
6
Balman, Mehmet, and Tevfik Kosar. An Online Scheduling Algorithm with Advance Reservation for Large-Scale Data Transfers. Office of Scientific and Technical Information (OSTI), 2010. http://dx.doi.org/10.2172/1050437.
Texto completo
7
Sadoune, Igor, Marcelin Joanis, and Andrea Lodi. Algorithmic collusion and the minimum price Markov game. CIRANO, 2025. https://doi.org/10.54932/mmfd7174.
Texto completoResumen
This paper introduces the Minimum Price Markov Game (MPMG), a theoretical model that reasonably approximates real-world first-price markets following the minimum price rule, such as public auctions. The goal is to provide researchers and practitioners with a framework to study market fairness and regulation in both digitized and non-digitized public procurement processes, amid growing concerns about algorithmic collusion in online markets. Using multi-agent reinforcement learningdriven artificial agents, we demonstrate that (i) the MPMG is a reliable model for first-price market dynamics, (ii) the minimum price rule is generally resilient to non-engineered tacit coordination among rational actors, and (iii) when tacit coordination occurs, it relies heavily on self-reinforcing trends. These findings contribute to the ongoing debate about algorithmic pricing and its implications.
8
Mathew, Jijo K., Christopher M. Day, Howell Li, and Darcy M. Bullock. Curating Automatic Vehicle Location Data to Compare the Performance of Outlier Filtering Methods. Purdue University, 2021. http://dx.doi.org/10.5703/1288284317435.
Texto completoResumen
Agencies use a variety of technologies and data providers to obtain travel time information. The best quality data can be obtained from second-by-second tracking of vehicles, but that data presents many challenges in terms of privacy, storage requirements and analysis. More frequently agencies collect or purchase segment travel time based upon some type of matching of vehicles between two spatially distributed points. Typical methods for that data collection involve license plate re-identification, Bluetooth, Wi-Fi, or some type of rolling DSRC identifier. One of the challenges in each of these sampling techniques is to employ filtering techniques to remove outliers associated with trip chaining, but not remove important features in the data associated with incidents or traffic congestion. This paper describes a curated data set that was developed from high-fidelity GPS trajectory data. The curated data contained 31,621 vehicle observations spanning 42 days; 2550 observations had travel times greater than 3 minutes more than normal. From this baseline data set, outliers were determined using GPS waypoints to determine if the vehicle left the route. Two performance measures were identified for evaluating three outlier-filtering algorithms by the proportion of true samples rejected and proportion of outliers correctly identified. The effectiveness of the three methods over 10-minute sampling windows was also evaluated. The curated data set has been archived in a digital repository and is available online for others to test outlier-filtering algorithms.
9
Arhin, Stephen, Babin Manandhar, Hamdiat Baba Adam, and Adam Gatiba. Predicting Bus Travel Times in Washington, DC Using Artificial Neural Networks (ANNs). Mineta Transportation Institute, 2021. http://dx.doi.org/10.31979/mti.2021.1943.
Texto completoResumen
Washington, DC is ranked second among cities in terms of highest public transit commuters in the United States, with approximately 9% of the working population using the Washington Metropolitan Area Transit Authority (WMATA) Metrobuses to commute. Deducing accurate travel times of these metrobuses is an important task for transit authorities to provide reliable service to its patrons. This study, using Artificial Neural Networks (ANN), developed prediction models for transit buses to assist decision-makers to improve service quality and patronage. For this study, we used six months of Automatic Vehicle Location (AVL) and Automatic Passenger Counting (APC) data for six Washington Metropolitan Area Transit Authority (WMATA) bus routes operating in Washington, DC. We developed regression models and Artificial Neural Network (ANN) models for predicting travel times of buses for different peak periods (AM, Mid-Day and PM). Our analysis included variables such as number of served bus stops, length of route between bus stops, average number of passengers in the bus, average dwell time of buses, and number of intersections between bus stops. We obtained ANN models for travel times by using approximation technique incorporating two separate algorithms: Quasi-Newton and Levenberg-Marquardt. The training strategy for neural network models involved feed forward and errorback processes that minimized the generated errors. We also evaluated the models with a Comparison of the Normalized Squared Errors (NSE). From the results, we observed that the travel times of buses and the dwell times at bus stops generally increased over time of the day. We gathered travel time equations for buses for the AM, Mid-Day and PM Peaks. The lowest NSE for the AM, Mid-Day and PM Peak periods corresponded to training processes using Quasi-Newton algorithm, which had 3, 2 and 5 perceptron layers, respectively. These prediction models could be adapted by transit agencies to provide the patrons with accurate travel time information at bus stops or online.
10
Danylchuk, Hanna B., and Serhiy O. Semerikov. Advances in machine learning for the innovation economy: in the shadow of war. Криворізький державний педагогічний університет, 2023. http://dx.doi.org/10.31812/123456789/7732.
Texto completoResumen
This preface introduces the selected and revised papers presented at the 10th International Conference on Monitoring, Modeling & Management of Emergent Economy (M3E2 2022), held online in Ukraine, on November 17-18, 2022. The conference aimed to bring together researchers, practitioners, and students from various fields to exchange ideas, share experiences, and discuss challenges and opportunities in applying computational intelligence and data science for the innovation economy. The innovation economy is a term that describes the emerging paradigm of economic development that is driven by knowledge, creativity, and innovation. It requires new approaches and methods for solving complex problems, discovering new opportunities, and creating value in various domains of science, business,and society. Computational intelligence and data science are two key disciplines that can provide such approaches and methods by exploiting the power of data, algorithms, models, and systems to enable intelligent decision making, learning, adaptation, optimization, and discovery. The papers in this proceedings cover a wide range of topics related to computational intelligence and data science for the innovation economy. They include theoretical foundations, novel techniques, and innovative applications. The papers were selected and revised based on the feedback from the program committe members and reviewers who ensured their high quality. We would like to thank all the authors who submitted their papers to M3E2 2022. We also appreciate the keynote speakers who shared their insights and visions on the current trends and future directions of computational intelligence and data science for the innovation economy. We acknowledge the support of our sponsors, partners, and organizers who made this conference possible despite the challenging circumstances caused by the ongoing war in Ukraine. Finally, we thank all the participants who attended the conference online and contributed to its success.