Student Center | Instructor's Center | Introduction to Algorithms | Home

Introduction to Algorithms, 2/e

Thomas H. Cormen, Dartmouth College
Charles E. Leiserson, Massachusetts Institute of Technology
Ronald L. Rivest, Massachusetts Institute of Technology
Clifford Stein, Columbia University

Approximation Algorithms

Glossary

approximation algorithm	an algorithm that returns near-optimal solutions (See page 1022)



ρ(n)-approximation algorithm	an algorithm that achieves an approximation ratio of ρ(n). (See page 1022)



approximation scheme	for an optimization problem is an approximation algorithm that takes as input not only an instance of the problem, but also a value ε > 0 such that for any fixed ε, the scheme is a (1 + ε)-approximation algorithm. (See page 1023)



polynomial-time approximation scheme	property of an approximation scheme if for any fixed ε > 0, the scheme runs in time polynomial in the size n of its input instance. (See page 1023)



fully polynomial-time approximation scheme	property of an approximation scheme if its running time is polynomial both in 1/ε and in the size of the input instance. (See page 1023)



vertex cover	of an undirected graph G = (V, E) is a subset V′ ⊆ V such that if (u, v) is an edge of G, then either u ∈ V′ or v ∈ V′ (or both). The size of a vertex cover is the number of vertices in it. (See page 1024)



vertex cover problem	to find a vertex cover of minimum size in a given undirected graph. We call such a vertex cover an optimal vertex cover. this problem is the optimization version of an NP-complete decision problem. (See page 1024)



maximal matching	a matching that is not a proper subset of any other matching. (See page 1026)



triangle inequality	The cost function c satisfies the triangle inequality if for all vertices u, v, w ∈ V, c(u, w) ≤ c(u, v) + c(v, w). The triangle inequality is a natural one, and in many applications it is automatically satisfied. (See page 1028)



closest-point heuristic	for building an approximate traveling-salesman tour. Begin with a trivial cycle consisting of a single arbitrarily chosen vertex. At each step, identify the vertex u that is not on the cycle but whose distance to any vertex on the cycle is minimum. Suppose that the vertex on the cycle that is nearest u is vertex v. Extend the cycle to include u by inserting u just after v. Repeat until all vertices are on the cycle. (See page 1033)



bottleneck traveling-salesman problem	finding the hamiltonian cycle such that the cost of the most costly edge in the cycle is minimized. (See page 1033)



approximation ratio	a randomized algorithm for a problem has an approximation ratio of ρ(n) if, for any input of size n, the exptected cost C of the solution produced by the randomized algorithm is within a factor of ρ(n) of the cost C* of an optimal solution: (See page 1039)



randomized ρ(n)-approximation algorithm	a randomized algorithm that achieves an approximation ratio of ρ(n). In other words, a randomized approximation algorithm is like a deterministic approximation algorithm, except that the approximation ratio is for an expected value. (See page 1039)



MAX-3-CNF satisfiability	In order to be satisfiable, there must be an assignment of the variables so that every clause evaluates to 1. If an instance is not satisfiable, we may want to compute how "close" to satisfiable it is, that is, we may wish to find an assignment of the variables that satisfies as many clauses as possible. We call the resulting maximization problem MAX-3-CNF satisfiability. The input to MAX-3-CNF satisfiability is the same as for 3-CNF satisfiability, and the goal is to return an assignment of the variables that maximizes the number of clauses evaluating to 1. (See page 1039)



minimum-weight vertex-cover problem	given an undirected graph G = (V, E) in which each vertex v ∈ V has an associated positive weight w(v). For any vertex cover V′ ⊆ V, we define the weight of the vertex cover w(V′) = Ε_{v ∈ V′}w(v). The goal is to find a vertex cover of minimum weight. (See page 1040)



MAX-CNF satisfiability problem	is like the MAX-3-CNF satisfiability problem, except that it does not restrict each clause to have exactly 3 literals. (See page 1043)



weight	of a cut is the number of edges crossing the cut. (See page 1043)



trim	To trim a list L by δ means to remove as many elements from L as possible, in such a way that if L′ is the resulting of trimming L, then for every element y that was removed from L, there is an element z still in L′ that approximates y. (See page 1045)



first-fit	The first-fit heuristic takes each object in turn and places it into the first bin that can accommodate it. (See page 1050)



maximal matching	a matching that is not a proper subset of any other matching. (See page 1051)



parallel-machine-scheduling problem	Given n jobs, J₁, J₂, . . . , J_n, where each job J_k has an associated nonnegative processing time of p_k. Also, given m identical machines, M₁, M₂, . . . , M_m. A schedule specifies, for each job J_k, the machine on which it runs and the time period during which it runs. Each job J_k must run on some machine M_i for p_k consecutive time units, and during that time period no other job may run on M_i. Let C_k denote the completion time of job J_k, that is, the time at which job J_k completes processing. Given a schedule we define C_max = max_1≤j≤nC_k to be the makespan of the schedule. The goal is to find a schedule whose makespan is minimum. (See page 1051)

2002 McGraw-Hill Higher Education
Any use is subject to the Terms of Use and Privacy Policy.
McGraw-Hill Higher Education is one of the many fine businesses of The McGraw-Hill Companies.