Budget Minimization with Precedence Constraints

• DOI: 10.48550/arxiv.1905.13740
• Publication Date: 2019-01-01
• Authors: Marinus Gottschau; Felix Happach; Marcus Kaiser; Clara Waldmann
• Keywords: Minification

Budget Minimization is a scheduling problem with precedence constraints, i.e., on partially ordered set of jobs $(N, \unlhd)$. A job $j \in N$ available for scheduling, if all $i \unlhd j$ are completed. Further, each assigned real valued costs $c_{j}$, which can be negative or positive. schedule an ordering $j_{1}, \dots, j_{\vert N \vert}$ in $N$. The budget the external investment needed to complete jobs, it $\max_{l \{0, \vert \} } \sum_{1 \le k l} c_{j_{k}}$. goal find minimum budget. Rafiey et al. (2015) showed that NP-hard following from reduction molecular folding problem. We extend this result and prove $α(N)$-approximate even bipartite partial orders. present structural insights lead arguably simpler algorithms extensions results by (2015). In particular, we show there always exists optimal solution partitions schedules subset independently other jobs. use insight derive polynomial-time solve optimality series-parallel convex