Faster access than browser!
57 relations: Algorithm, Approximation-preserving reduction, APX, Éva Tardos, Cambridge University Press, Charles E. Leiserson, Christofides algorithm, Clifford Stein, Clique problem, Computer science, Convex optimization, David S. Johnson, David Shmoys, Domination analysis, Dorit S. Hochbaum, Dynamic programming, Ellipsoid method, Exact algorithm, Genetic algorithm, Gerhard J. Woeginger, Graph coloring, Greedy algorithm, Hardness of approximation, Heuristic (computer science), Independent set (graph theory), Introduction to Algorithms, Jan Karel Lenstra, Johan Håstad, Joseph S. B. Mitchell, Knapsack problem, Linear programming, Linear programming relaxation, Local search (optimization), Marek Karpinski, Matching (graph theory), MAX-3SAT, Maximum cut, Maximum satisfiability problem, NP-completeness, NP-hardness, Operations research, Optimization problem, P versus NP problem, PCP theorem, Polynomial-time approximation scheme, Reduction (complexity), Ron Rivest, Sanjeev Arora, Semidefinite programming, Set cover problem, ..., Simulated annealing, Theoretical computer science, Thomas H. Cormen, Time complexity, Travelling salesman problem, Unique games conjecture, Vertex cover. Expand index (7 more) »
Algorithm
In mathematics and computer science, an algorithm is an unambiguous specification of how to solve a class of problems.
New!!: Approximation algorithm and Algorithm · See more »
Approximation-preserving reduction
In computability theory and computational complexity theory, especially the study of approximation algorithms, an approximation-preserving reduction is an algorithm for transforming one optimization problem into another problem, such that the distance of solutions from optimal is preserved to some degree.
New!!: Approximation algorithm and Approximation-preserving reduction · See more »
APX
In complexity theory the class APX (an abbreviation of "approximable") is the set of NP optimization problems that allow polynomial-time approximation algorithms with approximation ratio bounded by a constant (or constant-factor approximation algorithms for short).
New!!: Approximation algorithm and APX · See more »
Éva Tardos
Éva Tardos (born 1 October 1957) is a Hungarian mathematician and the Jacob Gould Schurman Professor of Computer Science at Cornell University.
New!!: Approximation algorithm and Éva Tardos · See more »
Cambridge University Press
Cambridge University Press (CUP) is the publishing business of the University of Cambridge.
New!!: Approximation algorithm and Cambridge University Press · See more »
Charles E. Leiserson
Charles Eric Leiserson is a computer scientist, specializing in the theory of parallel computing and distributed computing, and particularly practical applications thereof.
New!!: Approximation algorithm and Charles E. Leiserson · See more »
Christofides algorithm
The Christofides algorithm is an algorithm for finding approximate solutions to the travelling salesman problem, on instances where the distances form a metric space (they are symmetric and obey the triangle inequality).
New!!: Approximation algorithm and Christofides algorithm · See more »
Clifford Stein
Clifford Seth Stein (born December 14, 1965), a computer scientist, is a professor of industrial engineering and operations research at Columbia University in New York, NY, where he also holds an appointment in the Department of Computer Science.
New!!: Approximation algorithm and Clifford Stein · See more »
Clique problem
In computer science, the clique problem is the computational problem of finding cliques (subsets of vertices, all adjacent to each other, also called complete subgraphs) in a graph.
New!!: Approximation algorithm and Clique problem · See more »
Computer science
Computer science deals with the theoretical foundations of information and computation, together with practical techniques for the implementation and application of these foundations.
New!!: Approximation algorithm and Computer science · See more »
Convex optimization
Convex optimization is a subfield of optimization that studies the problem of minimizing convex functions over convex sets.
New!!: Approximation algorithm and Convex optimization · See more »
David S. Johnson
David Stifler Johnson (December 9, 1945 – March 8, 2016) was an American computer scientist specializing in algorithms and optimization.
New!!: Approximation algorithm and David S. Johnson · See more »
David Shmoys
David Bernard Shmoys (born 1959) is a Professor in the School of Operations Research and Information Engineering and the Department of Computer Science at Cornell University.
New!!: Approximation algorithm and David Shmoys · See more »
Domination analysis
Domination analysis of an approximation algorithm is a way to estimate its performance, introduced by Glover and Punnen in 1997.
New!!: Approximation algorithm and Domination analysis · See more »
Dorit S. Hochbaum
Dorit S. Hochbaum (born 1949) is a professor of industrial engineering and operations research at the University of California, Berkeley.
New!!: Approximation algorithm and Dorit S. Hochbaum · See more »
Dynamic programming
Dynamic programming is both a mathematical optimization method and a computer programming method.
New!!: Approximation algorithm and Dynamic programming · See more »
Ellipsoid method
In mathematical optimization, the ellipsoid method is an iterative method for minimizing convex functions.
New!!: Approximation algorithm and Ellipsoid method · See more »
Exact algorithm
In computer science and operations research, exact algorithms are algorithms that always solve an optimization problem to optimality.
New!!: Approximation algorithm and Exact algorithm · See more »
Genetic algorithm
In computer science and operations research, a genetic algorithm (GA) is a metaheuristic inspired by the process of natural selection that belongs to the larger class of evolutionary algorithms (EA).
New!!: Approximation algorithm and Genetic algorithm · See more »
Gerhard J. Woeginger
Gerhard J. Woeginger is an Austrian mathematician and computer scientist who works in Germany as a professor at RWTH Aachen University, where he chairs the algorithms and complexity group in the department of computer science.
New!!: Approximation algorithm and Gerhard J. Woeginger · See more »
Graph coloring
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints.
New!!: Approximation algorithm and Graph coloring · See more »
Greedy algorithm
A greedy algorithm is an algorithmic paradigm that follows the problem solving heuristic of making the locally optimal choice at each stage with the intent of finding a global optimum.
New!!: Approximation algorithm and Greedy algorithm · See more »
Hardness of approximation
In computer science, hardness of approximation is a field that studies the algorithmic complexity of finding near-optimal solutions to optimization problems.
New!!: Approximation algorithm and Hardness of approximation · See more »
Heuristic (computer science)
In computer science, artificial intelligence, and mathematical optimization, a heuristic (from Greek εὑρίσκω "I find, discover") is a technique designed for solving a problem more quickly when classic methods are too slow, or for finding an approximate solution when classic methods fail to find any exact solution.
New!!: Approximation algorithm and Heuristic (computer science) · See more »
Independent set (graph theory)
In graph theory, an independent set or stable set is a set of vertices in a graph, no two of which are adjacent.
New!!: Approximation algorithm and Independent set (graph theory) · See more »
Introduction to Algorithms
Introduction to Algorithms is a book by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.
New!!: Approximation algorithm and Introduction to Algorithms · See more »
Jan Karel Lenstra
Jan Karel Lenstra (born 19 December 1947, in Zaandam) is a Dutch mathematician and operations researcher, known for his work on scheduling algorithms, local search, and the travelling salesman problem.
New!!: Approximation algorithm and Jan Karel Lenstra · See more »
Johan Håstad
Johan Torkel Håstad (born 19 November 1960) is a Swedish theoretical computer scientist most known for his work on computational complexity theory.
New!!: Approximation algorithm and Johan Håstad · See more »
Joseph S. B. Mitchell
Joseph S. B. Mitchell is an American computer scientist and mathematician.
New!!: Approximation algorithm and Joseph S. B. Mitchell · See more »
Knapsack problem
The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.
New!!: Approximation algorithm and Knapsack problem · See more »
Linear programming
Linear programming (LP, also called linear optimization) is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships.
New!!: Approximation algorithm and Linear programming · See more »
Linear programming relaxation
In mathematics, the relaxation of a (mixed) integer linear program is the problem that arises by removing the integrality constraint of each variable.
New!!: Approximation algorithm and Linear programming relaxation · See more »
Local search (optimization)
In computer science, local search is a heuristic method for solving computationally hard optimization problems.
New!!: Approximation algorithm and Local search (optimization) · See more »
Marek Karpinski
Marek Karpinski is a computer scientist and mathematician known for his research in the theory of algorithms and their applications, combinatorial optimization, computational complexity, and mathematical foundations.
New!!: Approximation algorithm and Marek Karpinski · See more »
Matching (graph theory)
In the mathematical discipline of graph theory, a matching or independent edge set in a graph is a set of edges without common vertices.
New!!: Approximation algorithm and Matching (graph theory) · See more »
MAX-3SAT
MAX-3SAT is a problem in the computational complexity subfield of computer science.
New!!: Approximation algorithm and MAX-3SAT · See more »
Maximum cut
For a graph, a maximum cut is a cut whose size is at least the size of any other cut.
New!!: Approximation algorithm and Maximum cut · See more »
Maximum satisfiability problem
In computational complexity theory, the maximum satisfiability problem (MAX-SAT) is the problem of determining the maximum number of clauses, of a given Boolean formula in conjunctive normal form, that can be made true by an assignment of truth values to the variables of the formula.
New!!: Approximation algorithm and Maximum satisfiability problem · See more »
NP-completeness
In computational complexity theory, an NP-complete decision problem is one belonging to both the NP and the NP-hard complexity classes.
New!!: Approximation algorithm and NP-completeness · See more »
NP-hardness
NP-hardness (''n''on-deterministic ''p''olynomial-time hardness), in computational complexity theory, is the defining property of a class of problems that are, informally, "at least as hard as the hardest problems in NP".
New!!: Approximation algorithm and NP-hardness · See more »
Operations research
Operations research, or operational research in British usage, is a discipline that deals with the application of advanced analytical methods to help make better decisions.
New!!: Approximation algorithm and Operations research · See more »
Optimization problem
In mathematics and computer science, an optimization problem is the problem of finding the best solution from all feasible solutions.
New!!: Approximation algorithm and Optimization problem · See more »
P versus NP problem
The P versus NP problem is a major unsolved problem in computer science.
New!!: Approximation algorithm and P versus NP problem · See more »
PCP theorem
In computational complexity theory, the PCP theorem (also known as the PCP characterization theorem) states that every decision problem in the NP complexity class has probabilistically checkable proofs (proofs that can be checked by a randomized algorithm) of constant query complexity and logarithmic randomness complexity (uses a logarithmic number of random bits).
New!!: Approximation algorithm and PCP theorem · See more »
Polynomial-time approximation scheme
In computer science, a polynomial-time approximation scheme (PTAS) is a type of approximation algorithm for optimization problems (most often, NP-hard optimization problems).
New!!: Approximation algorithm and Polynomial-time approximation scheme · See more »
Reduction (complexity)
In computability theory and computational complexity theory, a reduction is an algorithm for transforming one problem into another problem.
New!!: Approximation algorithm and Reduction (complexity) · See more »
Ron Rivest
Ronald Linn Rivest (born May 6, 1947) is a cryptographer and an Institute Professor at MIT.
New!!: Approximation algorithm and Ron Rivest · See more »
Sanjeev Arora
Sanjeev Arora (born January 1968) is an Indian American theoretical computer scientist who is best known for his work on probabilistically checkable proofs and, in particular, the PCP theorem.
New!!: Approximation algorithm and Sanjeev Arora · See more »
Semidefinite programming
Semidefinite programming (SDP) is a subfield of convex optimization concerned with the optimization of a linear objective function (a user-specified function that the user wants to minimize or maximize) over the intersection of the cone of positive semidefinite matrices with an affine space, i.e., a spectrahedron.
New!!: Approximation algorithm and Semidefinite programming · See more »
Set cover problem
The set cover problem is a classical question in combinatorics, computer science and complexity theory.
New!!: Approximation algorithm and Set cover problem · See more »
Simulated annealing
Simulated annealing (SA) is a probabilistic technique for approximating the global optimum of a given function.
New!!: Approximation algorithm and Simulated annealing · See more »
Theoretical computer science
Theoretical computer science, or TCS, is a subset of general computer science and mathematics that focuses on more mathematical topics of computing and includes the theory of computation.
New!!: Approximation algorithm and Theoretical computer science · See more »
Thomas H. Cormen
Thomas H. Cormen is the co-author of Introduction to Algorithms, along with Charles Leiserson, Ron Rivest, and Cliff Stein.
New!!: Approximation algorithm and Thomas H. Cormen · See more »
Time complexity
In computer science, the time complexity is the computational complexity that describes the amount of time it takes to run an algorithm.
New!!: Approximation algorithm and Time complexity · See more »
Travelling salesman problem
The 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 and returns to the origin city?" It is an NP-hard problem in combinatorial optimization, important in operations research and theoretical computer science.
New!!: Approximation algorithm and Travelling salesman problem · See more »
Unique games conjecture
In computational complexity theory, the unique games conjecture is a conjecture made by Subhash Khot in 2002.
New!!: Approximation algorithm and Unique games conjecture · See more »
Vertex cover
In the mathematical discipline of graph theory, a vertex cover (sometimes node cover) of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set.
New!!: Approximation algorithm and Vertex cover · See more »
Redirects here:
Absolute performance guarantee, Approximability, Approximation algorithms, Approximation ratio, R-approximation algorithm, Relative performance guarantee, Rho-approximation algorithm, Ρ-approximation algorithm.
References
[1] https://en.wikipedia.org/wiki/Approximation_algorithm
