|
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] |
Theoretical Computer Science
Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory. It is difficult to circumscribe the theoretical areas precisely. The Association for Computing Machinery, ACM's ACM SIGACT, Special Interest Group on Algorithms and Computation Theory (SIGACT) provides the following description: History While logical inference and mathematical proof had existed previously, in 1931 Kurt Gödel proved with his incompleteness theorem that there are fundamental limitations on what statements could be proved or disproved. Information theory was added to the field with a 1948 mathematical theory of communication by Claude Shannon. In the same decade, Donald Hebb introduced a mathematical model of Hebbian learning, learning in the brain. With mounting biological data supporting this hypothesis with some modification, the fields of n ... [...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] |
Metric Space
In mathematics, a metric space is a set together with a notion of ''distance'' between its elements, usually called points. The distance is measured by a function called a metric or distance function. Metric spaces are the most general setting for studying many of the concepts of mathematical analysis and geometry. The most familiar example of a metric space is 3-dimensional Euclidean space with its usual notion of distance. Other well-known examples are a sphere equipped with the angular distance and the hyperbolic plane. A metric may correspond to a metaphorical, rather than physical, notion of distance: for example, the set of 100-character Unicode strings can be equipped with the Hamming distance, which measures the number of characters that need to be changed to get from one string to another. Since they are very general, metric spaces are a tool used in many different branches of mathematics. Many types of mathematical objects have a natural notion of distance and t ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Competitive Analysis (online Algorithm)
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 ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Metrical Task Systems
Task systems are mathematical objects used to model the set of possible configuration of online algorithms. They were introduced by Borodin, Linial and Saks (1992) to model a variety of online problems. A task system determines a set of states and costs to change states. Task systems obtain as input a sequence of requests such that each request assigns processing times to the states. The objective of an online algorithm for task systems is to create a schedule that minimizes the overall cost incurred due to processing the tasks with respect to the states and due to the cost to change states. If the cost function to change states is a metric, the task system is a metrical task system (MTS). This is the most common type of task systems. Metrical task systems generalize online problems such as paging, list accessing, and the k-server problem (in finite spaces). Formal Definition A task system is a pair (S,d) where S=\ is a set of states and d:S \times S \rightarrow \mathbb is a dis ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Mark Manasse
Mark may refer to: Currency * Bosnia and Herzegovina convertible mark, the currency of Bosnia and Herzegovina * East German mark, the currency of the German Democratic Republic * Estonian mark, the currency of Estonia between 1918 and 1927 * Finnish markka ( sv, finsk mark, links=no), the currency of Finland from 1860 until 28 February 2002 * Mark (currency), a currency or unit of account in many nations * Polish mark ( pl, marka polska, links=no), the currency of the Kingdom of Poland and of the Republic of Poland between 1917 and 1924 German * Deutsche Mark, the official currency of West Germany from 1948 until 1990 and later the unified Germany from 1990 until 2002 * German gold mark, the currency used in the German Empire from 1873 to 1914 * German Papiermark, the German currency from 4 August 1914 * German rentenmark, a currency issued on 15 November 1923 to stop the hyperinflation of 1922 and 1923 in Weimar Germany * Lodz Ghetto mark, a special currency for Lodz Ghetto. ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Daniel Sleator
Daniel Dominic Kaplan Sleator (born 10 December 1953) is a Professor of Computer Science at Carnegie Mellon University, Pittsburgh, United States. In 1999, he won the ACM Paris Kanellakis Award (jointly with Robert Tarjan) for the splay tree data structure. He was one of the pioneers in amortized analysis of algorithms, early examples of which were the analyses of the move-to-front heuristic, and splay trees. He invented many data structures with Robert Tarjan, such as splay trees, link/cut trees, and skew heaps. The Sleator and Tarjan paper on the move-to-front heuristic first suggested the idea of comparing an online algorithm to an optimal offline algorithm, for which the term competitive analysis was later coined in a paper of Karlin, Manasse, Rudolph, and Sleator. Sleator also developed the theory of link grammars, and the Serioso music analyzer for analyzing meter and harmony in written music. Personal life Sleator was born to William Warner Sleator, Jr., a profess ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Marek Chrobak
Marek Chrobak is a full professor at University of California, Riverside. He is known for his work Competitive analysis (online algorithm), competitive analysis of online algorithms, particularly for the k-server problem, on information dissemination in ad-hoc radio networks, and on graph drawing. In automata theory, Chrobak is known for his contributions to the study of finite automata over a one-letter alphabet. In particular, "Chrobak normal form" for nondeterministic finite automata is known. Chrobak obtained his PhD in Computer Science from Warsaw University in 1985. References External links * *Bibliography of papers on online algorithms * * * * * Year of birth missing (living people) Living people University of California, Riverside faculty University of Warsaw alumni {{US-academic-bio-stub ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Lawrence L
Lawrence may refer to: Education Colleges and universities * Lawrence Technological University, a university in Southfield, Michigan, United States * Lawrence University, a liberal arts university in Appleton, Wisconsin, United States Preparatory & high schools * Lawrence Academy at Groton, a preparatory school in Groton, Massachusetts, United States * Lawrence College, Ghora Gali, a high school in Pakistan * Lawrence School, Lovedale, a high school in India * The Lawrence School, Sanawar, a high school in India Research laboratories * Lawrence Berkeley National Laboratory, United States * Lawrence Livermore National Laboratory, United States People * Lawrence (given name), including a list of people with the name * Lawrence (surname), including a list of people with the name * Lawrence (band), an American soul-pop group * Lawrence (judge royal) (died after 1180), Hungarian nobleman, Judge royal 1164–1172 * Lawrence (musician), Lawrence Hayward (born 1961), British musician * ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Page Replacement Algorithm
In a computer operating system that uses paging for virtual memory management, page replacement algorithms decide which memory pages to page out, sometimes called swap out, or write to disk, when a page of memory needs to be allocated. Page replacement happens when a requested page is not in memory (page fault) and a free page cannot be used to satisfy the allocation, either because there are none, or because the number of free pages is lower than some threshold. When the page that was selected for replacement and paged out is referenced again it has to be paged in (read in from disk), and this involves waiting for I/O completion. This determines the ''quality'' of the page replacement algorithm: the less time waiting for page-ins, the better the algorithm. A page replacement algorithm looks at the limited information about accesses to the pages provided by hardware, and tries to guess which pages should be replaced to minimize the total number of page misses, while balancing thi ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Robert Tarjan
Robert Endre Tarjan (born April 30, 1948) is an American computer scientist and mathematician. He is the discoverer of several graph algorithms, including Tarjan's off-line lowest common ancestors algorithm, and co-inventor of both splay trees and Fibonacci heaps. Tarjan is currently the James S. McDonnell Distinguished University Professor of Computer Science at Princeton University, and the Chief Scientist at Intertrust Technologies Corporation. Early life and education He was born in Pomona, California. His father, raised in Hungary, was a child psychiatrist, specializing in mental retardation, and ran a state hospital. As a child, Tarjan read a lot of science fiction, and wanted to be an astronomer. He became interested in mathematics after reading Martin Gardner's mathematical games column in Scientific American. He became seriously interested in math in the eighth grade, thanks to a "very stimulating" teacher. While he was in high school, Tarjan got a job, where he work ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Christos Papadimitriou
Christos Charilaos Papadimitriou ( el, Χρήστος Χαρίλαος "Χρίστος" Παπαδημητρίου; born August 16, 1949) is a Greek theoretical computer scientist and the Donovan Family Professor of Computer Science at Columbia University. Education Papadimitriou studied at the National Technical University of Athens, where in 1972 he received his Bachelor of Arts degree in electrical engineering. He then pursued graduate studies at Princeton University, where he received his Ph.D. in electrical engineering and computer science in 1976 after completing a doctoral dissertation titled "The complexity of combinatorial optimization problems." Career Papadimitriou has taught at Harvard, MIT, the National Technical University of Athens, Stanford, UCSD, University of California, Berkeley and is currently the Donovan Family Professor of Computer Science at Columbia University. Papadimitriou co-authored a paper on pancake sorting with Bill Gates, then a Harvard undergra ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
