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.
Definition 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:
Monotonicity: for every two sets A ⊆ B ⊆ S, f(A) ≤ f(B) ≤ f(S). Locality: for every two sets A ⊆ B ⊆ S and every element x in S, if f(A) = f(B) = f(A ∪ {x}), then f(A) = f(B ∪ {x}). 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.
Examples and applications
A linear program may be defined by a system of d non-negative real variables, subject to n linear inequality constraints, together with a non-negative linear objective function to be minimized. This may be placed into the framework of LP-type problems by letting S be the set of constraints, and defining f(A) (for a subset A of the constraints) to be the minimum objective function value of the smaller linear program defined by A. 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. Similarly, an integer program (consisting of a collection of linear constraints and a linear objective function, as in a linear program, but with the additional restriction that the variables must take on only integer values) satisfies both the monotonicity and locality properties of an LP-type problem, with the same general position assumptions as for linear programs. Theorems of Bell (1977) and Scarf (1977) show that, for an integer program with d variables, the combinatorial dimension is at most 2d. Many natural optimization problems in computational geometry are LP-type:
… excerpt ends here. Continue reading the full article.
