0
$\begingroup$

We are given a n-vertex DAG $G=(V,E)$ and also given a cost function $c: V \rightarrow \Bbb N$.

Given a topological sort $S = v_1,v_2,...,v_n$, it has associated a sorting cost $S_c = \sum_{i=1}^{n} C(v_i)$ where $C(v_i)$ is the cost of choosing $v_i$ at that point: i.e. the sum of the cost functions of all vertices that were candidates at the point of choosing $v_i$, but they weren't chosen. Obviously, precedent vertices to $v_i$ in $S$ (already chosen vertices) are not included in this sum.

The idea is to find a topological sort $S$ that minimizes $S_c$. I think its a NP-hard problem, but would there be any approximation algorithm, or at least some smart heuristic? I tried to find this exact same problem but I couldn't find it... just similar ones.

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ What makes a given vertex $v$ a "candidate" at a given location $i$? Any vertex that is not yet chosen? Or maybe any vertex such that there is a topological order with the preceding $i-1$ vertices where they are, and that vertex $v$ in position $i$? (These are not the same.) $\endgroup$
    – Neal Young
    Nov 5 '21 at 13:23
  • 1
    $\begingroup$ Scheduling/ordering a DAG (representing unit time jobs) on a single machine to minimize weighted completion time is NP-Hard. Here each vertex has a weight $w(v)$ and $C(v_i) = w(v_i) \cdot i$ since $i$ is the completion time of job at position $i$. $\endgroup$
    – Chandra Chekuri
    Nov 5 '21 at 13:52
  • 1
    $\begingroup$ I see. (Equivalently $C(v_i)$ is the sum over the vertices $v$ not yet chosen of $c(v_i)$.) Is this single machine scheduling with precedence constraints? That problem seems to be NP hard but 2-approximable in polytime.. $\endgroup$
    – Neal Young
    Nov 5 '21 at 14:45
  • 1
    $\begingroup$ A "candidate" is a vertex not yet chosen that has all its incoming vertices already in the sort at that point. So, it would be your second option. Other not-yet chosen vertex may not be a candidate because there are still other vertices that need to go first (dependency constraint) $\endgroup$
    – msalichs
    Nov 5 '21 at 17:34
  • 2
    $\begingroup$ Your objective is not very "natural" if the cost itself depends on the evolving schedule. What is the motivation? $\endgroup$
    – Chandra Chekuri
    Nov 5 '21 at 20:38

Your Answer

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

Browse other questions tagged or ask your own question.