Добірка наукової літератури з теми "Competitive online algorithms"
Оформте джерело за APA, MLA, Chicago, Harvard та іншими стилями
Ознайомтеся зі списками актуальних статей, книг, дисертацій, тез та інших наукових джерел на тему "Competitive online algorithms".
Біля кожної праці в переліку літератури доступна кнопка «Додати до бібліографії». Скористайтеся нею – і ми автоматично оформимо бібліографічне посилання на обрану працю в потрібному вам стилі цитування: APA, MLA, «Гарвард», «Чикаго», «Ванкувер» тощо.
Також ви можете завантажити повний текст наукової публікації у форматі «.pdf» та прочитати онлайн анотацію до роботи, якщо відповідні параметри наявні в метаданих.
Статті в журналах з теми "Competitive online algorithms"
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.
Повний текст джерела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.
Повний текст джерела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.
Повний текст джерела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.
Повний текст джерела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.
Повний текст джерела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.
Повний текст джерела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.
Повний текст джерела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.
Повний текст джерела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.
Повний текст джерела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.
Повний текст джерелаДисертації з теми "Competitive online algorithms"
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.
Повний текст джерелаpublished_or_final_version
Computer Science
Doctoral
Doctor of Philosophy
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.
Повний текст джерела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.
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.
Повний текст джерелаpublished_or_final_version
Computer Science
Doctoral
Doctor of Philosophy
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.
Повний текст джерела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.
Повний текст джерелаNayyar, Krati. "Input Sensitive Analysis of a Minimum Metric Bipartite Matching Algorithm." Thesis, Virginia Tech, 2017. http://hdl.handle.net/10919/86518.
Повний текст джерелаMaster of Science
Gaspar, Cristian. "Variations on the Theme of Caching." Thesis, University of Waterloo, 2005. http://hdl.handle.net/10012/1048.
Повний текст джерела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.
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.
Повний текст джерела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
Luo, Lingzhi. "Distributed Algorithm Design for Constrained Multi-robot Task Assignment." Research Showcase @ CMU, 2014. http://repository.cmu.edu/dissertations/426.
Повний текст джерелаBender, Marco. "Randomized Approximation and Online Algorithms for Assignment Problems." Doctoral thesis, 2015. http://hdl.handle.net/11858/00-1735-0000-0022-6016-2.
Повний текст джерелаКниги з теми "Competitive online algorithms"
Borodin, Allan. Online computation and competitive analysis. Cambridge, [Eng.]: Cambridge University Press, 1998.
Знайти повний текст джерелаOnline Computation and Competitive Analysis. Cambridge University Press, 2005.
Знайти повний текст джерелаBuchbinder, Niv, and Joseph (Seffi) Naor. Design of Competitive Online Algorithms Via a Primal-Dual Approach. Now Publishers, 2009.
Знайти повний текст джерелаЧастини книг з теми "Competitive online algorithms"
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.
Повний текст джерелаIrani, Sandy. "Competitive analysis of paging." In Online Algorithms, 52–73. Berlin, Heidelberg: Springer Berlin Heidelberg, 1998. http://dx.doi.org/10.1007/bfb0029564.
Повний текст джерела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.
Повний текст джерела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.
Повний текст джерела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.
Повний текст джерела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.
Повний текст джерела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.
Повний текст джерела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.
Повний текст джерела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.
Повний текст джерела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.
Повний текст джерелаТези доповідей конференцій з теми "Competitive online algorithms"
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.
Повний текст джерела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.
Повний текст джерела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.
Повний текст джерелаChen, Lin, Nicole Megow та Kevin Schewior. "An ℴ(log m)-Competitive Algorithm for Online Machine Minimization". У 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.
Повний текст джерела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.
Повний текст джерела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.
Повний текст джерела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.
Повний текст джерела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.
Повний текст джерела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.
Повний текст джерела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.
Повний текст джерела