0
$\begingroup$

I am having a hard time wrapping my head around the time-varying edge cost of this question :

Suppose we have a connected graph $G = (V, E)$. Each edge e now has a time-varying edge cost given by a function $f_e$. Thus, at time t, it has cost $f_e(t)$. We’ll assume that all these functions are positive over their entire range. Observe that the set of edges constituting the minimum spanning tree of $G$ may change over time. Also, of course, the cost of the minimum spanning tree of $G$ becomes a function of the time $t$; we’ll denote this function $c_G(t)$. A natural problem then becomes: find a value of $t$ at which $c_G(t)$ is minimized. Suppose each function $f_e$ is a polynomial of degree 2: $f_e(t) = a_et^2 + b_et + c_e$ , where $a_e$ is positive for each edge $e$. Give an algorithm that takes the graph $G$ and the values $\{(a_e , b_e , c_e) : e ∈ E\}$ and returns a value of the time $t$ at which the minimum spanning tree has minimum cost. Your algorithm should run in time polynomial in the number of nodes and edges of the graph $G$. You may assume that arithmetic operations on the numbers $\{(a_e , b_e , c_e)\}$ can be done in constant time per operation.

My first idea was, because $a_e$ is positive, to find out the maximum value of $t$ that minimizes the cost of an edge $e$ (in other words looping through every edge once and find their minima). Intuitively, the maximum of these minima could be an upper-bound for the value that minimizes $c_G(t)$. Then I could run a MST algorithm for every time step from 0 to t and return the t that answers the question. However, this looks like a very brute-forcey method and thus not time-efficient at all.

Any help would be greatly appreciated!

Note that this question was part of the Greedy Algorithm chapter.

$\endgroup$
1
  • $\begingroup$ We require you to attribute the original source of all copied material: cs.stackexchange.com/help/referencing. Saying it came from "the Greedy Algorithm chapter" is not adequate. Please see the link for our expectations about providing a proper reference: e.g., we'd expect you to provide a full reference, including the textbook name and authors. $\endgroup$
    – D.W.
    Sep 27 at 4:11
1
$\begingroup$

Consider the edges sorted by $f_e(t)$ for some $t$.

Two quadratic polynomials can intersect at most two times. When the cost function of two edges $e_1$ and $e_2$ cross at time $t$, it means that

  • $f_{e_1}(t-\epsilon) < f_{e_2}(t-\epsilon)$ and
  • $f_{e_1}(t+\epsilon) > f_{e_2}(t+\epsilon)$.

Since there are $m$ edges and each pair of edges crosses at most twice, we have at most $2 \cdot {m \choose 2} \leq m^2$ many crossings, and therefore at most $m^2$ many times two edges can swap order in the sorted list.

Now you try all possible time intervals that don't contain crossings, $(t_a, t_b)$ and pick the $n-1$ cheapest edges. What remains is to minimize a sum over $n-1$ quadratic functions which is indeed a quadratic function.

$\endgroup$
0

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.