Class Description

GLO: Guaranteed Local Optima

The class of NPO problems which have the property that for all locally optimal solutions, the ratio between the values of the local and global optima is upper-bounded by a constant.

Defined in [AP95], where it was also shown that GLO is strictly contained in APX.

[KMS+99] showed that MaxSNP is not contained in GLO.

Linked From

No class.