|
Birkhoff's Algorithm
Birkhoff's algorithm (also called Birkhoff-von-Neumann algorithm) is an algorithm for decomposing a bistochastic matrix into a convex combination of permutation matrices. It was published by Garrett Birkhoff in 1946. It has many applications. One such application is for the problem of fair random assignment: given a randomized allocation of items, Birkhoff's algorithm can decompose it into a lottery on deterministic allocations. Terminology A ''bistochastic matrix'' (also called: ''doubly-stochastic'') is a matrix in which all elements are greater than or equal to 0 and the sum of the elements in each row and column equals 1. An example is the following 3-by-3 matrix: \begin 0.2 & 0.3 & 0.5 \\ 0.6 & 0.2 & 0.2 \\ 0.2 & 0.5 & 0.3 \end A ''permutation matrix'' is a special case of a bistochastic matrix, in which each element is either 0 or 1 (so there is exactly one "1" in each row and each column). An example is the following 3-by-3 matrix: \begin 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Bistochastic Matrix
In mathematics, especially in probability and combinatorics, a doubly stochastic matrix (also called bistochastic matrix) is a square matrix X=(x_) of nonnegative real numbers, each of whose rows and columns sums to 1, i.e., :\sum_i x_=\sum_j x_=1, Thus, a doubly stochastic matrix is both left stochastic and right stochastic. Indeed, any matrix that is both left and right stochastic must be square: if every row sums to one then the sum of all entries in the matrix must be equal to the number of rows, and since the same holds for columns, the number of rows and columns must be equal. Birkhoff polytope The class of n\times n doubly stochastic matrices is a convex polytope known as the Birkhoff polytope B_n. Using the matrix entries as Cartesian coordinates, it lies in an (n-1)^2-dimensional affine subspace of n^2-dimensional Euclidean space defined by 2n-1 independent linear constraints specifying that the row and column sums all equal one. (There are 2n-1 constraints rather ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Canadian Mathematical Bulletin
The ''Canadian Mathematical Bulletin'' (french: Bulletin Canadien de Mathématiques) is a mathematics journal, established in 1958 and published quarterly by the Canadian Mathematical Society. The current editors-in-chief of the journal are Antonio Lei and Javad Mashreghi. The journal publishes short articles in all areas of mathematics that are of sufficient interest to the general mathematical public. Abstracting and indexing The journal is abstracted in: for the Canadian Mathematical Bulletin. * '''' * '' [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Gordan's Lemma
Gordan's lemma is a lemma in convex geometry and algebraic geometry. It can be stated in several ways. * Let A be a matrix of integers. Let M be the set of non-negative integer solutions of A \cdot x = 0. Then there exists a finite subset of vectors in M, such that every element of M is a linear combination of these vectors with non-negative integer coefficients. * The semigroup of integral points in a rational convex polyhedral cone is finitely generated. * An affine toric variety is an algebraic variety (this follows from the fact that the prime spectrum of the semigroup algebra of such a semigroup is, by definition, an affine toric variety). The lemma is named after the mathematician Paul Gordan (1837–1912). Some authors have misspelled it as "Gordon's lemma". Proofs There are topological and algebraic proofs. Topological proof Let \sigma be the dual cone of the given rational polyhedral cone. Let u_1, \dots, u_r be integral vectors so that \sigma = \. Then the u_i's g ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Birkhoff Decomposition (other) .
{{disambig ...
Birkhoff decomposition refers to two different mathematical concepts: * The Birkhoff factorization, introduced by George David Birkhoff at 1909, is the presentation of an invertible matrix with polynomial coefficients as a product of three matrices. * The Birkhoff - von Neumann decomposition, introduced by Garrett Birkhoff (George's son) at 1946, is the presentation of a bistochastic matrix as a convex sum of permutation matrices. It can be found by the Birkhoff algorithm Birkhoff's algorithm (also called Birkhoff-von-Neumann algorithm) is an algorithm for decomposing a bistochastic matrix into a convex combination of permutation matrices. It was published by Garrett Birkhoff in 1946. It has many applications. One su ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Birkhoff Polytope
The Birkhoff polytope ''B''''n'' (also called the assignment polytope, the polytope of doubly stochastic matrices, or the perfect matching polytope of the complete bipartite graph K_) is the convex polytope in R''N'' (where ''N'' = ''n''2) whose points are the doubly stochastic matrices, i.e., the matrices whose entries are non-negative real numbers and whose rows and columns each add up to 1. It is named after Garrett Birkhoff. Properties Vertices The Birkhoff polytope has ''n''! vertices, one for each permutation on ''n'' items. This follows from the Birkhoff–von Neumann theorem, which states that the extreme points of the Birkhoff polytope are the permutation matrices, and therefore that any doubly stochastic matrix may be represented as a convex combination of permutation matrices; this was stated in a 1946 paper by Garrett Birkhoff, but equivalent results in the languages of projective configurations and of regular bipartite graph matchings, respectively, were sho ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Vijay Vazirani
Vijay Virkumar Vazirani ( hi, विजय वीरकुमार वज़ीरानी; b. 1957) is an Indian American distinguished professor of computer science in the Donald Bren School of Information and Computer Sciences at the University of California, Irvine. Education and career Vazirani first majored in electrical engineering at Indian Institute of Technology, Delhi but in his second year he transferred to MIT and received his bachelor's degree in computer science from MIT in 1979 and his Ph.D. from the University of California, Berkeley in 1983. His dissertation, ''Maximum Matchings without Blossoms'', was supervised by Manuel Blum. After postdoctoral research with Michael O. Rabin and Leslie Valiant at Harvard University, he joined the faculty at Cornell University in 1984. He moved to the IIT Delhi as a full professor in 1990, and moved again to the Georgia Institute of Technology in 1995. He was also a McKay Visiting Professor at the University of California, Be ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
NP-hard
In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard problem is the subset sum problem. A more precise specification is: a problem ''H'' is NP-hard when every problem ''L'' in NP can be reduced in polynomial time to ''H''; that is, assuming a solution for ''H'' takes 1 unit time, ''H''s solution can be used to solve ''L'' in polynomial time. As a consequence, finding a polynomial time algorithm to solve any NP-hard problem would give polynomial time algorithms for all the problems in NP. As it is suspected that P≠NP, it is unlikely that such an algorithm exists. It is suspected that there are no polynomial-time algorithms for NP-hard problems, but that has not been proven. Moreover, the class P, in which all problems can be solved in polynomial time, is contained in the NP class. Defi ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Envy-freeness
Envy-freeness, also known as no-envy, is a criterion for fair division. It says that, when resources are allocated among people with equal rights, each person should receive a share that is, in their eyes, at least as good as the share received by any other agent. In other words, no person should feel envy. General definitions Suppose a certain resource is divided among several agents, such that every agent i receives a share X_i. Every agent i has a personal preference relation \succeq_i over different possible shares. The division is called envy-free (EF) if for all i and j: :::X_i \succeq_i X_j Another term for envy-freeness is no-envy (NE). If the preference of the agents are represented by a value functions V_i, then this definition is equivalent to: :::V_i(X_i) \geq V_i(X_j) Put another way: we say that agent i ''envies'' agent j if i prefers the piece of j over his own piece, i.e.: :::X_i \prec_i X_j :::V_i(X_i) 2 the problem is much harder. See envy-free cake-cutting. ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Probabilistic-serial Procedure
A simultaneous eating algorithm (SE) is an algorithm for allocating divisible objects among agents with ordinal preferences. "Ordinal preferences" means that each agent can rank the items from best to worst, but cannot (or does not want to) specify a numeric value for each item. The SE allocation satisfies SD-efficiency - a weak ordinal variant of Pareto-efficiency (it means that the allocation is Pareto-efficient for ''at least one'' vector of additive utility functions consistent with the agents' item rankings). SE is parametrized by the "eating speed" of each agent. If all agents are given the same eating speed, then the SE allocation satisfies SD-envy-freeness - a strong ordinal variant of envy-freeness (it means that the allocation is envy-free for ''all'' vectors of additive utility functions consistent with the agents' item rankings). This particular variant of SE is called the Probabilistic Serial rule (PS). SE was developed by Hervé Moulin and Anna Bogomolnaia as a so ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Greedy Algorithm
A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage. In many problems, a greedy strategy does not produce an optimal solution, but a greedy heuristic can yield locally optimal solutions that approximate a globally optimal solution in a reasonable amount of time. For example, a greedy strategy for the travelling salesman problem (which is of high computational complexity) is the following heuristic: "At each step of the journey, visit the nearest unvisited city." This heuristic does not intend to find the best solution, but it terminates in a reasonable number of steps; finding an optimal solution to such a complex problem typically requires unreasonably many steps. In mathematical optimization, greedy algorithms optimally solve combinatorial problems having the properties of matroids and give constant-factor approximations to optimization problems with the submodular structure. Specifics Greedy algorith ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Permutation Matrix
In mathematics, particularly in matrix theory, a permutation matrix is a square binary matrix that has exactly one entry of 1 in each row and each column and 0s elsewhere. Each such matrix, say , represents a permutation of elements and, when used to multiply another matrix, say , results in permuting the rows (when pre-multiplying, to form ) or columns (when post-multiplying, to form ) of the matrix . Definition Given a permutation of ''m'' elements, :\pi : \lbrace 1, \ldots, m \rbrace \to \lbrace 1, \ldots, m \rbrace represented in two-line form by :\begin 1 & 2 & \cdots & m \\ \pi(1) & \pi(2) & \cdots & \pi(m) \end, there are two natural ways to associate the permutation with a permutation matrix; namely, starting with the ''m'' × ''m'' identity matrix, , either permute the columns or permute the rows, according to . Both methods of defining permutation matrices appear in the literature and the properties expressed in one representation can be easily converted to th ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Maximum Cardinality Matching
Maximum cardinality matching is a fundamental problem in graph theory. We are given a graph , and the goal is to find a matching containing as many edges as possible; that is, a maximum cardinality subset of the edges such that each vertex is adjacent to at most one edge of the subset. As each edge will cover exactly two vertices, this problem is equivalent to the task of finding a matching that covers as many vertices as possible. An important special case of the maximum cardinality matching problem is when is a bipartite graph, whose vertices are partitioned between left vertices in and right vertices in , and edges in always connect a left vertex to a right vertex. In this case, the problem can be efficiently solved with simpler algorithms than in the general case. Algorithms for bipartite graphs Flow-based algorithm The simplest way to compute a maximum cardinality matching is to follow the Ford–Fulkerson algorithm. This algorithm solves the more general problem ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
