### Better Know a Theorem: Parametric Search

01Jul11

Last week I was at an excellent summer school organized by TU Berlin and held at a nearby cottage/hotel. One topic that came up in a couple of talks was new to me: parametric search. First I’ll describe the setting and the basic result, due to Megiddo from 1979.

In an optimization problem, we are given some discrete structure (e.g. a graph) and some numerical data attached to the structure  (e.g., lengths in shortest path problems, capacities in max flow problems, costs in min spanning tree problems). Normally we assume that these data are just rationals expressed in binary. But the parametric version of the problem is more general: we introduce a parameter λ and each numerical data value is a linear function of λ, such as 5λ or (7 – 11λ). Observe that substituting any particular value of λ gives an instance of the original version of the problem; let the optimal value of this problem as a function of λ be OPT(λ). But, can we efficiently solve the problem for all real values of λ at once, which amounts to being able to draw the graph of the function OPT(λ) in terms of λ? Or can we answer other questions about this function?

We’ll assume that our optimization problems minimize sums of costs subject to feasibility constraints, which implies OPT(λ) is continuous, piecewise linear, and concave. Maximization is similar.

The min-ratio version of the problem gives one practical motivation to care about the parametric version. Consider the shortest st path problem in a graph. In the typical “shortest path problem,” each edge e would only have a single datum, its length l(e), and we would seek a path from s to t with minimum length (sum of lengths of the edges it contains). But now, suppose each edge also has a profit p(e) and that we seek a path such that the ratio of its total length to its total profit is minimized. This type of problem is easy to motivate as seeking the best benefit-to-cost ratio. And, if we have enough information about the parametric version, we could easily solve the min-ratio version: give edge e parametric length p(e)-λl(e), let OPT(λ) be the shortest path for these lengths as a function of λ,  then it is not hard to see that the minimum l-to-p ratio equals min {λ OPT(λ)≤0}.

So, how can we deal with parametric versions of flow, path, and tree problems? One observation is that many items of interest like min {λ OPT(λ)≤0}, or maxλ OPT(λ) can be expressed as the optima of linear programs. This gives a high-degree polynomial-time solution method to compute these items, which is unfortunately too slow to be practical in real-world instances. Also, it is worth keeping in mind that when Megiddo wrote his paper, poly-time LP algorithms were not known.

To explain Megiddo’s basic theorem, more definitions. An algorithm is combinatorial if it only applies the mathematical operations +, -, *, /, >, = to the data (and subsequent intermediate results relying on the data), but it does not rely on their bit-representation, and the running time does not depend on the length of the bit-representation1. It is strongly combinatorial if moreover * and / are not used, except to multiply data by constants. For example, the simplest and most well-known flow/path/tree algorithms are strongly combinatorial. Then Megiddo’s first theorem says:

Theorem (Megiddo 1979). Suppose there is a strongly combinatorial algorithm A with time complexity T for solving some minimization problem. Then its min-ratio version can be solved in time O(T2) by a combinatorial algorithm.

The idea is as follows. For ease of exposition assume p and l are nonnegative, so OPT(λ) is nonincreasing in λ, and assume the nontrivial case where OPT(0)>0. One crux is that under the operations {+, -, multiplication by constants}, linear functions in λ again yield linear functions in λ. So we could imagine running algorithm A where in place of constant data, we put linear functions of λ; any new intermediate results would again be linear functions of λ. This “almost” gives a parametric algorithm which runs symbolically for all values of λ at once. The problem is that when we compare two parametric values (e.g., compare 4+λ > 12-2λ) we actually need to know what is the value of λ. Megiddo’s solution is, at each such event, let λ* be the critical value determining the comparison (e.g., λ*=8/3 here); determine OPT(λ*) by running algorithm A on the rational data obtained at λ=λ*; if OPT(λ*)>0 then from now on assume λ>λ*, otherwise from now on assume λ≤λ*. In the future, comparisons either will be forced by these assumptions, else we again run algorithm A on a specific rational value. With a little work we prove that when the outer algorithm terminates, its optimal value is linear within the interval of assumptions, and includes the smallest λ with OPT(λ)=0.

For the running time, we are running an outer algorithm A symbolically on λ, and at each comparison of this algorithm, we run the inner algorithm A numerically on a specific value of λ. So the running time is at most the number of comparisons of A, times the running time of A, giving the theorem. ■

Megiddo goes on to show that in some situations, the running time can be improved further. One example is finding a min-ratio cycle: it can be obtained in time O(n6) (with n the number of vertices) by applying Megiddo’s theorem to Floyd’s algorithm; but Floyd’s algorithm has the structure that in each of n phases, we only need the n2 values computed in the last phase, so by working more carefully and by using  the inner A and binary search on n2 potential critical values in each phase, we get an overall runtime of O(n(n2log(n2) + log(n2)n3)) = O(n4log n).

### Parametric Flows

My interest in these parametric problems arises from the lectures that Tom McCormick gave at the aforementioned summer school. He talked about the parametric max-flow problem2. For parametric flow, a result of Carstensen (1983) shows that the graph of OPT(λ) can have exponentially many breakpoints (as a piecewise linear function). Thus the following result of Gallo-Grigoriadis-Tarjan, which Tom showed, is interesting:

Theorem (G-G-T 1989). For a special case of parametric max-flow, where the dependence on λ is positive in δout(s), negative in δin(t), and zero elsewhere, then

1. the graph of OPT(λ) consists of at most n linear segments;
2. and, we can adapt several known max-flow algorithms (let their time complexity be T) to compute the entire graph of OPT(λ) in time O(T).

This is much better than the generic O(T2) bound from Megiddo’s approach: going from the original problem to the parametric one only cost a constant factor of time! This G-G-T result is fairly complex and combines several interesting algorithmic ideas. Valid choices of algorithm include those of Karzanov, Goldberg-Tarjan, or Hochbaum with respective time complexities T=O(n3), O(nm log (n2/m)), O(nm log n), where m=|E|.

I asked a question at the course: what if we don’t have the special G-G-T structure, but we want to compute maxλ OPT(λ)? (This is natural: it’s the maximum flow value if we can both pick our choice of λ and our choice of flow.) It follows from a very general method of Tardos (1986) for linear programming that there is a high-degree polynomial-time combinatorial algorithm for this problem. But it turns out (as profs at the summer school suggested) that we get something more reasonable by using a variant of Megiddo’s method. Instead of searching for the λ with OPT(λ)=0, we (roughly speaking) search for the λ where the derivative of OPT(λ) is zero. (Recall OPT(λ) is concave and piecewise linear.) That is to say, when a comparison has λ* as its critical value, run an inner max-flow algorithm on the values λ=λ*, λ*+ε, λ*-ε to find out the slope of OPT(λ) to the left and right of λ*, e.g. if these slopes are both positive we should thereafter assume λ>λ*. So in O(T2) time, for any combinatorial max-flow algorithm, we get the desired maxλ OPT(λ).

As in Megiddo’s paper, the next natural question is whether this generic approach can be accelerated: for example, can we get a time complexity more like O(n5) instead of O(n6)?

Update: Indeed! I started reading Megiddo’s follow-up paper (1983) and it gives an idea to accomplish this and several other ideas. The key insight is the same as for the algorithm I sketched above for accelerating “parametric Floyd’s algorithm.” Remarkably, this approach (of reducing the number of calls to the inner algorithm) works whenever we have a good parallel (PRAM) algorithm for the problem. Specifically, we simulate a PRAM algorithm on a serial machine; but if C comparisons are done in parallel on a single time step, binary search allows us to reduce the number of calls to the inner algorithm to log C. So, we have:

Theorem (Megiddo 1983). Suppose there is a strongly combinatorial parallel algorithm for solving some minimization problem, which runs in T time steps on P processors, and a serial (i.e., non-parallel) algorithm running in time S. Then its min-ratio version can be solved in time O(T*log P*S) by a combinatorial algorithm.

Megiddo shows, for example, in parametric flow we can find λ such that OPT(λ)=x in Õ(min{n5,mn3}) time, using parallel max-flow algorithms with T = Õ(n2) and P = O(n). The same approach works for my question too. With one more idea, this approach also accelerates the parametric Floyd’s algorithm (min-ratio cycle) to Õ(n3) time.

Future reading: Fleischer and Iwata’s submodular function minimization algorithm (2003) is said to use many techniques related to parametric max-flow, in a more general setting.

1: Actually, in the definition of combinatorial we also require that the algorithm does not blow up the length of intermediate computations by more than a polynomial factor in bit-length. And, instead of “combinatorial with polynomial run-time” we usually say “strongly polynomial run-time.” See Schrijver’s 3-book set (2003) as a reference.

2: A nice exercise is to show that, given two cost-functions, find a flow F maximizing c1(F)/c2(F) always has an optimum which is a cycle or a path. But surprisingly, given two capacity-functions, finding a cut C minimizing c1(C)/c2(C) is not as simple. The latter is an example of a parametric flow problem that is actually useful in practice.