Competitive analysis (online algorithm)

Analysis of algorithms | Online algorithms

Competitive analysis is a method invented for analyzing online algorithms, in which the performance of an online algorithm (which must satisfy an unpredictable sequence of requests, completing each request without being able to see the future) is compared to the performance of an optimal offline algorithm that can view the sequence of requests in advance. An algorithm is competitive if its competitive ratio—the ratio between its performance and the offline algorithm's performance—is bounded. Unlike traditional worst-case analysis, where the performance of an algorithm is measured only for "hard" inputs, competitive analysis requires that an algorithm perform well both on hard and easy inputs, where "hard" and "easy" are defined by the performance of the optimal offline algorithm. For many algorithms, performance is dependent not only on the size of the inputs, but also on their values. For example, sorting an array of elements varies in difficulty depending on the initial order. Such data-dependent algorithms are analysed for average-case and worst-case data. Competitive analysis is a way of doing worst case analysis for on-line and randomized algorithms, which are typically data dependent. In competitive analysis, one imagines an "adversary" which deliberately chooses difficult data, to maximize the ratio of the cost of the algorithm being studied and some optimal algorithm. When considering a randomized algorithm, one must further distinguish between an oblivious adversary, which has no knowledge of the random choices made by the algorithm pitted against it, and an adaptive adversary which has full knowledge of the algorithm's internal state at any point during its execution. (For a deterministic algorithm, there is no difference; either adversary can simply compute what state that algorithm must have at any time in the future, and choose difficult data accordingly.) For example, the quicksort algorithm chooses one element, called the "pivot", that is, on average, not too far from the center value of the data being sorted. Quicksort then separates the data into two piles, one of which contains all elements with value less than the value of the pivot, and the other containing the rest of the elements. If quicksort chooses the pivot in some deterministic fashion (for instance, always choosing the first element in the list), then it is easy for an adversary to arrange the data beforehand so that quicksort will perform in worst-case time. If, however, quicksort chooses some random element to be the pivot, then an adversary without knowledge of what random numbers are coming up cannot arrange the data to guarantee worst-case execution time for quicksort. The classic on-line problem first analysed with competitive analysis is the list update problem: Given a list of items and a sequence of requests for the various items, minimize the cost of accessing the list where the elements closer to the front of the list cost less to access. (Typically, the cost of accessing an item is equal to its position in the list.) After an access, the list may be rearranged. Most rearrangements have a cost. The Move-To-Front algorithm simply moves the requested item to the front after the access, at no cost. The Transpose algorithm swaps the accessed item with the item immediately before it, also at no cost. Classical methods of analysis showed that Transpose is optimal in certain contexts. In practice, Move-To-Front performed much better. Competitive analysis was used to show that an adversary can make Transpose perform arbitrarily badly compared to an optimal algorithm, whereas Move-To-Front can never be made to incur more than twice the cost of an optimal algorithm. In the case of online requests from a server, competitive algorithms are used to overcome uncertainties about the future. That is, the algorithm does not "know" the future, while the imaginary adversary (the "competitor") "knows". Similarly, competitive algorithms were developed for distributed systems, where the algorithm has to react to a request arriving at one location, without "knowing" what has just happened in a remote location. This setting was presented in. (Wikipedia).

Submitting a sitemap and getting your site indexed - Search Engine Optimization Tutorial part 2

This part of the tutorial aims to help you understand how Google ranks websites, how to submit a sitemap, and getting your website indexed.This video series aims to teach you the basics of Search Engine Optimization, or SEO. Sentdex.com Facebook.com/sentdex Twitter.com/sentdex

From playlist Search Engine Optimization

Algorithms In Industry - Intro to Algorithms

This video is part of an online course, Intro to Algorithms. Check out the course here: https://www.udacity.com/course/cs215.

From playlist Introduction to Algorithms

Pareto Analysis for Beginners in Excel

Check out the article on Pareto Analysis and download the Excel file here: https://magnimetrics.com/pareto-principle-in-financial-analysis/ Fill our survey for a FREE Benchmark Analysis template! https://forms.gle/A4MLhr7J5rRG1JBi8 If you like this video, drop a comment, give it a thumbs

From playlist Excel Tutorials

Greedy Algorithm | What Is Greedy Algorithm? | Introduction To Greedy Algorithms | Simplilearn

This video on the Greedy Algorithm will acquaint you with all the fundamentals of greedy programming paradigm. In this tutorial, you will learn 'What Is Greedy Algorithm?' with the help of suitable examples. And finally, you will also discover few important applications of greedy algorithm

From playlist Data Structures & Algorithms [2022 Updated]

Online and Recursive System Identification | System Identification, Part 4

Online system identification algorithms estimate the parameters and states of a model as new data is measured and available in real-time or near real-time. Brian Douglas covers what online system identification is, why it’s a good option for real-time situations, and the general ideas beh

From playlist System Identification

Discrete Math - 3.1.3 Sorting Algorithms

Bubble sort and insertion sort algorithms. Textbook: Rosen, Discrete Mathematics and Its Applications, 7e Playlist: https://www.youtube.com/playlist?list=PLl-gb0E4MII28GykmtuBXNUNoej-vY5Rz

From playlist Discrete Math I (Entire Course)

Conducting an Online Job Search

In this video, you’ll learn more about conducting an online job search. Visit https://www.gcflearnfree.org/jobsearchandnetworking/find-a-job-online/1/ to learn even more. We hope you enjoy!

From playlist Searching for a Job

Getting indexed in Bing & Yahoo - Search Engine Optimization Tutorial part 6

How to submit a sitemap to Bing.com in order to get indexed in Bing and Yahoo. Sentdex.com Facebook.com/sentdex Twitter.com/sentdex

From playlist Search Engine Optimization

Compute E Solution - Applied Cryptography

This video is part of an online course, Applied Cryptography. Check out the course here: https://www.udacity.com/course/cs387.

From playlist Applied Cryptography

Jarek Byrka: Online Facility Location with Linear Delay

From playlist Workshop: Approximation and Relaxation

Ola Svensson: Learning-Augmented Online Algorithms and the Primal-Dual Method

The design of learning-augmented online algorithms is a new and active research area. The goal is to understand how to best incorporate predictions of the future provided e.g. by machine learning algorithms that rarely come with guarantees on their accuracy. In the absence of guarantees, t

From playlist Workshop: Continuous approaches to discrete optimization

Lec 14 | MIT 6.046J / 18.410J Introduction to Algorithms (SMA 5503), Fall 2005

Lecture 14: Competitive Analysis: Self-organizing Lists View the complete course at: http://ocw.mit.edu/6-046JF05 License: Creative Commons BY-NC-SA More information at http://ocw.mit.edu/terms More courses at http://ocw.mit.edu

From playlist MIT 6.046J / 18.410J Introduction to Algorithms (SMA 5503),

Rico Zenklusen: The Submodular Secretary Problem Goes Linear

During the last decade, the matroid secretary problem (MSP) became one of the most prominent classes of online selection problems. The strong interest in MSPs is due to both its many applications and the fact that matroid constraints have useful properties for the design of strong online a

From playlist HIM Lectures 2015

Lecture 20 - Introduction to Online Algorithms

This is Lecture 20 of the COMP510 (Computational Finance) course taught by Professor Steven Skiena [http://www.cs.sunysb.edu/~skiena/] at Hong Kong University of Science and Technology in 2008. The lecture slides are available at: http://www.algorithm.cs.sunysb.edu/computationalfinance/pd

From playlist COMP510 - Computational Finance - 2007 HKUST

Online Bipartite Matching and Adwords - Vijay V. Vazirani

Computer Science/Discrete Mathematics Seminar I Topic: Online Bipartite Matching and Adwords Speaker: Vijay V. Vazirani Affiliation: University of California Irvine Date: March 21, 2022 Over the last three decades, the online bipartite matching (OBM) problem has emerged as a central prob

From playlist Mathematics

Online Parallel Paging and Green Paging

Abstract: The parallel paging problem captures the task of efficiently sharing a cache among multiple parallel processors. Whereas the single-processor version of the problem has been well understood for decades, it has remained an open question how to find optimal algorithms for the multi

From playlist SIAG-ACDA Online Seminar Series

Set Chasing, with an application to online shortest path - Sébastien Bubeck

Computer Science/Discrete Mathematics Seminar I Topic: Set Chasing, with an application to online shortest path Speaker: Sébastien Bubeck Affiliation: Microsoft Research Lab - Redmond Date: April 18, 2022 Since the late 19th century, mathematicians have realized the importance and genera

From playlist Mathematics

Sebastian Bubeck: Chasing small sets

I will present an approach based on mirror descent (with a time-varying multiscale entropy functional) to chase small sets in arbitrary metric spaces. This could in particular resolve the randomized competitive ratio of the layered graph traversal problem introduced by Papadimitriou and Ya

From playlist Workshop: Continuous approaches to discrete optimization

Model Optimization | Series Conclusion | Introduction to Text Analytics with R Part 12

This video concludes our Introduction to Text Analytics with R and covers: – Optimizing our model for the best generalizability on new/unseen data. – Discussion of the sensitivity/specificity tradeoff of our optimized model. – Potential next steps regarding feature engineering and algorit

From playlist Introduction to Text Analytics with R

Statistical Learning: 1.2 Examples and Framework

Statistical Learning, featuring Deep Learning, Survival Analysis and Multiple Testing You are able to take Statistical Learning as an online course on EdX, and you are able to choose a verified path and get a certificate for its completion: https://www.edx.org/course/statistical-learning

From playlist Statistical Learning

Competitive analysis (online algorithm)

Related pages