|
Discrepancy Of Permutations
Discrepancy of permutations is a sub-field of discrepancy theory, that deals with balancing intervals induced by permutations of elements. There is a set of ''n'' elements, and there are m different permutations on this set. The general research question is: can we color each element in one of two different colors (e.g. black and white), such that in each permutation, every interval contains roughly the same number of elements of each color? Formally, the ''discrepancy'' of an interval is defined as the difference between the number of white elements and the number of black elements in that interval; the objective is to color the elements such that the maximum discrepancy of an interval in each of the permutations is as small as possible. Definitions Let ''p''1, ...,''pm'' be permutations of 'n'' The ''interval set'' of a permutation is the set of all subsets of 'n'' that are adjacent to each other in the permutation. For example, if ''n''=4 and one of the permutations is (1, ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Discrepancy Theory
In mathematics, discrepancy theory describes the deviation of a situation from the state one would like it to be in. It is also called the theory of irregularities of distribution. This refers to the theme of ''classical'' discrepancy theory, namely distributing points in some space such that they are evenly distributed with respect to some (mostly geometrically defined) subsets. The discrepancy (irregularity) measures how far a given distribution deviates from an ideal one. Discrepancy theory can be described as the study of inevitable irregularities of distributions, in measure-theoretic and combinatorial settings. Just as Ramsey theory elucidates the impossibility of total disorder, discrepancy theory studies the deviations from total uniformity. A significant event in the history of discrepancy theory was the 1916 paper of Weyl on the uniform distribution of sequences in the unit interval. __NOTOC__ Theorems Discrepancy theory is based on the following classic theorems: * T ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Permutation
In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or process of changing the linear order of an ordered set. Permutations differ from combinations, which are selections of some members of a set regardless of order. For example, written as tuples, there are six permutations of the set , namely (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), and (3, 2, 1). These are all the possible orderings of this three-element set. Anagrams of words whose letters are different are also permutations: the letters are already ordered in the original word, and the anagram is a reordering of the letters. The study of permutations of finite sets is an important topic in the fields of combinatorics and group theory. Permutations are used in almost every branch of mathematics, and in many other fields of scie ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Joel Spencer
Joel Spencer (born April 20, 1946) is an American mathematician. He is a combinatorialist who has worked on probabilistic methods in combinatorics and on Ramsey theory. He received his doctorate from Harvard University in 1970, under the supervision of Andrew Gleason. He is currently () a professor at the Courant Institute of Mathematical Sciences of New York University. Spencer's work was heavily influenced by Paul Erdős, with whom he coauthored many papers (giving him an Erdős number of 1). In 1963, while studying at the Massachusetts Institute of Technology, Spencer became a Putnam Fellow. In 1984 Spencer received a Lester R. Ford Award. He was an Erdős Lecturer at Hebrew University of Jerusalem in 2001. In 2012 he became a fellow of the American Mathematical Society. He was elected as a fellow of the Society for Industrial and Applied Mathematics in 2017, "for contributions to discrete mathematics and theory of computing, particularly random graphs and networks, Ramsey ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Bin Packing Problem
The bin packing problem is an optimization problem, in which items of different sizes must be packed into a finite number of bins or containers, each of a fixed given capacity, in a way that minimizes the number of bins used. The problem has many applications, such as filling up containers, loading trucks with weight capacity constraints, creating file backups in media and technology mapping in FPGA semiconductor chip design. Computationally, the problem is NP-hard, and the corresponding decision problem - deciding if items can fit into a specified number of bins - is NP-complete. Despite its worst-case hardness, optimal solutions to very large instances of the problem can be produced with sophisticated algorithms. In addition, many approximation algorithms exist. For example, the first fit algorithm provides a fast but often non-optimal solution, involving placing each item into the first bin in which it will fit. It requires '' Θ''(''n'' log ''n'') time, where ''n' ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
With High Probability
In mathematics, an event that occurs with high probability (often shortened to w.h.p. or WHP) is one whose probability depends on a certain number ''n'' and goes to 1 as ''n'' goes to infinity, i.e. the probability of the event occurring can be made as close to 1 as desired by making ''n'' big enough. Applications The term WHP is especially used in computer science, in the analysis of probabilistic algorithms. For example, consider a certain probabilistic algorithm on a graph with ''n'' nodes. If the probability that the algorithm returns the correct answer is 1-1/n, then when the number of nodes is very large, the algorithm is correct with a probability that is very near 1. This fact is expressed shortly by saying that the algorithm is correct WHP. Some examples where this term is used are: * Miller–Rabin primality test: a probabilistic algorithm for testing whether a given number ''n'' is prime or composite. If ''n'' is composite, the test will detect ''n'' as composite WHP. Th ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Online Fair Division
Online fair division is a class of fair division problems in which the resources, or the people to whom they should be allocated, or both, are not all available when the allocation decision is made. Some situations in which not all resources are available include: * Allocating food donations to charities (the "food bank" problem). Each donation must be allocated immediately when it arrives, before future donations arrive. * Allocating donated blood or organs to patients. Again, each donation must be allocated immediately, and it is not known when and what future donations will be. Some situations in which not all participants are available include: * Dividing a cake among people in a party. Some people come early and want to get a cake when they arrive, but other people may come later. * Dividing the rent and rooms among tenants in a rented apartment, when one or more of them are not available during the allocation. The online nature of the problem requires different techniques ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Agreeable Subset
An agreeable subset is a subset of items that is considered, by all people in a certain group, to be at least as good as its complement. Finding a small agreeable subset is a problem in computational social choice. An example situation in which this problem arises is when a family goes on a trip and has to decide which items to take. Since their car is limited in size, they cannot pick all items, so they have to agree on a subset of items which are most important. If they manage to find a subset of items such that all family members agree that it is at least as good as the subset of items remaining at home, then this subset is called ''agreeable''. Another use case is when the citizens in some city want to elect a committee from a given pool of candidates, such that all citizens agree that the subset of elected candidates is at least as good as the subset of non-elected ones. Subject to that, the committee size should be as small as possible. Definitions Agreeable subset The ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Online Fair Division
Online fair division is a class of fair division problems in which the resources, or the people to whom they should be allocated, or both, are not all available when the allocation decision is made. Some situations in which not all resources are available include: * Allocating food donations to charities (the "food bank" problem). Each donation must be allocated immediately when it arrives, before future donations arrive. * Allocating donated blood or organs to patients. Again, each donation must be allocated immediately, and it is not known when and what future donations will be. Some situations in which not all participants are available include: * Dividing a cake among people in a party. Some people come early and want to get a cake when they arrive, but other people may come later. * Dividing the rent and rooms among tenants in a rented apartment, when one or more of them are not available during the allocation. The online nature of the problem requires different techniques ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Discrepancy Theory
In mathematics, discrepancy theory describes the deviation of a situation from the state one would like it to be in. It is also called the theory of irregularities of distribution. This refers to the theme of ''classical'' discrepancy theory, namely distributing points in some space such that they are evenly distributed with respect to some (mostly geometrically defined) subsets. The discrepancy (irregularity) measures how far a given distribution deviates from an ideal one. Discrepancy theory can be described as the study of inevitable irregularities of distributions, in measure-theoretic and combinatorial settings. Just as Ramsey theory elucidates the impossibility of total disorder, discrepancy theory studies the deviations from total uniformity. A significant event in the history of discrepancy theory was the 1916 paper of Weyl on the uniform distribution of sequences in the unit interval. __NOTOC__ Theorems Discrepancy theory is based on the following classic theorems: * T ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
