Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
Consider this problem: Given a list of finite sets, find an ordering $s_1, s_2, s_3, \ldots$ that minimizes $|s_1| + |s_1 \cup s_2| + |s_1 \cup s_2 \cup s_3| + \ldots$.
Are there known algorithms for this? What is its complexity? I haven't been able to think of an efficient optimal algorithm yet, but it's not obviously in NP-Hard either.
This problem is actually related to a scheduling problem knows as "Precedence constrained scheduling to minimize weighted completion time". The problem is as follows : Given a set of jobs, where each job has a processing time (p) and weight (w) and a precedence graph is defined on the jobs. Goal is to schedule the jobs in a single machine (non-preemptive) such that the precedence constraints are statisfied and the sum of weighted completion time is minimized. The problem is NP-hard and a 2-approximation is known.
Reduction from minimum cumulative sum problem to Precedence constrained scheduling problem : For each element create a job with p = 1, w = 0. Also for each set create a job with p = 0, w = 1. Create the precedence graph, such that if element $e \in S$, then $e$ must be scheduled before $S$. I think this special case of the scheduling problem is also NP-hard.
See the following links,
1) http://www.win.tue.nl/~gwoegi/papers/precsum.pdf
2) http://web.engr.illinois.edu/~chekuri/papers/dam_sched.ps
Shalmoli Gupta already explained that the general problem is NP-Hard, so I decided to investigate if any special cases are polynomial solveable. Eventually, I found a solution to the special case of sets that represent a tree, or more generally, a series parallel order by subset inclusion with all incomparable sets disjoint.
One property that makes things easier is if the list of sets is closed under intersection. If $s_1 \subseteq s_2$, then, there is an optimal ordering in which $s_1$ comes before $s_2$. We can assume WLOG that the optimal ordering is a linear extension of the partial order given by subset inclusion.
Since all subsets of a set appear before it in the order, this means that the amount added to the running sum by a given set is fixed, regardless of where it appears. If $S$ is the list of sets, then the incremental cost of a set is the number of elements in s that are not in any subset of s that appears in $S$. If the same set appears multiple times in $S$, we can arbitrarily choose one to go first and let the others have cost 0.
This means that the problem is equivalent to the problem of minimum weighted completion time in single machine scheduling with precedence constraints. In this problem, given a set of jobs with weights $w_j$ and times $t_j$, and a partial order on the jobs $P$, we wish to find an ordering of the jobs that minimizes the weighted total completion time, i.e.
$\sum_{i=1}^{n} w_{j_i} \left(\sum_{k=1}^{i} t_{j_k}\right)$
subject to the precedence constraints $P$. The minimal cumulative set problem with intersection closed sets can be turned into this by creating a job for each set, where every job has weight 1, time equal to the incremental cost defined above, and $P$ is the order given by subset inclusion.
As it turns out, this problem is NP-Hard for general $P$ as well. However, certain special forms of $P$ can be solved in polynomial time.
This paper gives an $O(nlogn)$ algorithm for the case of series parallel orders $P$ (which includes the important case of trees as well). Unfortunately, I couldn't access that paper, so I decided to try to reinvent it independently. Here's what I came up with.
In order to solve this problem, several observations are required.
First off, in the absence of any precedence constraints, the optimal solution is to simply sort the jobs in order of increasing $\frac{t_j}{w_j}$. For simplicity, I will be referring to this as the value of the job, abbreviated $v(j)$. Note that since sorting is $O(nlogn)$, it is impossible to do better than this complexity.
Rule 1 Let $a$ and $b$ be jobs such that $a < b \in P$ and b covers a. If $v(a) < v(b)$, then we can drop the constraint $a < b$ without affecting the optimal ordering or objective value.
Suppose $b$ appears before $a$ in the optimal ordering of the relaxed problem. Since b covered a originally, that means that all jobs between b and a in the new ordering are incomparable to a and b. But since b has a higher value than a, we can decrease the objective value by swapping b and a, a contradiction.
Likewise, we can drop the constraint in the case that $v(a) = v(b)$ as long as we ensure that after sorting by value, we break ties by consulting the precedence relations of the original (simplified) problem. This ensures that the optimal solution found for the relaxed problem is also an optimal solution to the original problem.
Therefore, whenever b covers a and $v(a) \leq v(b)$, we can simplify the problem by dropping the constraint $a < b$.
Rule 2 Suppose that we know that b follows immediately after a in an optimal solution. We can merge a and b into a new node c with $w_c = w_a + w_b$ and $t_c = t_a + t_b$, while contracting the poset $P$ appropriately.
The optimal objective value of the new problem differs by a constant from the original objective value (specifically $w_at_b$), however this constant does not depend on ordering and hence the optimal ordering is not affected. We can recover an optimal solution to the old problem by taking an optimal solution to the new problem and replacing $c$ with $ab$.
Rule 3 Suppose that in an optimal solution to a problem instance, $a$ comes immediately before $b$ and $v(a) > v(b)$. Now suppose we create a larger problem instance by adding new jobs with the new poset formed from series or parallel composition with the original. There will always be an optimal solution to the larger problem where $a$ comes immediately before $b$.
Suppose otherwise. Let the optimal solution contain $a, x_1, x_2, \ldots, b$. Since $P$ was formed by series parallel composition, we know that all $x_i$s are incomparable to $a$ and $b$. Merge all the $x_i$ nodes into a new node $x'$ using rule 2. Now consider $v(x')$. If $v(x') \leq v(a)$ then we can swap $x'$ and $a$ without increasing objective value. Likewise, if $v(x') \geq v(b)$, we can swap $x'$ and $b$. Therefore, $v(a) < v(x') < v(b)$. But $v(a) > v(b)$, a contradiction.
Using rule 2 and rule 3, we can already get a simple but suboptimal $O(n^2)$ algorithm. Since $P$ is a series parallel order, assume the input contains a tree representation of $P$ where each node represents series composition or parallel composition, and the leaves are individual jobs. We can find an optimal solution with preorder traversal of the tree by maintaining the invariant that the optimal solution to each subproblem is a chain in increasing value order.
Suppose $P$ is the series composition of subproblems with posets $P_1$ and $P_2$. Let the optimal solutions be ordering $C_1$ and $C_2$. The optimal solution to $P$ is clearly the concatenation of these chains. However, it is possible that the first job in $C_2$ has lower value than the last job in $C_1$. In order to maintain the invariant that the solution is a sorted chain, we use rule 3 + rule 2 to merge the endpoints as long as they aren't in sorted order.
If $P$ is instead a parallel composition, we simply take the sorted chains $S_1$ and $S_2$ and merge them into a new sorted chain. Thanks to the invariant, this is valid.
Unfortunately, this algorithm is $O(n^2)$. In order to get an $O(nlogn)$ algorithm, we need to compute the chains lazily using rule 1.
Specifically, if a subproblem contains only nodes where the precedence constraints are the same as the order of values, then we can forget the precedence constraints completely and only look at the values. This is ensured by the same invariant that ensured the solutions are sorted chains in the previous algorithm.
Instead of computing a sorted chain for each subproblem, we represent the optimal solution to a subproblem as a pair of Fibonacci heaps, one a min heap, and one a max heap, both containing all the jobs in the subproblem. This means that we can pop off the minimum or maximum element of the solution in logarithmic time.
As before, we do a preorder traversal. Where $P$ is a series composition, we examine the maximum job of the first heap pair and the minimum job of the second heap pair. If their values are out of order, we pop them off and merge them using rule 2 and 3. Then we compare the newly created job to the new endpoints and continue popping and merging as long as they are out of order. Once the endpoints no longer have out of order values, we can safely forget the series precedence restriction thanks to rule 1. Then we just push the newly created jobs if any onto a heap, then merge the heaps to create the heap pair representing the solution to $P$ itself.
For a parallel composition, we simply merge the heap pairs. The new min heap is the merge of the min heap from each subproblem and likewise with the max heap. Note that Fibonacci heaps are mergeable in constant time.
Once we have a heap pair representing the solution to the entire problem, we can find the actual solution ordering by popping off the min heap until it is empty. After that we undo all the rule 2 substitutions to get a solution to the original problem.
Each job that is popped off a heap is either immediately merged into a new job, reducing the total job count, or is popped exactly once at the end. Therefore there is at most a linear number of heap pops, leading to $O(nlogn)$ time over all. The other operations are constant time per node or job and hence linear over all.
