Titlebook: Complexity and Approximation; Combinatorial Optimi Giorgio Ausiello,Alberto Marchetti-Spaccamela,Vigg Textbook 1999 Springer-Verlag Berlin

bronchiole

The Complexity of Optimization Problems,set of . and . is the set of .. As an alternative view, we can also consider a predicate .(x,y) which is true if and only if (x,y) ∈ .. If we want to analyze the properties of the computations to be performed, it is necessary to consider the characteristics of the sets ., . and of the relation . (or of the predicate .) more closely.

隐士

Input-Dependent and Asymptotic Approximation,proximation algorithm but no approxima­tion scheme exists (unless P=N.). To deal with these two latter kinds of problem, in this chapter we will relax the constraint on the performance ratio in two ways.

profligate

Approximation Preserving Reductions,eductions not always preserve the measure function and, even if this happens, they rarely preserve the quality of the solutions. It is then clear that a stronger kind of reducibility has to be used that not only maps instances of a problem .. to instances of a problem .., but it also maps back good solutions for .. to good solutions for ...

斜