<p>We are given a n-vertex DAG <span class="math-container">$G=(V,E)$</span> and also given a cost function <span class="math-container">$c: V \rightarrow \Bbb N$</span>.</p>
<p>Given a topological sort <span class="math-container">$S = v_1,v_2,...,v_n$</span>, it has associated a sorting cost <span class="math-container">$S_c = \sum_{i=1}^{n} C(v_i)$</span>
where <span class="math-container">$C(v_i)$</span> is the cost of choosing <span class="math-container">$v_i$</span> at that point: i.e. the sum of the cost functions of all vertices that were candidates at the point of choosing <span class="math-container">$v_i$</span>, but they weren't chosen. Obviously, precedent vertices to <span class="math-container">$v_i$</span> in <span class="math-container">$S$</span> (already chosen vertices) are not included in this sum.</p>
<p>The idea is to find a topological sort <span class="math-container">$S$</span> that minimizes <span class="math-container">$S_c$</span>. 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.</p>

CC BY-SA 4.0
2021-11-05T13:23:35.590Z
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.)
Neal Young
CC BY-SA 4.0
2021-11-05T13:52:31.970Z
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$.
Chandra Chekuri
CC BY-SA 4.0
2021-11-05T14:45:11.790Z
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.](https://scholar.google.com/scholar?q=Single+Machine+Scheduling+with+Precedence+Constraints&hl=en&as_sdt=0&as_vis=1&oi=scholart).
Neal Young
CC BY-SA 4.0
2021-11-05T15:09:24.963Z
Yes, I forgot to mention the 2-approximation for the scheduling problem. I worked on it in grad school :). 2 is the best one can get under UGC like assumptions, and that is a nice result due to Bansal and Khot. https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=5438609
Chandra Chekuri
CC BY-SA 4.0
2021-11-05T17:34:44.813Z
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)
msalichs
CC BY-SA 4.0
2021-11-05T17:48:19.350Z
So its not exactly the same problem youre describing (which i think is easier to model) because here you dont start counting the cost of some vertices from the start, just when its feasible to chose them.
msalichs
CC BY-SA 4.0
2021-11-05T20:38:06.997Z
Your objective is not very "natural" if the cost itself depends on the evolving schedule. What is the motivation?
Chandra Chekuri
<ds.algorithms><approximation-algorithms><directed-acyclic-graph><topological-sorting>
Minimize Cumulative Cost on Topological Sort
msalichs
# Minimize Cumulative Cost on Topological Sort

(Asked by: username_0 on 2021-11-05)

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.

**Tags:** ds.algorithms, approximation-algorithms, directed-acyclic-graph, topological-sorting
> **Comments:**
> **username_1**: 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.)  
> **username_2**: 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$.  
> **username_1**: 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.](https://scholar.google.com/scholar?q=Single+Machine+Scheduling+with+Precedence+Constraints&hl=en&as_sdt=0&as_vis=1&oi=scholart).  
> **username_2**: Yes, I forgot to mention the 2-approximation for the scheduling problem. I worked on it in grad school :). 2 is the best one can get under UGC like assumptions, and that is a nice result due to Bansal and Khot. https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=5438609  
> **username_0**: 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)  
> **username_0**: So its not exactly the same problem youre describing (which i think is easier to model) because here you dont start counting the cost of some vertices from the start, just when its feasible to chose them.  
> **username_2**: Your objective is not very "natural" if the cost itself depends on the evolving schedule. What is the motivation?  

---

## 0 answers

