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 as problems in which one is given as input a finite set of elements, and a function that maps subsets of to values from a totally ordered set. The function is required to satisfy two key properties: Monotonicity: for every two sets , f(A) ≤ f(B) ≤ f(S). Locality: for every two sets and every element in , if , then .
A basis of an LP-type problem is a set with the property that every proper subset of has a smaller value of than 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 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 and an element whether , and a basis computation that (with the same inputs) finds a basis of }. The task for the algorithm to perform is to evaluate by only using these restricted evaluations or primitives.
Examples and applications
A linear program may be defined by a system of non-negative real variables, subject to 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 be the set of constraints, and defining (for a subset of the constraints) to be the minimum objective function value of the smaller linear program defined by . 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 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 and show that, for an integer program with variables, the combinatorial dimension is at most .
Many natural optimization problems in computational geometry are LP-type:
The smallest circle problem is the problem of finding the minimum radius of a circle containing a given set of points in the plane. It satisfies monotonicity (adding more points can only make the circle larger) and locality (if the smallest circle for set contains and , then the same circle also contains }). Because the smallest circle is always determined by some three points, the smallest circle problem has combinatorial dimension three, even though it is defined using two-dimensional Euclidean geometry.Although the smallest circle problem was first stated to be an LP-type problem by , several earlier papers described algorithms for this problem based on ideas from low-dimensional linear programming, including and . More generally, the smallest enclosing ball of points in dimensions forms an LP-type problem of combinatorial dimension . The smallest circle problem can be generalized to the smallest ball enclosing a set of balls,. to the smallest ball that touches or surrounds each of a set of balls,. to the weighted 1-center problem,. or to similar smaller enclosing ball problems in non-Euclidean spaces such as the space with distances defined by Bregman divergence.. The related problem of finding the smallest enclosing ellipsoid is also an LP-type problem, but with a larger combinatorial dimension, .; . Let be a sequence of convex sets in -dimensional Euclidean space, and suppose that we wish to find the longest prefix of this sequence that has a common intersection point. This may be expressed as an LP-type problem in which where Ki is the first member of A that does not belong to an intersecting prefix of A, and where if there is no such member. The combinatorial dimension of this system is .. Suppose we are given a collection of axis-aligned rectangular boxes in three-dimensional space, and wish to find a line directed into the positive octant of space that cuts through all the boxes. This may be expressed as an LP-type problem with combinatorial dimension 4.. The problem of finding the closest distance between two convex polytopes, specified by their sets of vertices, may be represented as an LP-type problem. In this formulation, the set is the set of all vertices in both polytopes, and the function value is the negation of the smallest distance between the convex hulls of the two subsets of vertices in the two polytopes. The combinatorial dimension of the problem is if the two polytopes are disjoint, or if they have a nonempty intersection. Let } be a set of quasiconvex functions. Then the pointwise maximum is itself quasiconvex, and the problem of finding the minimum value of is an LP-type problem. It has combinatorial dimension at most , where is the dimension of the domain of the functions, but for sufficiently smooth functions the combinatorial dimension is smaller, at most . Many other LP-type problems can also be expressed using quasiconvex functions in this way; for instance, the smallest enclosing circle problem is the problem of minimizing where each of the functions measures the Euclidean distance from one of the given points.; .
LP-type problems have also been used to determine the optimal outcomes of certain games in algorithmic game theory,. improve vertex placement in finite element method meshes,. solve facility location problems,. analyze the time complexity of certain exponential-time search algorithms,. and reconstruct the three-dimensional positions of objects from their two-dimensional images..
Algorithms
Seidel gave an algorithm for low-dimensional linear programming that may be adapted to the LP-type problem framework. Seidel's algorithm takes as input the set and a separate set (initially empty) of elements known to belong to the optimal basis. It then considers the remaining elements one-by-one in a random order, performing violation tests for each one and, depending on the result, performing a recursive call to the same algorithm with a larger set of known basis elements. It may be expressed with the following pseudocode:
function seidel(S, f, X) is R := empty set B := X for x in a random permutation of S: if f(B) ≠ f(B ∪ {x}): B := seidel(R, f, X ∪ {x}) R := R ∪ {x} return B
In a problem with combinatorial dimension , the violation test in the th iteration of the algorithm fails only when is one of the remaining basis elements, which happens with probability at most . Based on this calculation, it can be shown that overall the expected number of violation tests performed by the algorithm is , linear in but worse than exponential in .
Clarkson defines two algorithms, a recursive algorithm and an iterative algorithm, for linear programming based on random sampling techniques, and suggests a combination of the two that calls the iterative algorithm from the recursive algorithm. The recursive algorithm repeatedly chooses random samples whose size is approximately the square root of the input size, solves the sampled problem recursively, and then uses violation tests to find a subset of the remaining elements that must include at least one basis element:
function recursive(S, f) is X := empty set repeat R := a random subset of S with size d√n B := basis for R ∪ X, computed recursively V := {x | f(B) ≠ f(B ∪ {x})} X := X ∪ V until V is empty return B
In each iteration, the expected size of is ,Tail bounds on the size of are also known: see . and whenever is nonempty it includes at least one new element of the eventual basis of . Therefore, the algorithm performs at most iterations, each of which performs violation tests and makes a single recursive call to a subproblem of size .
Clarkson's iterative algorithm assigns weights to each element of , initially all of them equal. It then chooses a set of elements from at random, and computes the sets and as in the previous algorithm. If the total weight of is at most times the total weight of (as happens with constant probability) then the algorithm doubles the weights of every element of , and as before it repeats this process until becomes empty. In each iteration, the weight of the optimal basis can be shown to increase at a greater rate than the total weight of , from which it follows that the algorithm must terminate within iterations.
By using the recursive algorithm to solve a given problem, switching to the iterative algorithm for its recursive calls, and then switching again to Seidel's algorithm for the calls made by the iterative algorithm, it is possible solve a given LP-type problem using violation tests.
When applied to a linear program, this algorithm can be interpreted as being a dual simplex method.. With certain additional computational primitives beyond the violation test and basis computation primitives, this method can be made deterministic..
Matoušek, Sharir, and Welzl 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. If an LP-type problem does not have this property, it can be made to have it by adding new dummy elements and by modifying the function to return the ordered pair of its old value and of the number , ordered lexicographically.
Rather than adding elements of S one at a time, or finding samples of the elements, describe an algorithm that removes elements one at a time. At each step it maintains a basis that may initially be the set of dummy elements. It may be described with the following pseudocode:
function msw(S, f, C) is if S = C then return C choose a random element x of S \ C B = msw(S \ x, f, C) if f(B) ≠ f(B ∪ {x}) then B := basis(B ∪ {x}) B := msw(S, f, B) return B
In most of the recursive calls of the algorithm, the violation test succeeds and the if statement is skipped. However, with a small probability the violation test fails and the algorithm makes an additional basis computation and then an additional recursive call. As the authors show, the expected time for the algorithm is linear in n and exponential in the square root of . By combining this method with Clarkson's recursive and iterative procedures, these two forms of time dependence can be separated out from each other, resulting in an algorithm that performs O(dn) violation tests in the outer recursive algorithm and a number that is exponential in the square root of in the lower levels of the algorithm.. A very similar time bound for linear programming was also given by .
Variations
Optimization with outliers