LP-type problem

In the study of algorithms, an LP-type problem (also called a generalized linear program) is an optimization problem that shares certain properties with low-dimensional linear programs and that may be solved by similar algorithms. LP-type problems include many important optimization problems that are not themselves linear programs, such as the problem of finding the smallest circle containing a given set of planar points. They may be solved by a combination of randomized algorithms in an amount of time that is linear in the number of elements defining the problem, and subexponential in the dimension of the problem.

LP-type problems were defined by Sharir & Welzl (1992) as problems in which one is given as input a finite set S of elements, and a function f that maps subsets of S to values from a totally ordered set. The function is required to satisfy two key properties:

A basis of an LP-type problem is a set B ⊆ S with the property that every proper subset of B has a smaller value of f than B itself, and the dimension (or combinatorial dimension) of an LP-type problem is defined to be the maximum cardinality of a basis.

It is assumed that an optimization algorithm may evaluate the function f only on sets that are themselves bases or that are formed by adding a single element to a basis. Alternatively, the algorithm may be restricted to two primitive operations: a violation test that determines, for a basis B and an element x whether f(B) = f(B ∪ {x}), and a basis computation that (with the same inputs) finds a basis of B ∪ {x}. The task for the algorithm to perform is to evaluate f(S) by only using these restricted evaluations or primitives.

...
Wikipedia