|
Online Optimization
Online optimization is a field of optimization theory, more popular in computer science and operations research, that deals with optimization problems having no or incomplete knowledge of the future (online). These kind of problems are denoted as online problems and are seen as opposed to the classical optimization problems where complete information is assumed (offline). The research on online optimization can be distinguished into online problems where multiple decisions are made sequentially based on a piece-by-piece input and those where a decision is made only once. A famous online problem where a decision is made only once is the Ski rental problem. In general, the output of an online algorithm is compared to the solution of a corresponding offline algorithm which is necessarily always optimal and knows the entire input in advance (competitive analysis). In many situations, present decisions (for example, resources allocation) must be made with incomplete knowledge of the futu ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Optimization
Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfields: discrete optimization and continuous optimization. Optimization problems of sorts arise in all quantitative disciplines from computer science and engineering to operations research and economics, and the development of solution methods has been of interest in mathematics for centuries. In the more general approach, an optimization problem consists of maxima and minima, maximizing or minimizing a Function of a real variable, real function by systematically choosing Argument of a function, input values from within an allowed set and computing the Value (mathematics), value of the function. The generalization of optimization theory and techniques to other formulations constitutes a large area of applied mathematics. More generally, opti ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Job Shop Scheduling
Job-shop scheduling, the job-shop problem (JSP) or job-shop scheduling problem (JSSP) is an optimization problem in computer science and operations research. It is a variant of optimal job scheduling. In a general job scheduling problem, we are given ''n'' jobs ''J''1, ''J''2, ..., ''Jn'' of varying processing times, which need to be scheduled on ''m'' machines with varying processing power, while trying to minimize the makespan – the total length of the schedule (that is, when all the jobs have finished processing). In the specific variant known as ''job-shop scheduling'', each job consists of a set of ''operations'' ''O''1, ''O''2, ..., ''On'' which need to be processed in a specific order (known as ''precedence constraints''). Each operation has a ''specific machine'' that it needs to be processed on and only one operation in a job can be processed at a given time. A common relaxation is the flexible job shop, where each operation can be processed on ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Online Mirror Descent
In mathematics, mirror descent is an iterative optimization algorithm for finding a local minimum of a differentiable function. It generalizes algorithms such as gradient descent and multiplicative weights. History Mirror descent was originally proposed by Nemirovski and Yudin in 1983. Motivation In gradient descent with the sequence of learning rates (\eta_n)_ applied to a differentiable function F, one starts with a guess \mathbf_0 for a local minimum of F, and considers the sequence \mathbf_0, \mathbf_1, \mathbf_2, \ldots such that :\mathbf_=\mathbf_n-\eta_n \nabla F(\mathbf_n),\ n \ge 0. This can be reformulated by noting that :\mathbf_=\arg \min_ \left(F(\mathbf_n) + \nabla F(\mathbf_n)^T (\mathbf - \mathbf_n) + \frac\, \mathbf - \mathbf_n\, ^2\right) In other words, \mathbf_ minimizes the first-order approximation to F at \mathbf_n with added proximity term \, \mathbf - \mathbf_n\, ^2. This Euclidean distance term is a particular example of a Bregman distance. Us ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Online Algorithm
In computer science, an online algorithm is one that can process its input piece-by-piece in a serial fashion, i.e., in the order that the input is fed to the algorithm, without having the entire input available from the start. In contrast, an offline algorithm is given the whole problem data from the beginning and is required to output an answer which solves the problem at hand. In operations research, the area in which online algorithms are developed is called online optimization. As an example, consider the sorting algorithms selection sort and insertion sort: selection sort repeatedly selects the minimum element from the unsorted remainder and places it at the front, which requires access to the entire input; it is thus an offline algorithm. On the other hand, insertion sort considers one input element per iteration and produces a partial solution without considering future elements. Thus insertion sort is an online algorithm. Note that the final result of an insertion sort ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Online Matching
In computer technology and telecommunications, online indicates a state of connectivity and offline indicates a disconnected state. In modern terminology, this usually refers to an Internet connection, but (especially when expressed "on line" or "on the line") could refer to any piece of equipment or functional unit that is connected to a larger system. Being online means that the equipment or subsystem is connected, or that it is ready for use. "Online" has come to describe activities performed on and data available on the Internet, for example: "online identity", "online predator", "online gambling", "online game", "online shopping", "online banking", and "online learning". Similar meaning is also given by the prefixes "cyber" and "e", as in the words "cyberspace", "cybercrime", "email", and "ecommerce". In contrast, "offline" can refer to either computing activities performed while disconnected from the Internet, or alternatives to Internet activities (such as shopping in bri ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Linear Search Problem
In computational complexity theory, the linear search problem is an optimal search problem introduced by Richard E. Bellman and independently considered by Anatole Beck. The problem "An immobile hider is located on the real line according to a known probability distribution. A searcher, whose maximal velocity is one, starts from the origin and wishes to discover the hider in minimal expected time. It is assumed that the searcher can change the direction of his motion without any loss of time. It is also assumed that the searcher cannot see the hider until he actually reaches the point at which the hider is located and the time elapsed until this moment is the duration of the game." In order to find the hider the searcher has to go a distance x1 in one direction, return to the origin and go distance x2 in the other direction etc., (the length of the n-th step being denoted by xn), and to do it in an optimal way. (However, an optimal solution need not have a first step and could sta ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Search Games
A search game is a two-person zero-sum game which takes place in a set called the search space. The searcher can choose any continuous trajectory subject to a maximal velocity constraint. It is always assumed that neither the searcher nor the hider has any knowledge about the movement of the other player until their distance apart is less than or equal to the discovery radius and at this very moment capture occurs. As mathematical models, search games can be applied to areas such as hide-and-seek games that children play or representations of some tactical military situations. The area of search games was introduced in the last chapter of Rufus Isaacs' classic book "Differential Games" and has been developed further by Shmuel GalS. Gal, ''Search Games'', Academic Press, New York (1980)S. Alpern and S. Gal, The Theory of Search Games and Rendezvous', Springer (2003). and Steve Alpern. The princess and monster game deals with a moving target. Strategy A natural strategy to search fo ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Secretary Problem
The secretary problem demonstrates a scenario involving optimal stopping theory For French translation, secover storyin the July issue of ''Pour la Science'' (2009). that is studied extensively in the fields of applied probability, statistics, and decision theory. It is also known as the marriage problem, the sultan's dowry problem, the fussy suitor problem, the googol game, and the best choice problem. The basic form of the problem is the following: imagine an administrator who wants to hire the best secretary out of n rankable applicants for a position. The applicants are interviewed one by one in random order. A decision about each particular applicant is to be made immediately after the interview. Once rejected, an applicant cannot be recalled. During the interview, the administrator gains information sufficient to rank the applicant among all applicants interviewed so far, but is unaware of the quality of yet unseen applicants. The question is about the optimal strategy ( sto ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Bandit Problem
In probability theory and machine learning, the multi-armed bandit problem (sometimes called the ''K''- or ''N''-armed bandit problem) is a problem in which a fixed limited set of resources must be allocated between competing (alternative) choices in a way that maximizes their expected gain, when each choice's properties are only partially known at the time of allocation, and may become better understood as time passes or by allocating resources to the choice. This is a classic reinforcement learning problem that exemplifies the exploration–exploitation tradeoff dilemma. The name comes from imagining a gambler at a row of slot machines (sometimes known as "one-armed bandits"), who has to decide which machines to play, how many times to play each machine and in which order to play them, and whether to continue with the current machine or try a different machine. The multi-armed bandit problem also falls into the broad category of stochastic scheduling. In the problem, each mach ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
List Update Problem
The List Update or the List Access problem is a simple model used in the study of competitive analysis of online algorithms. Given a set of items in a list where the cost of accessing an item is proportional to its distance from the head of the list, e.g. a Linked List, and a request sequence of accesses, the problem is to come up with a strategy of reordering the list so that the total cost of accesses is minimized. The reordering can be done at any time but incurs a cost. The standard model includes two reordering actions: * A free transposition of the item being accessed anywhere ahead of its current position; * A paid transposition of a unit cost for exchanging any two adjacent items in the list. Performance of algorithms depend on the construction of request sequences by adversaries under various Adversary models An online algorithm for this problem has to reorder the elements and serve requests based only on the knowledge of previously requested items and hence its strategy ma ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
K-server Problem
The -server problem is a problem of theoretical computer science in the category of online algorithms, one of two abstract problems on metric spaces that are central to the theory of competitive analysis (the other being metrical task systems). In this problem, an online algorithm must control the movement of a set of ''k'' ''servers'', represented as points in a metric space, and handle ''requests'' that are also in the form of points in the space. As each request arrives, the algorithm must determine which server to move to the requested point. The goal of the algorithm is to keep the total distance all servers move small, relative to the total distance the servers could have moved by an optimal adversary who knows in advance the entire sequence of requests. The problem was first posed by Mark Manasse, Lyle A. McGeoch and Daniel Sleator (1988). The most prominent open question concerning the ''k''-server problem is the so-called ''k''-server conjecture, also posed by Manasse e ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Computer Science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical disciplines (including the design and implementation of Computer architecture, hardware and Computer programming, software). Computer science is generally considered an area of research, academic research and distinct from computer programming. Algorithms and data structures are central to computer science. The theory of computation concerns abstract models of computation and general classes of computational problem, problems that can be solved using them. The fields of cryptography and computer security involve studying the means for secure communication and for preventing Vulnerability (computing), security vulnerabilities. Computer graphics (computer science), Computer graphics and computational geometry address the generation of images. Progr ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
