Relevant bibliographies by topics / Competitive online algorithms

Academic literature on the topic 'Competitive online algorithms'

Author: Grafiati
Published: 10 December 2022
Last updated: 28 January 2023

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

Select a source type:

Contents

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Competitive online algorithms.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "Competitive online algorithms"

1

Wu, Yonghua, Guohun Zhu, Huaying Chen, and Jucun Qin. "WIN Algorithm for Discrete Online TSP." Journal of Advanced Computational Intelligence and Intelligent Informatics 15, no. 9 (November 20, 2011): 1199–202. http://dx.doi.org/10.20965/jaciii.2011.p1199.

Full text
Abstract:
Traveling Salesman Problem (TSP) which is proved as an NP-Complete problem is solved by many algorithms. In this paper, we propose online TSP which is based on general discrete metric space. A Waiting-If-Necessary (WIN) algorithm is proposed that involves with increasing cost caused by zealous algorithms and unnecessary waiting caused by cautious algorithms. We measure the performance of the WIN algorithm using competitive analysis and found that it is a 2-competitive algorithm. The competitive ratio of theWIN algorithm can be improved by setting parameterT0.
APA, Harvard, Vancouver, ISO, and other styles
2

ZHANG, YONG, YUXIN WANG, FRANCIS Y. L. CHIN, and HING-FUNG TING. "COMPETITIVE ALGORITHMS FOR ONLINE PRICING." Discrete Mathematics, Algorithms and Applications 04, no. 02 (June 2012): 1250015. http://dx.doi.org/10.1142/s1793830912500152.

Full text
Abstract:
Given a seller with m items, a sequence of users {u1, u2, …} come one by one, the seller must set the unit price and assign some items to each user on his/her arrival. Items can be sold fractionally. Each ui has his/her value function vi(⋅) such that vi(x) is the highest unit price ui is willing to pay for x items. The objective is to maximize the revenue by setting the price and number of items for each user. In this paper, we have the following contributions: if the highest value h among all vi(x) is known in advance, we first show the lower bound of the competitive ratio is ⌊ log h⌋/2, then give an online algorithm with competitive ratio 4⌊ log h⌋ + 6; if h is not known in advance, we give an online algorithm with competitive ratio 2⋅h log -1/2 h + 8⋅h3 log -1/2 h.
APA, Harvard, Vancouver, ISO, and other styles
3

Kumar, Sandeep, and Deepak Garg. "Online Financial Algorithms: Competitive Analysis." International Journal of Computer Applications 40, no. 7 (February 29, 2012): 8–14. http://dx.doi.org/10.5120/4974-7228.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Ashlagi, Itai, Brendan Lucier, and Moshe Tennenholtz. "Equilibria of Online Scheduling Algorithms." Proceedings of the AAAI Conference on Artificial Intelligence 27, no. 1 (June 30, 2013): 67–73. http://dx.doi.org/10.1609/aaai.v27i1.8631.

Full text
Abstract:
We describe a model for competitive online scheduling algorithms. Two servers, each with a single observable queue, compete for customers. Upon arrival, each customer strategically chooses the queue with minimal expected wait time. Each scheduler wishes to maximize its number of customers, and can strategically select which scheduling algorithm, such as First-Come-First-Served (FCFS), to use for its queue. This induces a game played by the servers and the customers. We consider a non-Bayesian setting, where servers and customers play to maximize worst-case payoffs. We show that there is a unique subgame perfect safety-level equilibrium and we describe the associated scheduling algorithm (which is not FCFS). The uniqueness result holds for both randomized and deterministic algorithms, with a different equilibrium algorithm in each case. When the goal of the servers is to minimize competitive ratio, we prove that it is an equilibrium for each server to apply FCFS: each server obtains the optimal competitive ratio of 2.
APA, Harvard, Vancouver, ISO, and other styles
5

Hopf, Michael, Clemens Thielen, and Oliver Wendt. "Competitive algorithms for multistage online scheduling." European Journal of Operational Research 260, no. 2 (July 2017): 468–81. http://dx.doi.org/10.1016/j.ejor.2016.12.047.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Yang, Lin, Ali Zeynali, Mohammad H. Hajiesmaili, Ramesh K. Sitaraman, and Don Towsley. "Competitive Algorithms for Online Multidimensional Knapsack Problems." Proceedings of the ACM on Measurement and Analysis of Computing Systems 5, no. 3 (December 14, 2021): 1–30. http://dx.doi.org/10.1145/3491042.

Full text
Abstract:
In this paper, we study the online multidimensional knapsack problem (called OMdKP) in which there is a knapsack whose capacity is represented in m dimensions, each dimension could have a different capacity. Then, n items with different scalar profit values and m-dimensional weights arrive in an online manner and the goal is to admit or decline items upon their arrival such that the total profit obtained by admitted items is maximized and the capacity of knapsack across all dimensions is respected. This is a natural generalization of the classic single-dimension knapsack problem and finds several relevant applications such as in virtual machine allocation, job scheduling, and all-or-nothing flow maximization over a graph. We develop two algorithms for OMdKP that use linear and exponential reservation functions to make online admission decisions. Our competitive analysis shows that the linear and exponential algorithms achieve the competitive ratios of O(θα ) and O(łogł(θα)), respectively, where α is the ratio between the aggregate knapsack capacity and the minimum capacity over a single dimension and θ is the ratio between the maximum and minimum item unit values. We also characterize a lower bound for the competitive ratio of any online algorithm solving OMdKP and show that the competitive ratio of our algorithm with exponential reservation function matches the lower bound up to a constant factor.
APA, Harvard, Vancouver, ISO, and other styles
7

Lee, Russell, Jessica Maghakian, Mohammad Hajiesmaili, Jian Li, Ramesh Sitaraman, and Zhenhua Liu. "Online peak-aware energy scheduling with untrusted advice." ACM SIGEnergy Energy Informatics Review 1, no. 1 (November 2021): 59–77. http://dx.doi.org/10.1145/3508467.3508473.

Full text
Abstract:
This paper studies the online energy scheduling problem in a hybrid model where the cost of energy is proportional to both the volume and peak usage, and where energy can be either locally generated or drawn from the grid. Inspired by recent advances in online algorithms with Machine Learned (ML) advice, we develop parameterized deterministic and randomized algorithms for this problem such that the level of reliance on the advice can be adjusted by a trust parameter. We then analyze the performance of the proposed algorithms using two performance metrics: robustness that measures the competitive ratio as a function of the trust parameter when the advice is inaccurate, and consistency for competitive ratio when the advice is accurate. Since the competitive ratio is analyzed in two different regimes, we further investigate the Pareto optimality of the proposed algorithms. Our results show that the proposed deterministic algorithm is Pareto-optimal, in the sense that no other online deterministic algorithms can dominate the robustness and consistency of our algorithm. Furthermore, we show that the proposed randomized algorithm dominates the Pareto-optimal deterministic algorithm. Our large-scale empirical evaluations using real traces of energy demand, energy prices, and renewable energy generations highlight that the proposed algorithms outperform worst-case optimized algorithms and fully data-driven algorithms.
APA, Harvard, Vancouver, ISO, and other styles
8

Xu, Chenyang, and Benjamin Moseley. "Learning-Augmented Algorithms for Online Steiner Tree." Proceedings of the AAAI Conference on Artificial Intelligence 36, no. 8 (June 28, 2022): 8744–52. http://dx.doi.org/10.1609/aaai.v36i8.20854.

Full text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
9

Ma, Hang. "A Competitive Analysis of Online Multi-Agent Path Finding." Proceedings of the International Conference on Automated Planning and Scheduling 31 (May 17, 2021): 234–42. http://dx.doi.org/10.1609/icaps.v31i1.15967.

Full text
Abstract:
We study online Multi-Agent Path Finding (MAPF), where new agents are constantly revealed over time and all agents must find collision-free paths to their given goal locations. We generalize existing complexity results of (offline) MAPF to online MAPF. We classify online MAPF algorithms into different categories based on (1) controllability (the set of agents that they can plan paths for at each time) and (2) rationality (the quality of paths they plan) and study the relationships between them. We perform a competitive analysis for each category of online MAPF algorithms with respect to commonly-used objective functions. We show that a naive algorithm that routes newly-revealed agents one at a time in sequence achieves a competitive ratio that is asymptotically bounded from both below and above by the number of agents with respect to flowtime and makespan. We then show a counter-intuitive result that, if rerouting of previously-revealed agents is not allowed, any rational online MAPF algorithms, including ones that plan optimal paths for all newly-revealed agents, have the same asymptotic competitive ratio as the naive algorithm, even on 2D 4-neighbor grids. We also derive constant lower bounds on the competitive ratio of any rational online MAPF algorithms that allow rerouting. The results thus provide theoretical insights into the effectiveness of using MAPF algorithms in an online setting for the first time.
APA, Harvard, Vancouver, ISO, and other styles
10

Yang, Lin, Ali Zeynali, Mohammad H. Hajiesmaili, Ramesh K. Sitaraman, and Don Towsley. "Competitive Algorithms for Online Multidimensional Knapsack Problems." ACM SIGMETRICS Performance Evaluation Review 50, no. 1 (June 20, 2022): 87–88. http://dx.doi.org/10.1145/3547353.3522627.

Full text
Abstract:
In this work, we study the online multidimensional knapsack problem (called OMdKP) in which there is a knapsack whose capacity is represented in m dimensions, each dimension could have a different capacity. Then, n items with different scalar profit values and m-dimensional weights arrive in an online manner and the goal is to admit or decline items upon their arrival such that the total profit obtained by admitted items is maximized and the capacity of knapsack across all dimensions is respected. This is a natural generalization of the classic single-dimension knapsack problem with several relevant applications such as in virtual machine allocation, job scheduling, and all-or-nothing flow maximization over a graph. We develop an online algorithm for OMdKP that uses an exponential reservation function to make online admission decisions. Our competitive analysis shows that the proposed online algorithm achieves the competitive ratio of O(log (Θ α)), where α is the ratio between the aggregate knapsack capacity and the minimum capacity over a single dimension and θ is the ratio between the maximum and minimum item unit values. We also show that the competitive ratio of our algorithm with exponential reservation function matches the lower bound up to a constant factor.
APA, Harvard, Vancouver, ISO, and other styles
More sources

Dissertations / Theses on the topic "Competitive online algorithms"

1

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

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

Wong, Chiu Wai M. Eng Massachusetts Institute of Technology. "Competitive algorithms for online matching and vertex cover problems." Thesis, Massachusetts Institute of Technology, 2013. http://hdl.handle.net/1721.1/85521.

Full text
Abstract:
Thesis: M. Eng., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2013.
Cataloged from PDF version of thesis.
Includes bibliographical references (pages 73-75).
The past decade has witnessed an explosion of research on the online bipartite matching problem. Surprisingly, its dual problem, online bipartite vertex cover, has never been explicitly studied before. One of the motivation for studying this problem is that it significantly generalizes the classical ski rental problem. An instance of such problems specifies a bipartite graph G = (L, R, E) whose left vertices L are offline and right vertices arrive online one at a time. An algorithm must maintain a valid vertex cover from which no vertex can ever be removed. The objective is to minimize the size of the cover. In this thesis, we introduce a charging-based algorithmic framework for this problem as well as its generalizations. One immediate outcome is a simple analysis of an optimal 1/1-1/e- competitive algorithm for online bipartite vertex cover. By extending the charging-based analysis in various nontrivial ways, we also obtain optimal l_1 e-competitive algorithms for the edge-weighted and submodular versions of online bipartite vertex cover, which all match the best performance of ski rental. As an application, we show that by analyzing our algorithm in the primal-dual framework, our result on submodular vertex cover implies an optimal (1/1-1/e)-competitive algorithm for its dual, online bipartite submodular matching. This problem is a generalization of online bipartite matching and may have applications in display ad allocation. We consider also the more general scenario where all the vertices are online and the graph is not necessarily bipartite, which is known as the online fractional vertex cover and matching problems. Our contribution in this direction is a primal-dual 1.901-competitive (or 1/1.901 ~~ 0.526) algorithm for these problems. Previously, it was only known that they admit a simple well-known 2-competitive (or 1/2) greedy algorithm. Our result is the first successful attempt to beat the greedy algorithm for these two problems. Moreover, our algorithm for the online matching problem significantly generalizes the traditional online bipartite graph matching problem, where vertices from only one side of the bipartite graph arrive online. In particular, our algorithm improves upon the result of the fractional version of the online edge-selection problem in Blum et. al. (JACM '06). Finally, on the hardness side, we show that no randomized online algorithm can achieve a competitive ratio better than 1.753 and 0.625 for the online fractional vertex cover problem and the online fractional matching problem respectively, even for bipartite graphs.
by Chiu Wai Wong.
M. Eng.
APA, Harvard, Vancouver, ISO, and other styles
3

Chan, Sze-hang, and 陳思行. "Competitive online job scheduling algorithms under different energy management models." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2013. http://hdl.handle.net/10722/206690.

Full text
Abstract:
Online flow-time scheduling is a fundamental problem in computer science and has been extensively studied for years. It is about how to design a scheduler to serve computer jobs with unpredictable arrival times and varying sizes and priorities so as to minimize the total flow time (better understood as response time) of jobs. It has many applications, most notable in the operating of server farms. As energy has become an important issue, the design of scheduler also has to take power management into consideration, for example, how to scale the speed of the processors dynamically. The objectives are orthogonal as one would prefer lower processor speed to save energy, yet a good quality of service must be retained. In this thesis, I study a few scheduling problems for energy and flow time in depth and give new algorithms to tackle them. The competitiveness of our algorithms is guaranteed with worst-case mathematical analysis against the best possible or hypothetical solutions. In the speed scaling model, the power of a processor increases with its speed according to a certain function (e.g., a cubic function of speed). Among all online scheduling problems with speed scaling, the nonclairvoyant setting (in which the size of a job is not known during its execution) with arbitrary priorities is perhaps the most challenging. This thesis gives the first competitive algorithm called WLAPS for this setting. In reality, it is not uncommon that during the peak-load period, some (low-priority) users have their jobs rejected by the servers. This triggers me to study more complicated scheduling algorithms that can strike a good balance among speed scaling, flow time and rejection penalty. Two new algorithms UPUW and HDFAC for different models of rejection penalty have been proposed and analyzed. Last, but perhaps the most interesting, we study power management in large server farm environment in which the primary energy saving mechanism is to put some processors to sleep. Two new algorithms POOL and SATA have been designed to tackle jobs that cannot and can migrate among the processors, respectively. They are integrated algorithms that can consider speed scaling, job scheduling and processor sleep management together to optimize the energy usage and ow time simultaneously. These algorithms are again proven mathematically to be competitive even in the worst case.
published_or_final_version
Computer Science
Doctoral
Doctor of Philosophy
APA, Harvard, Vancouver, ISO, and other styles
4

Lorenz, Julian Michael. "Optimal trading algorithms : portfolio transactions, multiperiod portfolio selection, and competitive online search /." Zürich : ETH, 2008. http://e-collection.ethbib.ethz.ch/show?type=diss&nr=17746.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

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

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

Nayyar, Krati. "Input Sensitive Analysis of a Minimum Metric Bipartite Matching Algorithm." Thesis, Virginia Tech, 2017. http://hdl.handle.net/10919/86518.

Full text
Abstract:
In various business and military settings, there is an expectation of on-demand delivery of supplies and services. Typically, several delivery vehicles (also called servers) carry these supplies. Requests arrive one at a time and when a request arrives, a server is assigned to this request at a cost that is proportional to the distance between the server and the request. Bad assignments will not only lead to larger costs but will also create bottlenecks by increasing delivery time. There is, therefore, a need to design decision-making algorithms that produce cost-effective assignments of servers to requests in real-time. In this thesis, we consider the online bipartite matching problem where each server can serve exactly one request. In the online minimum metric bipartite matching problem, we are provided with a set of server locations in a metric space. Requests arrive one at a time that have to be immediately and irrevocably matched to a free server. The total cost of matching all the requests to servers, also known as the online matching is the sum of the cost of all the edges in the matching. There are many well-studied models for request generation. We study the problem in the adversarial model where an adversary who knows the decisions made by the algorithm generates a request sequence to maximize ratio of the cost of the online matching and the minimum-cost matching (also called the competitive ratio). An algorithm is a-competitive if the cost of online matching is at most 'a' times the minimum cost. A recently discovered robust and deterministic online algorithm (we refer to this as the robust matching or the RM-Algorithm) was shown to have optimal competitive ratios in the adversarial model and a relatively weaker random arrival model. We extend the analysis of the RM-Algorithm in the adversarial model and show that the competitive ratio of the algorithm is sensitive to the input, i.e., for "nice" input metric spaces or "nice" server placements, the performance guarantees of the RM-Algorithm is significantly better. In fact, we show that the performance is almost optimal for any fixed metric space and server locations.
Master of Science
APA, Harvard, Vancouver, ISO, and other styles
7

Gaspar, Cristian. "Variations on the Theme of Caching." Thesis, University of Waterloo, 2005. http://hdl.handle.net/10012/1048.

Full text
Abstract:
This thesis is concerned with caching algorithms. We investigate three variations of the caching problem: web caching in the Torng framework, relative competitiveness and caching with request reordering.

In the first variation we define different cost models involving page sizes and page costs. We also present the Torng cost framework introduced by Torng in [29]. Next we analyze the competitive ratio of online deterministic marking algorithms in the BIT cost model combined with the Torng framework. We show that given some specific restrictions on the set of possible request sequences, any marking algorithm is 2-competitive.

The second variation consists in using the relative competitiveness ratio on an access graph as a complexity measure. We use the concept of access graphs introduced by Borodin [11] to define our own concept of relative competitive ratio. We demonstrate results regarding the relative competitiveness of two cache eviction policies in both the basic and the Torng framework combined with the CLASSICAL cost model.

The third variation is caching with request reordering. Two reordering models are defined. We prove some important results about the value of a move and number of orderings, then demonstrate results about the approximation factor and competitive ratio of offline and online reordering schemes, respectively.
APA, Harvard, Vancouver, ISO, and other styles
8

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

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

Luo, Lingzhi. "Distributed Algorithm Design for Constrained Multi-robot Task Assignment." Research Showcase @ CMU, 2014. http://repository.cmu.edu/dissertations/426.

Full text
Abstract:
The task assignment problem is one of the fundamental combinatorial optimization problems. It has been extensively studied in operation research, management science, computer science and robotics. Task assignment problems arise in various applications of multi-robot systems (MRS), such as environmental monitoring, disaster response, extraterrestrial exploration, sensing data collection and collaborative autonomous manufacturing. In these MRS applications, there are realistic constraints on robots and tasks that must be taken into account both from the modeling perspective and the algorithmic perspective. From the modeling aspect, such constraints include (a) Task group constraints: where tasks form disjoint groups and each robot can be assigned to at most one task in each group. One example of the group constraints comes from tightly-coupled tasks, where multiple micro tasks form one tightly-coupled macro task and need multiple robots to perform each simultaneously. (b) Task deadline constraints: where tasks must be assigned to meet their deadlines. (c) Dynamically-arising tasks: where tasks arrive dynamically and the payoffs of future tasks are unknown. Such tasks arise in scenarios like searchrescue, where new victims are found dynamically. (d) Robot budget constraints: where the number of tasks each robot can perform is bounded according to the resource it possesses (e.g., energy). From the solution aspect, there is often a need for decentralized solution that are implemented on individual robots, especially when no powerful centralized controller exists or when the system needs to avoid single-point failure or be adaptive to environmental changes. Most existing algorithms either do not consider the above constraints in problem modeling, are centralized or do not provide formal performance guarantees. In this thesis, I propose methods to address these issues for two classes of problems, namely, the constrained linear assignment problem and constrained generalized assignment problem. Constrained linear assignment problem belongs to P, while constrained generalized assignment problem is NP-hard. I develop decomposition-based distributed auction algorithms with performance guarantees for both problem classes. The multi-robot assignment problem is decomposed into an optimization problem for each robot and each robot iteratively solving its own optimization problem leads to a provably good solution to the overall problem. For constrained linear assignment problem, my approaches provides an almost optimal solution. For constrained generalized assignment problem, I present a distributed algorithm that provides a solution within a constant factor of the optimal solution. I also study the online version of the task allocation problem with task group constraints. For the online problem, I prove that a repeated greedy version of my algorithm gives solution with constant factor competitive ratio. I include simulation results to evaluate the average-case performance of the proposed algorithms. I also include results on multi-robot cooperative package transport to illustrate the approach.
APA, Harvard, Vancouver, ISO, and other styles
10

Bender, Marco. "Randomized Approximation and Online Algorithms for Assignment Problems." Doctoral thesis, 2015. http://hdl.handle.net/11858/00-1735-0000-0022-6016-2.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Books on the topic "Competitive online algorithms"

1

Borodin, Allan. Online computation and competitive analysis. Cambridge, [Eng.]: Cambridge University Press, 1998.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
2

Online Computation and Competitive Analysis. Cambridge University Press, 2005.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
3

Buchbinder, Niv, and Joseph (Seffi) Naor. Design of Competitive Online Algorithms Via a Primal-Dual Approach. Now Publishers, 2009.

Find full text
APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "Competitive online algorithms"

1

Fiat, Amos, and Gerhard J. Woeginger. "Competitive analysis of algorithms." In Online Algorithms, 1–12. Berlin, Heidelberg: Springer Berlin Heidelberg, 1998. http://dx.doi.org/10.1007/bfb0029562.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Irani, Sandy. "Competitive analysis of paging." In Online Algorithms, 52–73. Berlin, Heidelberg: Springer Berlin Heidelberg, 1998. http://dx.doi.org/10.1007/bfb0029564.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Fiat, Amos, and Gerhard J. Woeginger. "Competitive odds and ends." In Online Algorithms, 385–94. Berlin, Heidelberg: Springer Berlin Heidelberg, 1998. http://dx.doi.org/10.1007/bfb0029578.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Aspnes, James. "Competitive analysis of distributed algorithms." In Online Algorithms, 118–46. Berlin, Heidelberg: Springer Berlin Heidelberg, 1998. http://dx.doi.org/10.1007/bfb0029567.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

El-Yaniv, Ran. "Competitive solutions for on-line financial problems." In Online Algorithms, 326–72. Berlin, Heidelberg: Springer Berlin Heidelberg, 1998. http://dx.doi.org/10.1007/bfb0029576.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Karlin, Anna R. "On the performance of competitive algorithms in practice." In Online Algorithms, 373–84. Berlin, Heidelberg: Springer Berlin Heidelberg, 1998. http://dx.doi.org/10.1007/bfb0029577.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Harks, Tobias, Stefan Heinz, and Marc E. Pfetsch. "Competitive Online Multicommodity Routing." In Approximation and Online Algorithms, 240–52. Berlin, Heidelberg: Springer Berlin Heidelberg, 2007. http://dx.doi.org/10.1007/11970125_19.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Mansour, Yishay, Boaz Patt-Shamir, and Dror Rawitz. "Competitive Router Scheduling with Structured Data." In Approximation and Online Algorithms, 219–32. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012. http://dx.doi.org/10.1007/978-3-642-29116-6_19.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Zhang, Yong, Francis Y. L. Chin, and Hing-Fung Ting. "Competitive Algorithms for Online Pricing." In Lecture Notes in Computer Science, 391–401. Berlin, Heidelberg: Springer Berlin Heidelberg, 2011. http://dx.doi.org/10.1007/978-3-642-22685-4_35.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Tauer, Bjoern, and Laura Vargas Koch. "FIFO and Randomized Competitive Packet Routing Games." In Approximation and Online Algorithms, 165–87. Cham: Springer International Publishing, 2021. http://dx.doi.org/10.1007/978-3-030-92702-8_11.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Competitive online algorithms"

1

Jinhong Xu, Weijun Xu, Jinling Li, and Yucheng Dong. "Competitive Algorithms about Online Reverse Auctions." In 2008 IEEE Congress on Evolutionary Computation (CEC). IEEE, 2008. http://dx.doi.org/10.1109/cec.2008.4631185.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Yang, Lin, Ali Zeynali, Mohammad H. Hajiesmaili, Ramesh K. Sitaraman, and Don Towsley. "Competitive Algorithms for Online Multidimensional Knapsack Problems." In SIGMETRICS/PERFORMANCE '22: ACM SIGMETRICS/IFIP PERFORMANCE Joint International Conference on Measurement and Modeling of Computer Systems. New York, NY, USA: ACM, 2022. http://dx.doi.org/10.1145/3489048.3522627.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Buchbinder, Niv, Moran Feldman, Joseph (Seffi) Naor, and Ohad Talmon. "O(depth)-Competitive Algorithm for Online Multi-level Aggregation." In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2017. http://dx.doi.org/10.1137/1.9781611974782.80.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Chen, Lin, Nicole Megow, and Kevin Schewior. "An ℴ(log m)-Competitive Algorithm for Online Machine Minimization." In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2015. http://dx.doi.org/10.1137/1.9781611974331.ch12.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Günther, Elisabeth, Olaf Maurer, Nicole Megow, and Andreas Wiese. "A New Approach to Online Scheduling: Approximating the Optimal Competitive Ratio." In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2013. http://dx.doi.org/10.1137/1.9781611973105.9.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Menati, Ali, Sid Chi-Kin Chau, and Minghua Chen. "Competitive prediction-aware online algorithms for energy generation scheduling in microgrids." In e-Energy '22: The Thirteenth ACM International Conference on Future Energy Systems. New York, NY, USA: ACM, 2022. http://dx.doi.org/10.1145/3538637.3538867.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Alinia, Bahram, Mohammad Sadegh Talebi, Mohammad H. Hajiesmaili, Ali Yekkehkhany, and Noel Crespi. "Competitive Online Scheduling Algorithms with Applications in Deadline-Constrained EV Charging." In 2018 IEEE/ACM 26th International Symposium on Quality of Service (IWQoS). IEEE, 2018. http://dx.doi.org/10.1109/iwqos.2018.8624184.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Cao, Ying, Bo Sun, and Danny H. K. Tsang. "Optimal Online Algorithms for One-Way Trading and Online Knapsack Problems: A Unified Competitive Analysis." In 2020 59th IEEE Conference on Decision and Control (CDC). IEEE, 2020. http://dx.doi.org/10.1109/cdc42340.2020.9303856.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

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.

Full text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
10

Bahmani, Bahman, Aranyak Mehta, and Rajeev Motwani. "A 1.43-Competitive Online Graph Edge Coloring Algorithm In The Random Order Arrival Model." In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2010. http://dx.doi.org/10.1137/1.9781611973075.4.

Full text
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the extended bibliographies on the topic 'Competitive online algorithms' for particular source types:
Journal articles
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography