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, 2021 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, 2021 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, 2021 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, 2021 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, 2021 at 20:38

0

Reset to default

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.