Travelling salesman problemThe travelling salesman problem (TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?" It is an NP-hard problem in combinatorial optimization, important in theoretical computer science and operations research. The travelling purchaser problem and the vehicle routing problem are both generalizations of TSP.
Beal conjectureThe Beal conjecture is the following conjecture in number theory: If where A, B, C, x, y, and z are positive integers with x, y, z ≥ 3, then A, B, and C have a common prime factor. Equivalently, The equation has no solutions in positive integers and pairwise coprime integers A, B, C if x, y, z ≥ 3. The conjecture was formulated in 1993 by Andrew Beal, a banker and amateur mathematician, while investigating generalizations of Fermat's Last Theorem. Since 1997, Beal has offered a monetary prize for a peer-reviewed proof of this conjecture or a counterexample.
Knapsack problemThe knapsack problem is the following problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine which items to include in the collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items.
Online algorithmIn 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.
Constraint satisfactionIn artificial intelligence and operations research, constraint satisfaction is the process of finding a solution through a set of constraints that impose conditions that the variables must satisfy. A solution is therefore a set of values for the variables that satisfies all constraints—that is, a point in the feasible region. The techniques used in constraint satisfaction depend on the kind of constraints being considered.
Convex geometryIn mathematics, convex geometry is the branch of geometry studying convex sets, mainly in Euclidean space. Convex sets occur naturally in many areas: computational geometry, convex analysis, discrete geometry, functional analysis, geometry of numbers, integral geometry, linear programming, probability theory, game theory, etc. According to the Mathematics Subject Classification MSC2010, the mathematical discipline Convex and Discrete Geometry includes three major branches: general convexity polytopes and polyhedra discrete geometry (though only portions of the latter two are included in convex geometry).
Decision problemIn computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm whether a given natural number is prime. Another is the problem "given two numbers x and y, does x evenly divide y?". The answer is either 'yes' or 'no' depending upon the values of x and y. A method for solving a decision problem, given in the form of an algorithm, is called a decision procedure for that problem.
Poincaré conjectureIn the mathematical field of geometric topology, the Poincaré conjecture (UKˈpwæ̃kæreɪ, USˌpwæ̃kɑːˈreɪ, pwɛ̃kaʁe) is a theorem about the characterization of the 3-sphere, which is the hypersphere that bounds the unit ball in four-dimensional space. Originally conjectured by Henri Poincaré in 1904, the theorem concerns spaces that locally look like ordinary three-dimensional space but which are finite in extent. Poincaré hypothesized that if such a space has the additional property that each loop in the space can be continuously tightened to a point, then it is necessarily a three-dimensional sphere.
Ellipsoid methodIn mathematical optimization, the ellipsoid method is an iterative method for minimizing convex functions. When specialized to solving feasible linear optimization problems with rational data, the ellipsoid method is an algorithm which finds an optimal solution in a number of steps that is polynomial in the input size. The ellipsoid method generates a sequence of ellipsoids whose volume uniformly decreases at every step, thus enclosing a minimizer of a convex function. The ellipsoid method has a long history.
Milton FriedmanMilton Friedman (ˈfriːdmən; July 31, 1912 – November 16, 2006) was an American economist and statistician who received the 1976 Nobel Memorial Prize in Economic Sciences for his research on consumption analysis, monetary history and theory and the complexity of stabilization policy. With George Stigler and others, Friedman was among the intellectual leaders of the Chicago school of economics, a neoclassical school of economic thought associated with the work of the faculty at the University of Chicago that rejected Keynesianism in favor of monetarism until the mid-1970s, when it turned to new classical macroeconomics heavily based on the concept of rational expectations.
