LP-type problem


In the study of algorithms, an LP-type problem 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:
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 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 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 to be the minimum objective function value of the smaller linear program defined by. With suitable general position assumptions, 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 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:
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 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 is
R := empty set
B := X
for x in a random permutation of S:
if ff:
B := seidel
R := R
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 is
X := empty set
repeat
R := a random subset of S with size d√n
B := basis for RX, computed recursively
V :=
X := XV
until V is empty
return B
In each iteration, the expected size of is, 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 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 is
if S = C then
return C
choose a random element x of S \ C
B = msw
if f ≠ f then
B := basis
B := msw
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 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.

Variations

Optimization with outliers

considers a variation of LP-type optimization problems in which one is given, together with the set and the objective function, a number ; the task is to remove elements from in order to make the objective function on the remaining set as small as possible. For instance, when applied to the smallest circle problem, this would give the smallest circle that contains all but of a given set of planar points. He shows that, for all non-degenerate LP-type problems this problem may be solved in time, by solving a set of LP-type problems defined by subsets of.

Implicit problems

Some geometric optimization problems may be expressed as LP-type problems in which the number of elements in the LP-type formulation is significantly greater than the number of input data values for the optimization problem. As an example, consider a collection of points in the plane, each moving with constant velocity. At any point in time, the diameter of this system is the maximum distance between two of its points. The problem of finding a time at which the diameter is minimized can be formulated as minimizing the pointwise maximum of quasiconvex functions, one for each pair of points, measuring the Euclidean distance between the pair as a function of time. Thus, it can be solved as an LP-type problem of combinatorial dimension two on a set of elements, but this set is significantly larger than the number of input points.
describes an algorithm for solving implicitly defined LP-type problems such as this one in which each LP-type element is determined by a -tuple of input values, for some constant. In order to apply his approach, there must exist a decision algorithm that can determine, for a given LP-type basis and set of input values, whether is a basis for the LP-type problem determined by.
Chan's algorithm performs the following steps:
With the assumption that the decision algorithm takes an amount of time that grows at least polynomially as a function of the input size, Chan shows that the threshold for switching to an explicit LP formulation and the number of subsets in the partition can be chosen in such a way that the implicit LP-type optimization algorithm also runs in time.
For instance, for the minimum diameter of moving points, the decision algorithm needs only to calculate the diameter of a set of points at a fixed time, a problem that can be solved in time using the rotating calipers technique. Therefore, Chan's algorithm for finding the time at which the diameter is minimized also takes time.
Chan uses this method to find a point of maximal Tukey depth among a given collection of points in -dimensional Euclidean space, in time. A similar technique was used by to find a point of maximal Tukey depth for the uniform distribution on a convex polygon.

History and related problems

The discovery of linear time algorithms for linear programming and the observation that the same algorithms could in many cases be used to solve geometric optimization problems that were not linear programs goes back at least to, who gave a linear expected time algorithm for both three-variable linear programs and the smallest circle problem. However, Megiddo formulated the generalization of linear programming geometrically rather than combinatorially, as a convex optimization problem rather than as an abstract problem on systems of sets. Similarly, and Clarkson observed that their methods could be applied to convex programs as well as linear programs. showed that the minimum enclosing ellipsoid problem could also be formulated as a convex optimization problem by adding a small number of non-linear constraints. The use of randomization to improve the time bounds for low dimensional linear programming and related problems was pioneered by Clarkson and by.
The definition of LP-type problems in terms of functions satisfying the axioms of locality and monotonicity is from, but other authors in the same timeframe formulated alternative combinatorial generalizations of linear programs. For instance, in a framework developed by, the function is replaced by a total ordering on the subsets of. It is possible to break the ties in an LP-type problem to create a total order, but only at the expense of an increase in the combinatorial dimension.
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.
Another abstract generalization of both linear programs and linear complementarity problems, formulated by and later studied by several other authors, concerns orientations of the edges of a hypercube with the property that every face of the hypercube has a unique sink, a vertex with no outgoing edges. An orientation of this type may be formed from an LP-type problem by corresponding the subsets of S with the vertices of a hypercube in such a way that two subsets differ by a single element if and only if the corresponding vertices are adjacent, and by orienting the edge between neighboring sets towards if and towards otherwise. 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 in a number of steps exponential in the square root of .
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. Violator spaces are defined similarly to LP-type problems, by a function that maps sets to objective function values, but the values of are not ordered. Despite the lack of ordering, every set has a well-defined set of bases that can be found by variations of Clarkson's algorithms for LP-type problems. Indeed, violator spaces have been shown to exactly characterize the systems that can be solved by Clarkson's algorithms.