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.

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.^[1] 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 2^d.^[1]

Many natural optimization problems in computational geometry are LP-type:

Smallest circle problem

• The smallest circle problem is the problem of finding the minimum radius of a circle containing a given set of n points in the plane. It satisfies monotonicity (adding more points can only make the circle larger) and locality (if the smallest circle for set A contains B and x, then the same circle also contains B ∪ {x}). 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.^[2] More generally, the smallest enclosing ball of points in d dimensions forms an LP-type problem of combinatorial dimension d + 1. The smallest circle problem can be generalized to the smallest ball enclosing a set of balls,^[3] to the smallest ball that touches or surrounds each of a set of balls,^[4] to the weighted 1-center problem,^[5] or to similar smaller enclosing ball problems in non-Euclidean spaces such as the space with distances defined by Bregman divergence.^[6] The related problem of finding the smallest enclosing ellipsoid is also an LP-type problem, but with a larger combinatorial dimension, d(d + 3)/2.^[7]
• Let K₀, K₁, ... be a sequence of n convex sets in d-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 f(A) = −i where K_i is the first member of A that does not belong to an intersecting prefix of A, and where f(A) = −n if there is no such member. The combinatorial dimension of this system is d + 1.^[8]
• 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.^[9]
• 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 S is the set of all vertices in both polytopes, and the function value f(A) is the negation of the smallest distance between the convex hulls of the two subsets A of vertices in the two polytopes. The combinatorial dimension of the problem is d + 1 if the two polytopes are disjoint, or d + 2 if they have a nonempty intersection.^[1]
• Let S = {f₀, f₁, ...} be a set of quasiconvex functions. Then the pointwise maximum max_i f_i is itself quasiconvex, and the problem of finding the minimum value of max_i f_i is an LP-type problem. It has combinatorial dimension at most 2d + 1, where d is the dimension of the domain of the functions, but for sufficiently smooth functions the combinatorial dimension is smaller, at most d + 1. 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 max_i f_i where each of the functions f_i measures the Euclidean distance from one of the given points.^[10]

LP-type problems have also been used to determine the optimal outcomes of certain games in algorithmic game theory,^[11] improve vertex placement in finite element method meshes,^[12] solve facility location problems,^[13] analyze the time complexity of certain exponential-time search algorithms,^[14] and reconstruct the three-dimensional positions of objects from their two-dimensional images.^[15]

Algorithms

Seidel

Seidel (1991) 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 S and a separate set X (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:

def seidel(S,f,X):
    R = empty set
    B = X
    for x in a random permutation of S:
        if f(B) ≠ f(B ∪ {x}):
            B = seidel(R,f, basis(X ∪ {x}))
        R = R ∪ {x}
    return B

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. Based on this calculation, it can be shown that overall the expected number of violation tests performed by the algorithm is O(d! n), linear in n but worse than exponential in d.

Clarkson

Clarkson (1995) 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:

def recursive(S,f):
    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 V is O(√n),^[16] and whenever V is nonempty it includes at least one new element of the eventual basis of S. Therefore, the algorithm performs at most d iterations, each of which performs n violation tests and makes a single recursive call to a subproblem of size O(d√n).

Clarkson's iterative algorithm assigns weights to each element of S, initially all of them equal. It then chooses a set R of 9d² elements from S at random, and computes the sets B and V as in the previous algorithm. If the total weight of V is at most 2/(9d − 1) times the total weight of S (as happens with constant probability) then the algorithm doubles the weights of every element of V, and as before it repeats this process until V 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 S, from which it follows that the algorithm must terminate within O(log n) 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 O(dn + d! d^O(1) log n) violation tests.

When applied to a linear program, this algorithm can be interpreted as being a dual simplex method.^[17] With certain additional computational primitives beyond the violation test and basis computation primitives, this method can be made deterministic.^[18]

Matoušek, Sharir, and Welzl

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. If an LP-type problem does not have this property, it can be made to have it by adding d new dummy elements and by modifying the function f to return the ordered pair of its old value f(A) and of the number min(d,, ordered lexicographically.

Rather than adding elements of S one at a time, or finding samples of the elements, Matoušek, Sharir & Welzl (1996) describe an algorithm that removes elements one at a time. At each step it maintains a basis C that may initially be the set of dummy elements. It may be described with the following pseudocode:

def msw(S,f,C):
    if S = C:
        return C
    choose a random element x of S \ C
    B = msw(S \ x, f, C)
    if f(B) ≠ f(B ∪ {x}):
        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 d log n. 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 d log d in the lower levels of the algorithm.^[19]

Variations

Optimization with outliers

Matoušek (1995) considers a variation of LP-type optimization problems in which one is given, together with the set S and the objective function f, a number k; the task is to remove k elements from S 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 k of a given set of planar points. He shows that, for all non-degenerate LP-type problems (that is, problems in which all bases have distinct values) this problem may be solved in time O(nk^d), by solving a set of O(k^d) LP-type problems defined by subsets of S.

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 n 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 O(n²) 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 O(n²) elements, but this set is significantly larger than the number of input points.^[20]

Chan (2004) describes an algorithm for solving implicitly defined LP-type problems such as this one in which each LP-type element is determined by a k-tuple of input values, for some constant k. In order to apply his approach, there must exist a decision algorithm that can determine, for a given LP-type basis B and set S of n input values, whether B is a basis for the LP-type problem determined by S.

Chan's algorithm performs the following steps:

• If the number of input values is below some threshold value, find the set of LP-type elements that it determines and solve the resulting explicit LP-type problem.
• Otherwise, partition the input values into a suitable number greater than k of equal-sized subsets S_i.
• If f is the objective function for the implicitly defined LP-type problem to be solved, then define a function g that maps collections of subsets S_i to the value of f on the union of the collection. Then the collection of subsets S_i and the objective function g itself defines an LP-type problem, of the same dimension as the implicit problem to be solved.
• Solve the (explicit) LP-type problem defined by g using Clarkson's algorithm, which performs a linear number of violation tests and a polylogarithmic number of basis evaluations. The basis evaluations for g may be performed by recursive calls to Chan's algorithm, and the violation tests may be performed by calls to the decision algorithm.

With the assumption that the decision algorithm takes an amount of time O(T(n)) that grows at least polynomially as a function of the input size n, 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 O(T(n)).

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 O(n log n) time using the rotating calipers technique. Therefore, Chan's algorithm for finding the time at which the diameter is minimized also takes time O(n log n). Chan uses this method to find a point of maximal Tukey depth among a given collection of n points in d-dimensional Euclidean space, in time O(n^{d − 1} + n log n). 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.

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 Megiddo (1983, 1984), 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, Dyer (1986) and Clarkson (in the 1988 conference version of Clarkson 1995) observed that their methods could be applied to convex programs as well as linear programs. Dyer (1992) 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 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. For instance, in a framework developed by Gärtner (1995), the function f is replaced by a total ordering on the subsets of S. 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.^[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.

Another abstract generalization of both linear programs and linear complementarity problems, formulated by Stickney & Watson (1978) and later studied by several other authors, concerns orientations of the edges of a hypercube with the property that every face of the hypercube (including the whole hypercube as a face) 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 A ⊆ B towards B if f(A) ≠ f(B) and towards A 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 (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. Violator spaces are defined similarly to LP-type problems, by a function f that maps sets to objective function values, but the values of f are not ordered. Despite the lack of ordering, every set S has a well-defined set of bases (the minimal sets with the same value as the whole set) 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.^[23]

Notes

References