Precedence constraints in combinatorial optimization

Precedence Constraints are a common restriction in scheduling, ensuring that certain tasks can only be executed after specific predecessors have been completed. Beyond scheduling, precedence constraints also appear in many other optimization problems, ranging from transportation and routing to packing problems. This dissertation investigates various combinatorial optimization problems under precedence constraints. While classical precedence constraints are typically described by partial orders, this work also considers more flexible variants. The dissertation begins with the development of a unified model for optimization under precedence constraints, representing precedence constraints as Boolean formulas. Existing models for precedence constraints emerge as special cases of this definition: For example, classical precedence constraints can be expressed as conjunctive clauses. Based on this definition, we first study a classical scheduling problem, where tasks of uniform length are processed on parallel machines. We focus on the parameterized complexity with respect to two parameters: the total number of predecessors and the total number of successors. With respect to the first parameter, the problem is shown to be FPT (fixed-parameter tractable), making it manageable when the parameter size is small. Regarding the second parameter, the dissertation analyzes the parameterized hardness of the problem under various structural restrictions on the Boolean formulas. Next, the work extends the concept of precedence constraints to two other classical combinatorial optimization problems. For the shortest-path problem, it analyzes the complexity concerning feasibility and optimality and develops a dynamic programming approach. While this algorithm generally has exponential runtime, it provides the foundation for polynomial-time solutions in certain special cases. For the maximum matching problem, precedence constraints mean that edges join the matching sequentially and can only be added once their predecessor vertices are already covered. We analyze the complexity of various special cases and develop a dynamic programming algorithm for constant treewidth. The final chapter addresses search on trees, where a target node must be located through queries to the edges. This problem is related to precedence-constrained problems because the order of queries is constrained by the tree structure. Based on linear programming, the dissertation develops a constant-factor approximation algorithm for a broad class of objective functions.