Suppose there is a path (linear) graph $G = (V, E)$ where $V = \{0, \ldots, n - 1\}$ and $E=\{(0, 1), (1, 2), \ldots, (n - 2, n - 1)\}$, with edge weights $w_e : E \to \mathbb{N}$ and vertex weights $w_v : V \to \mathbb{N}$. Let $\lambda$ be a known constant.

We need to find an exact cover $C \subseteq \mathbb{P}(V)$ of $V$ (with $\iota : V \to C$ being the associated injection) such that each $p \in C$ is a contiguous subset (interval) in $\mathbb{N}$ and

$$\lambda \left( \sum_{\iota(i) \neq \iota(j)} w_e(i, j) \right) + (1 - \lambda) \left( \max_{p \in C} \sum_{v \in p} w_v(v) \right)$$

is minimized.

In other words, we are trying to minimize a convex combination of the sum of the edge weights of the cut edges and the maximum total node weight for each part.

Is there an efficient algorithm for this problem? An approximation algorithm?

  • 1
    $\begingroup$ Have you tried dynamic programming? Have you tried binary search on the value of the max total node weight? Can you tell us anything about the context where you encountered this task? $\endgroup$
    – D.W.
    Apr 1 at 6:14
  • $\begingroup$ This is a subproblem for a new scheduler design for an open source high-level hardware synthesis program I work on (github.com/google/xls). The vertex weights can be thought of as "number of picoseconds some operation takes", while the edge weights are "how much data passes from one operation to the next". Maybe there's a way to couch this as a dynamic programming recurrence, but I haven't come up with it. I also didn't think of doing binary search; can you elaborate on that? I imagine it works because the Pareto frontier between cut weight and node weight is monotone? $\endgroup$
    – taktoa
    Apr 1 at 14:48
  • $\begingroup$ @D.W., I don't think binary search is going to work - the function doesn't depend monotonically on the second term. $\endgroup$
    – user114966
    Apr 1 at 21:04
  • $\begingroup$ Are the vertex/edge weights large or small? To put it another way: Are you OK with a pseudopolynomial algorithm (one whose running time is polynomial in the weights of the vertices and edges), or do you need a polynomial time algorithm (one whose running time is polynomial in their length, i.e., the log of the weights)? $\endgroup$
    – D.W.
    Apr 1 at 22:14
  • $\begingroup$ Pseudopolynomial time is fine. $\endgroup$
    – taktoa
    Apr 1 at 23:14

I suggest using dynamic programming. Because your graph forms a path, we can use dynamic programming (considering all prefixes of the path), solving once for each candidate for the maximum total weight of the parts. Details below.

Let $S$ denote the sum of the weights of the cut edges (i.e., the first part of your objective function) and $M$ the maximum total weight of the parts (i.e., the second part of your objective function), so that your goal is to minimize $\lambda S + (1-\lambda) M$. Define $f(m)$ to be the minimum possible value of $S$, for all covers with $M \le m$. I'll show below how to calculate $f(m)$ for any desired $m$. This then is sufficient to compute the minimum possible value of $\lambda S + (1-\lambda) M$, by enumerating all $m$ and checking which gives the lowest value of $\lambda f(m) + (1-\lambda) m$.

So, let's fix $m$ from here on. For any $k$ that ends a consecutive interval in $C$, i.e., where $\iota(k) \ne \iota(k+1)$, define $S_*$ by $$S_* = \sum_{i\le k, \iota(i)\ne \iota(i+1)} w_e(i,i+1).$$ We will let $A[k]$ denote the minimum possible value of $S_*$, taken over all exact covers that contain an interval that ends at $k$ (i.e., where $\iota(k)\ne \iota(k+1)$) and such that $M\le m$ for this cover. Note that this depends on only how vertices $0,1,2,\dots,k$ are partitioned by $C$, and doesn't depend on what is done with vertices $k+1,\dots,n-1$.

Now we can write a recurrence relation for $A[k]$:

$$A[k] = \min_t A[t] + w_e(k,k+1),$$

where $t$ ranges over $0 \le t < k$ such that $\sum_{i=t+1}^k w_v(i) \le m$. Thus, for each $m$, you can fill in the array $A[\cdot]$ in $O(n^2)$ time using dynamic programming. It's possible to get this down to $O(n \log n)$ time by pre-computing prefix sums for $w_v(\cdot)$ and binary search to find the range of allowable $t$'s, and storing $A[\cdot]$ in a balanced binary tree augmented with minimums stored in each tree node to quickly find the minimum of $A[\cdot]$ over a range of indices. To get the total running time, we must multiply this by the number of values of $m$ we iterate through. A trivial upper bound on $M$ is the sum of all vertex weights.

In this way, we obtain an algorithm whose running time is $O(Tn \log n)$ where $T=\sum_v w_v(v)$ is the total of all vertex weights. In practice, often the running time will be less, as we can iterate through $m$ in increasing order, and once we find a solution whose objective function has value $v$, then there is no need to consider values of $m$ larger than $v/(1-\lambda)$. As @j_random_hacker points out, we can replace $T$ with $O(n^2)$, if that helps: we only need to consider values of $m$ that are equal to the sum of vertex weights along some interval, and there are only $O(n^2)$ such intervals.

If you want an approximation algorithm, scale all of the vertex weights down by a factor of $c$, and then round to the nearest integer. This will speed up the algorithm by a factor of $c$, and should approximate the optimal solution to within $\pm (1-\lambda)cn$ (probably better than that in practice).

  • $\begingroup$ Better than mine in several ways: (1) You don't explicitly enumerate heaviest paths (there's no need, although this does enable you to replace $T$ with $n^2$, which is polynomial in the problem size); (2) Forcing a path break at the end of each subproblem means you can minimise over a simpler expression, improving by a $n/\log n$ factor. $\endgroup$ Apr 2 at 5:48
  • $\begingroup$ Since $f(m)$ is nonincreasing in $m$, computing $f(m)$ tells us that $f(m-i) \ge f(m)-i$ for all $i \le m$. IOW, the max slope of the graph of $m$ vs. $f(m)$ is 1. This can be exploited to bound out ranges of $m$ values. E.g., suppose we calculate $f(100)=500$ and later $f(150)=470$: We no longer need to test $m$ in the range $70\dots 99$ since these values must all be $\ge$ 470. $\endgroup$ Apr 2 at 6:20
  • $\begingroup$ @j_random_hacker, I like your idea that we don't need to enumerate all possible values of $m$, only those that can occur as the sum of vertex weights of some interval. And nice optimization to avoid some $m$ values. Cool stuff! $\endgroup$
    – D.W.
    Apr 2 at 6:26
  • $\begingroup$ @taktoa, yup, good point. $\endgroup$
    – D.W.
    Apr 7 at 18:25

Here's an implementation of D.W.'s algorithm (the $O(n^2)$ version) in C++. There was some subtlety around the base case of the recurrence; A needs to be indexed on std::optional<NodeId>, where A[std::nullopt] = 0 is the base case.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.