### Better Know a Theorem: Parametric Search

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 *s*–*t* 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-representation^{1}. 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(T^{2}) 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(*n*^{6}) (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 * n^{2}* values computed in the last phase, so by working more carefully and by using the inner A and binary search on

*n*

^{2}potential critical values in each phase, we get an overall runtime of O(

*n*(

*n*

^{2}log(

*n*

^{2}) + log(

*n*

^{2})

*n*

^{3})) = O(

*n*

^{4}log

*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 problem^{2}. 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

- the graph of OPT(λ) consists of at most
nlinear segments;- 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(T^{2}) 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(*n*^{3}), O(*nm *log (*n*^{2}/*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(T^{2}) 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(n^{5}) instead of O(n^{6})?

*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{n^{5},mn^{3}}) time, using parallel max-flow algorithms with T = Õ(n^{2}) 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 Õ(n^{3}) 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.

Filed under: algorithms, b.k.a.t., combinatorial optimization | 1 Comment

I guess it should be l(e)- \lambda p(e) instead of p(e) – \lambda l(e)