LP-type problem
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.
With suitable general position assumptions (in order to prevent multiple solution points having the same optimal objective function value), this satisfies the monotonicity and locality requirements of an LP-type problem, and has combinatorial dimension equal to the number d of variables.
[15] Seidel (1991) gave an algorithm for low-dimensional linear programming that may be adapted to the LP-type problem framework.
It may be expressed with the following pseudocode: In a problem with combinatorial dimension d, the violation test in the ith iteration of the algorithm fails only when x is one of the d − |X| remaining basis elements, which happens with probability at most (d − |X|)/i.
[18] Matoušek, Sharir & Welzl (1996) describe an algorithm that uses an additional property of linear programs that is not always held by other LP-type problems, that all bases have the same cardinality of each other.
It may be described with the following pseudocode: In most of the recursive calls of the algorithm, the violation test succeeds and the if statement is skipped.
A similar technique was used by Braß, Heinrich-Litan & Morin (2003) to find a point of maximal Tukey depth for the uniform distribution on a convex polygon.
The use of randomization to improve the time bounds for low dimensional linear programming and related problems was pioneered by Clarkson and by Dyer & Frieze (1989).
The definition of LP-type problems in terms of functions satisfying the axioms of locality and monotonicity is from Sharir & Welzl (1992), but other authors in the same timeframe formulated alternative combinatorial generalizations of linear programs.
[21] Additionally, as in LP-type problems, Gärtner defines certain primitives for performing computations on subsets of elements; however, his formalization does not have an analogue of the combinatorial dimension.
The resulting orientation has the additional property that it forms a directed acyclic graph, from which it can be shown that a randomized algorithm can find the unique sink of the whole hypercube (the optimal basis of the LP-type problem) in a number of steps exponential in the square root of n.[22] The more recently developed framework of violator spaces generalizes LP-type problems, in the sense that every LP-type problem can be modeled by a violator space but not necessarily vice versa.
